direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 681-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

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.
primary: 90B36 Scheduling theory, stochastic
secondary: 90B35 Scheduling theory, deterministic
68M20 Performance evaluation; queueing; scheduling
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]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe