A robust optimization approach for scheduling with uncertain start-time dependent costs
Computers & Operations Research · 2026-12 · 196 · 107637
DOI: 10.1016/j.cor.2026.107637 ↗Kurz gefasst
Fachartikel in der Zeitschrift Computers & Operations Research, 2026-12. Verfasst von Sofía Rodríguez-Ballesteros und 4 weiteren Autor:innen. Die Arbeit nennt 47 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: European Regional Development Fund, Generalitat Valenciana.
Abstract (Originalsprache)
In this work, we study a single-machine scheduling problem that aims at minimizing the total cost of a schedule subject to start-time dependent costs. This framework naturally captures scenarios where costs fluctuate throughout the day, such as time-varying energy or labor prices. To model more realistic scenarios, we assume that these costs lie within a budgeted uncertainty set and propose a two-stage robust optimization approach. In a first stage, the order in which activities should be executed is decided. After a cost scenario has been revealed, the starting times for each activity are established, subject to the ordering from the first stage. We demonstrate that the proposed problem is NP-hard and not approximable, implying the complexity of its robust counterpart. Furthermore, we show that already evaluating a first-stage solution is NP-hard when the uncertainty set is discrete. We develop models and solution methods for both continuous and discrete budgeted uncertainty. In computational experiments, we compare these approaches and demonstrate the advantages of including uncertainty beforehand.
Förderung
- European Regional Development Fund
- Generalitat Valenciana
Zitieren
APA
Rodríguez-Ballesteros, S., Alcaraz, J., Anton-Sanchez, L., Goerigk, M., & Henke, D. (2026). A robust optimization approach for scheduling with uncertain start-time dependent costs. Computers & Operations Research, 196, 107637. https://doi.org/10.1016/j.cor.2026.107637
Vancouver
Rodríguez-Ballesteros S, Alcaraz J, Anton-Sanchez L, Goerigk M, Henke D. A robust optimization approach for scheduling with uncertain start-time dependent costs. Computers & Operations Research. 2026;196:107637. doi:10.1016/j.cor.2026.107637
BibTeX
@article{RodrguezBallesteros2026,
author = {Rodríguez-Ballesteros, Sofía and Alcaraz, Javier and Anton-Sanchez, Laura and Goerigk, Marc and Henke, Dorothee},
title = {A robust optimization approach for scheduling with uncertain start-time dependent costs},
journal = {Computers & Operations Research},
year = {2026},
volume = {196},
pages = {107637},
doi = {10.1016/j.cor.2026.107637}
}
EUVIMED