direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 700-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Scheduling under uncertainty: Bounding the makespan distribution
primary: 90B36 Scheduling theory, stochastic
secondary: 90B35 Scheduling theory, deterministic
68M20 Performance evaluation; queueing; scheduling
uncertainty, scheduling, makespan distribution function, stochastic bounds, 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. This phenomenon occurs even in the absence of resource constraints, and has been the subject of extensive research in discrete mathematics and operations research.
This article presents a survey on the reasons for this phenomenon, its complexity, and on methods how to obtain more relevant information. To this end, we consider scheduling models with fixed precedence constraints, but (independent) random processing times. The objective then is to obtain information about the distribution of the project makespan. We will demonstrate that this is an #P-complete problem in general, and then consider several combinatorial methods to obtain approximate information about the makespan distribution.
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe