On stochastic scheduling problems with due dates

A collection of stochastic jobs is available to be processed by a single machine. Each job earns a reward when it is finished, provided that it is finished before its duo date. The highest completion rate (HCR) strategy always processes jobs with the largest probability of imminent completion. This strategy is shown to be optimal in a number of important cases. We also consider the general problem of evaluating suboptimal strategies.