Robust single machine scheduling for minimizing total flow time in the presence of uncertain processing times

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

30 Scopus citations

Abstract

This research deals with the single machine scheduling problem (SMSP) with uncertain job processing times. The single machine robust scheduling problem (SMRSP) aims to obtain robust job sequences with minimum worst-case total flow time. We describe uncertain processing times using intervals, and adopt an uncertainty set that incorporates a budget parameter to control the degree of conservatism. A revision of the uncertainty set is also proposed to address correlated uncertain processing times due to a number of common sources of uncertainty. A mixed integer linear program is developed for the SMRSP, where a linear program for determining the worst-case total flow time is integrated within the conventional integer program of the SMSP. To efficiently solve the SMRSP, a simple iterative improvement (SII) heuristic and a simulated annealing (SA) heuristic are developed. Experimental results demonstrate that the proposed SII and SA heuristics are effective and efficient in solving SMRSP with practical problem sizes.

Original languageEnglish
Pages (from-to)102-110
Number of pages9
JournalComputers and Industrial Engineering
Volume74
Issue number1
DOIs
StatePublished - 1 Jan 2014

Keywords

  • Robust scheduling
  • Single machine
  • Total flow time

Fingerprint Dive into the research topics of 'Robust single machine scheduling for minimizing total flow time in the presence of uncertain processing times'. Together they form a unique fingerprint.

Cite this