A Comment on a Paper of Maxwell

In his paper “On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs,” [Maxwell, W. L. 1970. On sequencing n jobs on one machine to minimize the number of late jobs. Management Sci. 16(5, January).], Maxwell presents an integer programming formulation (which we shall call P) of a one-machine job-shop problem, and attempts to prove the validity of Moore's optimal algorithm [Moore, J. M. 1908. An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Sci. 15(1, September).] by applying cutting plane constraints to the program P. Unfortunately, Maxwell's proof is incorrect. In this brief note, we shall locate Maxwell's error, and present an example, which casts doubt on the possibility of minor modifications being sufficient to correct the proof. We shall adopt much of the notation of Maxwell's paper.

• 저널Management Science · 18(11) · 716–717
• 토픽Scheduling and Optimization Algorithms · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.18.11.716
• 저자Jeffrey B. Sidney