Stochastic machine scheduling with precedence constraints

M. Skutella, Marc Jochen Uetz

Research output: Contribution to journalArticleAcademicpeer-review

57 Citations (Scopus)

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.
Original languageUndefined
Article number10.1137/S0097539702415007
Pages (from-to)788-802
Number of pages15
JournalSIAM journal on computing
Volume34
Issue number4
DOIs
Publication statusPublished - Apr 2005

Keywords

  • EWI-13110
  • IR-62396

Cite this