Robust scheduling on a single machine to minimize total flow time

Chung-Cheng Lu, Shih Wei Lin, Kuo Ching Ying*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

69 Scopus citations


In a real-world manufacturing environment featuring a variety of uncertainties, production schedules for manufacturing systems often cannot be executed exactly as they are developed. In these environments, schedule robustness that guarantees the best worst-case performance is a more appropriate criterion in developing schedules, although most existing studies have developed optimal schedules with respect to a deterministic or stochastic scheduling model. This study concerns robust single machine scheduling with uncertain job processing times and sequence-dependent family setup times explicitly represented by interval data. The objective is to obtain robust sequences of job families and jobs within each family that minimize the absolute deviation of total flow time from the optimal solution under the worst-case scenario. We prove that the robust single machine scheduling problem of interest is NP-hard. This problem is reformulated as a robust constrained shortest path problem and solved by a simulated annealing-based algorithmic framework that embeds a generalized label correcting method. The results of numerical experiments demonstrate that the proposed heuristic is effective and efficient for determining robust schedules. In addition, we explore the impact of degree of uncertainty on the performance measures and examine the tradeoff between robustness and optimality.

Original languageEnglish
Pages (from-to)1682-1691
Number of pages10
JournalComputers and Operations Research
Issue number7
StatePublished - 1 Jul 2012


  • Robust scheduling
  • Sequence-dependent family setup times
  • Single machine scheduling
  • Total flow time


Dive into the research topics of 'Robust scheduling on a single machine to minimize total flow time'. Together they form a unique fingerprint.

Cite this