Inhalt des Dokuments
Preprint 756-2002
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Stochastic Machine Scheduling with Precedence Constraints
- Authors
- Publication
- Submitted.
- Classification
-
not available
- Keywords
-
Stochastic scheduling, Approximation, Worst-case performance, LP-relaxation
- Abstract
-
We consider parallel, identical machine scheduling problems where the jobs are subject to precedence constraints, release dates, and the processing times of jobs are governed by independent probability distributions. The objective is to minimize the expected value of the total weighted completion time `&; w_j C_j, where w_jgeq 0`. Building upon a linear programming relaxation by Moehring, Schulz, and Uetz, and an idle time charging scheme by Chekuri, Motwani, Natarajan, and Stein, we derive the first constant-factor approximation algorithms for this model.
- Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe