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.
