Template-type: ReDif-Paper 1.0
Author-Name: Skutella Martin
Author-Name: Uetz Marc
Author-workplace-name: METEOR
Title: Stochastic Machine Scheduling with Precedence Constraints
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. Building upon a linear programming relaxation by Möhring, Schulz and Uetz (Journal of the ACM 46, 1999, 924-942) and an idle time charging scheme by Chekuri, Motwani, Natarajan, and Stein (SIAM Journal on Computing 31, 2001, 146-166) we derive the first constant-factor approximation algorithms for this model.
Keywords: computer science applications; 
Series: Research Memoranda
Creation-Date: 2002
Number: 026
File-URL: http://digitalarchive.maastrichtuniversity.nl/fedora/objects/guid:c322a07d-d469-443d-84bc-2d1f5503b020/datastreams/ASSET1/content
File-Format: application/pdf
File-Size: 140233
Handle: RePEc:unm:umamet:2002026