Stochastic machine scheduling with precedence constraints. (English) Zbl 1075.68008
Summary: 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 R. H. Möhring, A. S. Schulz and M. Uetz [J. Assoc. Comput. Mach. 46, 924–942 (1999; Zbl 1176.90262)] and a delayed list scheduling algorithm by C. Chekuri, R. Motwani, B. Natarajan and C. Stein [SIAM J. Comput. 31, 146–166 (2001; Zbl 0992.68066)], we derive the first constant-factor approximation algorithms for this model.
MSC:
68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
68Q25 | Analysis of algorithms and problem complexity |
68W25 | Approximation algorithms |
68W40 | Analysis of algorithms |
90B36 | Stochastic scheduling theory in operations research |
90C05 | Linear programming |