Robust scheduling with budgeted uncertainty - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2019

Robust scheduling with budgeted uncertainty

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

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⟩
422 Consultations
1063 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More