Robust scheduling with budgeted uncertainty

Marin Bougeret 1 Artur Alves Pessoa 2 Michael Poss 3
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Complete list of metadatas

Cited literature [27 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02020566
Contributor : Marin Bougeret <>
Submitted on : Wednesday, April 10, 2019 - 9:23:26 AM
Last modification on : Friday, May 3, 2019 - 12:08:04 PM

File

journal_v3_Fig.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Marin Bougeret, Artur Alves Pessoa, Michael Poss. Robust scheduling with budgeted uncertainty. Discrete Applied Mathematics, Elsevier, 2018, 261 (31), pp.93-107. ⟨10.1016/j.dam.2018.07.001⟩. ⟨lirmm-02020566⟩

Share

Metrics

Record views

113

Files downloads

170