Scheduling in static jobshops for minimizing mean flowtime subject to minimum total deviation of job completion times

摘要

In this paper, the problem of minimizing total absolute differences of completion times (TADC) of jobs and mean flowtime is studied. The objective of minimizing TADC ensures the completion times of jobs are close to one another, while the objective of minimizing mean flowtime minimizes the average time spent by the jobs in the system. Early completion of jobs is not desirable in delivery situations when jobs have to be dispatched together for a customized delivery or assembly and, particularly, when the finished jobs incur costs for preserving/holding them till other matching job orders complete. In this work, lower bounds on TADC and mean flowtime subject to minimum TADC for the static jobshop problem are reported. A simulated annealing algorithm using the concept of backward scheduling is proposed for minimizing mean flowtime subject to optimal TADC, and the proposed algorithm is evaluated using 82 jobshop scheduling problems taken from literature, of size varying from 6-jobs 6-machines to 50-jobs 20-machines. Finally, we combine a statistical optimum prediction technique with the proposed simulated annealing algorithm, and evaluate the statistical bounds established for the objective of minimizing mean flowtime subject to minimum TADC on the benchmark problems.