An adaptive robust optimization model for parallel machine scheduling

Izack Cohen*, Krzysztof Postek, Shimrit Shtern

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)
2 Downloads (Pure)


Real-life parallel machine scheduling problems can be characterized by: (i) limited information about the exact task duration at the scheduling time, and (ii) an opportunity to reschedule the remaining tasks each time a task processing is completed and a machine becomes idle. Robust optimization is the natural methodology to cope with the first characteristic of duration uncertainty, yet the existing literature on robust scheduling does not explicitly consider the second characteristic the possibility to adjust decisions as more information about the tasks duration becomes available, despite that re-optimizing the schedule every time new information emerges is standard practice. In this paper, we develop an adaptive robust optimization scheduling approach that takes into account, at the beginning of the planning horizon, the possibility that scheduling decisions can be adjusted. We demonstrate that the suggested approach can lead to better here-and-now decisions and better makespan guarantees. To that end, we develop the first mixed integer linear programming model for adaptive robust scheduling, and a two-stage approximation heuristic, where we minimize the worst-case makespan. Using this model, we show via a numerical study that adaptive scheduling leads to solutions with better and more stable makespan realizations compared to static approaches.
Original languageEnglish
Pages (from-to)83-104
Number of pages22
JournalEuropean Journal of Operational Research
Issue number1
Publication statusPublished - 2022

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.


  • Scheduling
  • Robust optimization
  • Parallel machine scheduling
  • Robust scheduling


Dive into the research topics of 'An adaptive robust optimization model for parallel machine scheduling'. Together they form a unique fingerprint.

Cite this