Scheduling under Uncertainty: Optimizing Against a Randomizing Adversary

Invited contribution to the Proceedings of the 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. Lecture Notes in Computer Science 1913, pages 15-26.

uncertainty, scheduling, online algorithm, project planning

Deterministic models for project scheduling and control 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 the expected project duration and cost frequently observed in practice. To cope with these phenomena, we consider scheduling models in which processing times are random but precedence and resource constraints are fixed. Scheduling is done by policies which consist of an online process of decisions that are based on the observed past and the a priori knowledge of the distribution of processing times. We give an informal survey on different classes of policies and show that suitable combinatorial properties of such policies give insight into optimality, computational methods, and their approximation behavior. In particular, we present recent constant-factor approximation algorithms for simple policies in machine scheduling that are based on a suitable polyhedral relaxation of the performance space of policies.

Download as [PDF] [ps.gz]