EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

A robust optimization approach for scheduling with uncertain start-time dependent costs

Sofía Rodríguez-Ballesteros, Javier Alcaraz, Laura Anton-Sanchez, Marc Goerigk, Dorothee Henke

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →