Otto-Hahn-Str. 16, Raum 205

In this work we study min max 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 focus on problems minimizing the (weighted and unweighted) sum of completion times on a single machine and minimizing the makespan on parallel and unrelated machines. Our results concern polynomial algorithms, pseudo-polynomial algorithms, and 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 NP-hard in the strong sense. This is joint work with Marin Bougeret (LIRMM, Montpellier) and Artur Alves Pessoa (Universidade Federal Fluminense).

Im Rahmen des Graduiertenkollegs 1855 ``Diskrete Optimierung technischer Systeme unter Unsicherheit``

Dr. Michael Poss

Laboratoire d'Informatique, de Robotique et de Microelectronique de Montpellier