A Simple Optimality Proof of Moore's Sequencing Algorithm

Abstract

In a recent article J. M. Moore [Moore, J. M. 1968. An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Sci. 14 (1, September) 102–109.] gave an algorithm for minimizing the number of late jobs in a one machine sequencing problem. As indicated by the author, T. J. Hodgson has proposed a simpler version of this algorithm, for which version the proof of optimality is similar to the proof given by the author for the original algorithm. In this note a simpler proof of optimality, based on the inductive principle, will be presented for Hodgson's algorithm. As Moore's algorithm only differs on minor points, this proof covers it as well.