KNAPSACK-LIKE SCHEDULING PROBLEMS, THE MOORE-HODGSON ALGORITHM AND THE TOWER OF SETS PROPERTY

Suppose there are n jobs, each with a specified processing time, release date, due date and weight. The objective is to schedule the jobs for processing by a single machine so that the total weight of the late jobs is minimized. A well-known algorithm of Moore and Hodgson solves this problem in O(n log n) time when all release dates are equal, provided processing times and job weights are, in a certain sense, 'agreeable.' In this paper, we show the Moore-Hodgson algorithm can be adapted to solve three other special cases of the general scheduling problem. Each of these special cases can be formulated as a knapsack-like problem with nested inequality constraints. We show that optimal solutions to these knapsack-like problems exhibit a 'tower of sets' property, provided processing times, release dates, due dates and job weights satisfy certain order relations. We then show that the 'tower of sets' property enables dynamic programming recurrences to be solved by O(n log n) time procedures, and that this property contributes to simple proofs of validity of the procedures.