Rescheduling a single machine with various objectives

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 noidle time and no-tardiness of remaining orders. They are the objective of minimizing total earliness of remaining orders with no-change in sequence of remaining orders, the objective of minimizing total completion time of new orders, 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 procedure for one objective and four intuitive heuristics for the other two objectives. We theoretically analyze performance 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.

Original languageEnglish
Pages (from-to)805-818
Number of pages14
JournalIndustrial Engineering and Management Systems
Issue number4
StatePublished - 2018


  • Computational Complexity
  • Heuristic Analysis
  • Order Disruption
  • Rescheduling


Dive into the research topics of 'Rescheduling a single machine with various objectives'. Together they form a unique fingerprint.

Cite this