Coping with Uncertainty in Scheduling

                        Rolf H. M\"ohring


Deterministic models for scheduling and project control usually suffer from 
the fact that they assume complete information and neglect random
influences 
that occur during project execution.  A typical consequence is the 
underestimation of expected project duration and cost frequently 
observed in practice.

The area of \emph{stochastic scheduling} provides theory and methods to 
cope with these phenomena.  I will survey recent developments for problems 
where processing times are random but precedence and resource constraints 
are fixed.  In this case, scheduling is done by an on-line process of 
decisions (a \emph{policy}) which are based on the observed past and the a 
priori knowledge of the distribution of processing times.  Suitable 
combinatorial properties of such policies lead to insights into optimality, 
computational methods, and their approximation behaviour.