Single machine stochastic scheduling: Minimizing the number of tardy jobs

This paper deals with a single machine scheduling problem of determining a sequence so as to minimize the number of tardy jobs in a stochastic sense. In this model the processing times of jobs are assumed to be random variables with known distributions. When the processing time is a known constant, the problem of minimizing the number of tardy jobs on a single machine can be solved optimally by a well-known procedure due to Moore, but in a form suggested by Hodgson. In this paper, it shows that if job processing times can be stochastically ordered, an approach which is similar to the Moore and Hodgson algorithm will yield an optimal solution.