Stochastic machine scheduling with precedence constraints

Skutella, M. and Uetz, M.J. (2005) Stochastic machine scheduling with precedence constraints. SIAM Journal on Computing, 34 (4). pp. 788-802. ISSN 0097-5397

PDF
Restricted to UT campus only: Request a copy
194Kb

Abstract:	We consider parallel, identical machine scheduling problems, where the jobs are subject to precedence constraints and release dates, and where the processing times of jobs are governed by independent probability distributions. Our 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 [J. ACM, 46 (1999), pp. 924–942] and a delayed list scheduling algorithm by Chekuri et al. [SIAM J. Comput., 31 (2001), pp. 146–166], we derive the first constant-factor approximation algorithms for this model.
Item Type:	Article
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/62396
Official URL:	http://dx.doi.org/10.1137/S0097539702415007
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page