Minimizing worst-case regret of makespan on a single machine with uncertain processing and setup times

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

This research addresses a single machine scheduling problem with uncertain processing times and sequence-dependent setup times represented by intervals. Our objective is to obtain a robust schedule with the minimum absolute deviation from the optimal makespan in the worst-case scenario. The problem is reformulated as a robust traveling salesman problem (RTSP), whereby a property is utilized to efficiently identify worst-case scenarios. A local search-based heuristic that incorporates this property is proposed to solve the RTSP, along with a simulated annealing-based implementation. The effectiveness and efficiency of the proposed heuristic are compared to those of an exact solution method in the literature.

Original languageEnglish
Pages (from-to)144-151
Number of pages8
JournalApplied Soft Computing Journal
Volume23
DOIs
StatePublished - 1 Jan 2014

Keywords

  • Sequence-dependent setup times
  • Single machine scheduling
  • Uncertainty modeling

Fingerprint Dive into the research topics of 'Minimizing worst-case regret of makespan on a single machine with uncertain processing and setup times'. Together they form a unique fingerprint.

Cite this