Open AccessA Comment on a Paper of Maxwell
Author(s) -
Jeffrey B. Sidney
Publication year - 1972
Publication title -
management science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 4.954
H-Index - 255
eISSN - 1526-5501
pISSN - 0025-1909
DOI - 10.1287/mnsc.18.11.716
Subject(s) - notation , integer programming , computer science , minor (academic) , cutting plane method , integer (computer science) , plane (geometry) , mathematics , algorithm , mathematical optimization , calculus (dental) , programming language , arithmetic , law , medicine , geometry , dentistry , political science
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.