Scheduling independent jobs with stochastic processing times and a common due date on parallel and identical machines

The authors propose a heuristic procedure that constructs a schedule for N jobs with stochastic processing times and a common due date on M parallel, identical machines. The criterion is the minimization of the total expected incompletion cost. A worst-case analysis for the ratio of the heuristic and optimal solutions is presented and a bound on the ratio is derived. The experimental results presented indicate that the heuristic procedure generates almost optimal solutions.