Single-machine Robust Scheduling with a Common Due Date Considering the Weighted Sum of Earliness and Tardiness(Theory and Methodology)

概要

論文の詳細を見る
This study is concerned with the single-machine scheduling problem for jobs with a common due date. A penalty is incurred to the jobs completed before or after the given due date, and the minimization of the weighted sum of penalties is the primary objective for the problem. This study further assumes that the processing time of jobs is uncertain, but their maximum and minimum processing times are deterministic and known in advance. A combination of actual processing time of jobs constitutes a scenario, and a robust schedule of which worst-case performance is best under the set of all candidate scenarios is presented. For 210 problem instances with seven jobs, robust schedules were obtained and then evaluated under four reduced sets of scenarios in the numerical experiment. The results revealed that the robust schedules initially obtained often produced good results under the reduced sets of scenarios. From the viewpoint of best worst-case performance, obtaining a robust schedule that considers all potential scenarios is shown to be beneficial even if some scenarios rarely happen and are negligible.
2011-02-15