2000 | OriginalPaper | Buchkapitel
Scheduling under Uncertainty: Optimizing against a Randomizing Adversary
verfasst von : Rolf H. Möhring
Erschienen in: Approximation Algorithms for Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.