SCHEDULING 2-POINT STOCHASTIC JOBS TO MINIMIZE THE MAKESPAN ON 2 PARALLEL MACHINES

Simple optimal policies are known for the problem of scheduling jobs t o minimize expected makespan on two parallel machines when the job run ning-time distribution has a monotone hazard rate. But no such policy appears to be known in general. We investigate the general problem by adopting two-point running-time distributions, the simplest discrete d istributions not having monotone hazard rates. We derive a policy that gives an explicit, compact solution to this problem and prove its opt imality. We also comment briefly on first-order extensions of the mode l, but each of these seems to be markedly more difficult to analyze.