On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs

An integer programming formulation for the problem of sequencing jobs on a single machine to minimize the number of late jobs is developed. The structure of the formulation is exploited to obtain the easily stated algorithm (previously developed by Moore [5]) for the solution of the problem and then to compare it to other similar allocation problems, among which is the Knapsack problem.