Dynamic scheduling of stochastic jobs on a single machine

In this paper, the problem of minimizing the expected number of tardy jobs on a single machine is investigated. Jobs having stochastic processing times and deterministic due dates arrive randomly. The objectives of this research are to evaluate the role of the variance of processing time and to develop a dynamic scheduling policy, which is simple and robust, so that it can be used in rapidly changing and uncertain manufacturing environments. A heuristic based on a myopically optimal solution is developed. The sufficient conditions for the optimality and the worst case analysis are also provided. Computational study validates its effectiveness by comparison with optimal solutions.