Thumbnail Image
🆕 Date Issued:
2000
🗄 In DepositOnce:2022-05-11
Submitted Version

Please use this identifier to cite or link to this item:

Scheduling precedence-constrained jobs with stochastic processing times on parallel machines

Skutella, Martin; Uetz, Marc

Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin

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.
scheduling problemsapproximation algorithm
In Copyright
Full item page