We consider parallel, identical machine scheduling
problems where the jobs are subject to precedence constraints,
release dates, and the processing times of jobs are governed by
independent probability distributions. The objective is to minimize
the expected value of the total weighted completion time `&;
w_j C_j, where w_jgeq 0`. Building upon a linear programming
relaxation by Moehring, Schulz, and Uetz, and an idle time charging
scheme by Chekuri, Motwani, Natarajan, and Stein, we derive the
first constant-factor approximation algorithms for this model.
