Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/323369 
Erscheinungsjahr: 
2024
Quellenangabe: 
[Journal:] Journal of Scheduling [ISSN:] 1099-1425 [Volume:] 28 [Issue:] 3 [Publisher:] Springer US [Place:] New York, NY [Year:] 2024 [Pages:] 269-287
Verlag: 
Springer US, New York, NY
Zusammenfassung: 
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.
Schlagwörter: 
Scheduling
Robust optimization
Recoverable robustness
Polyhedral uncertainty
Budgeted uncertainty
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.