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