Algorithms and Complexity Analysis for Robust Single-Machine Scheduling Problems

Bita Tadayon, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


In this paper, we study a robust single-machine scheduling problem under four alternative optimization criteria: minimizing total completion time, minimizing total weighted completion time, minimizing maximum lateness, and minimizing the number of late jobs. We assume that job processing times are subject to uncertainty. Accordingly, we construct three alternative uncertainty sets, each of which defines job processing times that can simultaneously occur. The robust optimization framework assumes that, given a job schedule, a worst-case set of processing times will be realized from among those allowed by the uncertainty set under consideration. For each combination of objective function and uncertainty set, we first analyze the problem of identifying a set of worst-case processing times with respect to a fixed schedule, and then investigate the problem of selecting a schedule whose worst-case objective is minimal.

Original languageEnglish (US)
Pages (from-to)575-592
Number of pages18
JournalJournal of Scheduling
Issue number6
StatePublished - Dec 1 2015
Externally publishedYes


  • Complexity
  • Dynamic programming
  • Integer programming
  • Robust optimization

ASJC Scopus subject areas

  • Software
  • General Engineering
  • Management Science and Operations Research
  • Artificial Intelligence


Dive into the research topics of 'Algorithms and Complexity Analysis for Robust Single-Machine Scheduling Problems'. Together they form a unique fingerprint.

Cite this