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 journalJournal Article peer-review

74 Scopus citations

Abstract

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
Volume39
Issue number7
DOIs
StatePublished - 07 2012
Externally publishedYes

Keywords

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

Fingerprint

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