Inhalt des Dokuments
Preprint 681-2000
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Scheduling under Uncertainty: Optimizing Against a Randomizing Adversary
- Author
- Publication
- 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.
- Classification
-
MSC: primary: 90B36 Scheduling theory, stochastic secondary: 90B35 Scheduling theory, deterministic 68M20 Performance evaluation; queueing; scheduling - Keywords
-
uncertainty, scheduling, online algorithm, project planning
- Abstract
-
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.
- Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe