# Single machine robust scheduling with budgeted uncertainty Article - 2023

Marin Bougeret, Artur Alves Pessoa, Michael Poss

Marin Bougeret, Artur Alves Pessoa, Michael Poss, « Single machine robust scheduling with budgeted uncertainty  », Operations Research Letters, à paraître. ISSN 0167-6377

Abstract

We consider robust single machine scheduling problems. First, we prove that with uncertain processing times, minimizing the number of tardy jobs is NP-hard. Second, we show that the weighted variant of the problem has the same complexity as the nominal counterpart whenever only the weights are uncertain. Last, we provide approximation algorithms for the problems minimizing the weighted sum of completion times. Noticeably, our algorithms extend to more general robust combinatorial optimization problems with cost uncertainty, such as max-cut.