Home > Research > Publications & Outputs > Recoverable robust single machine scheduling wi...

Electronic data

  • Fulltext

    Final published version, 604 KB, fulltext

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Text available via DOI:

View graph of relations

Recoverable robust single machine scheduling with polyhedral uncertainty

Research output: Contribution to Journal/MagazineJournal articlepeer-review

E-pub ahead of print
<mark>Journal publication date</mark>30/06/2025
<mark>Journal</mark>Journal of Scheduling
Issue number3
Volume28
Number of pages19
Pages (from-to)269-287
Publication StatusE-pub ahead of print
Early online date19/12/24
<mark>Original language</mark>English

Abstract

This paper considers a recoverable robust single-machine scheduling problem under polyhedral uncertainty with the objective of minimising the total flow time. In this setting, a decision-maker must determine a first-stage schedule subject to the uncertain job processing times. Then following the realisation of these processing times, they have the option to swap the positions of up to Δ disjoint pairs of jobs to obtain a second-stage schedule. We first formulate this scheduling problem using a general recoverable robust framework, before we examine the incremental subproblem in further detail. We prove a general result for max-weight matching problems, showing that for edge weights of a specific form, the matching polytope can be fully characterised by polynomially many constraints. We use this result to derive a matching-based compact formulation for the full problem. Further analysis of the incremental problem leads to an additional assignment-based compact formulation. Computational results on budgeted uncertainty sets compare the relative strengths of the three compact models we propose.