Scheduling under Uncertainty: Optimizing against a Randomizing Adversary

Deterministic models for project schedulingand control suf- fer from the fact that they ssume complete inform tion and neglect random influences that occur during project execution. A typical con- sequence is the underestimation of the expected project duration and cost frequently observed in practice. To cope with these phenomena, we consider schedulingmodels in which processingtimes are random but precedence and resource constraints are fixed. Scheduling is done by poli- cies which consist of an an online process of decisions that are based on the observed past and the a priori knowledge of the distribution of pro- cessing times. We give an informal survey on different classes of policies and show that suitable combinatorial properties of such policies give in- sights into optimality, comput tional methods, and their approximation behavior. In particular, we present recent constant-factor approximation algorithms for simple policies in machine scheduling that are based on suitable polyhedral relaxation of the performance space of policies.