Robust scheduling with budgeted uncertainty - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Discrete Applied Mathematics Year : 2019

Robust scheduling with budgeted uncertainty


In this work we study robust scheduling problems assuming that the processing times can take any value in the budgeted uncertainty set introduced by Bertsimas and Sim (2003, 2004). We consider problems on a single machine that minimize the (weighted and unweighted) sum of completion times and problems that minimize the makespan on parallel and unrelated machines. We provide approximation algorithms: constant factor, average non-constant factor, (fully or not) polynomial time approximation schemes. In addition, we prove that the robust version of minimizing the weighted completion time on a single machine is in the strong sense.
Fichier principal
Vignette du fichier
journal_v3_Fig.pdf (508.62 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-02020566 , version 1 (10-04-2019)



Marin Bougeret, Artur Alves Pessoa, Michael Poss. Robust scheduling with budgeted uncertainty. Discrete Applied Mathematics, 2019, 261, pp.93-107. ⟨10.1016/j.dam.2018.07.001⟩. ⟨lirmm-02020566⟩
430 View
1077 Download



Gmail Mastodon Facebook X LinkedIn More