A Simple Optimality Proof of Moore's Sequencing Algorithm

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.

• 저널Management Science · 17(1) · 116–118
• 토픽Scheduling and Optimization Algorithms · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.17.1.116
• 저자L. B. J. M. Sturm