Inhalt des Dokuments
Preprint 691-2000
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Scheduling Precedence-Constrained Jobs with Stochastic Processing Times on Parallel Machines
- Authors
- Publication
- Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'01), 589-590.
- Classification
-
not available
- Keywords
-
not available
- Abstract
-
We consider parallel machine scheduling problems where the jobs are subject to precedence constraints, and the processing times of jobs are governed by independent probability distributions. The objective is to minimize the weighted sum of job completion times &;j wjC_j in expectation, where wj&; 0. Building upon an LP-relaxation by Möhring, Schulz, and Uetz (J.ACM 46 (1999), pp.924-942) and an idle time charging scheme by Chekuri, Motwani, Natarajan, and Stein (SIAM J. Comp., to appear) we derive the first approximation algorithms for this model.
- Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe