Rescheduling a Single Machine with Various Objectives

摘要

We consider a single machine rescheduling problem with two types of disruptions such as order cancelations and new orders after the initial scheduling. The original objective is minimizing total completion time and after the disruption, we reschedule remaining (not cancelled) and new orders with one of the three objectives under the condition of no- idle time and no-tardiness of remaining orders. They are the objective of minimizing total earliness of remaining or- ders with no-change in sequence of remaining orders, the objective of minimizing total completion time of new or- ders, and finally, a composite objective, which is minimizing the sum of total completion time of new orders and total earliness of remaining orders. We first prove complexity of the problems. Then, we develop an optimal solution pro- cedure for one objective and four intuitive heuristics for the other two objectives. We theoretically analyze perfor- mance of each heuristic. Finally, we empirically evaluate each heuristic, and the results indicate that heuristic H2, which uses the LPT rule to select a new order to be scheduled first, performs better than H1 and H3 and in turn, H1, which uses the LS rule to select a new order, performs better than H3, which uses the SPT rule.