Title : On the complexity of single machine scheduling problems 
under scenario-based uncertainty

Mohamed Ali Aloulou - Federico della Croce
LAMSADE - Paris Dauphine

In this paper, we are interested in scheduling environments where 
some job characteristics are uncertain. This uncertainty is modeled 
through a finite set of well-defined scenarios. In such a context, 
we search for a solution that is acceptable for any considered 
scenario. For this purpose, several criteria can be applied to select 
among the solutions. We use here the so-called maximal cost criterion. 
We present algorithmic and computational complexity results for 
several single machine scheduling problems.