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, relea se date, due date and weight. The objective is to schedule the jobs fo r 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, prov ided processing times and job weights are, in a certain sense, 'agreea ble.' In this paper, we show the Moore-Hodgson algorithm can be adapte d to solve three other special cases of the general scheduling problem . Each of these special cases can be formulated as a knapsack-like pro blem with nested inequality constraints. We show that optimal solution s to these knapsack-like problems exhibit a 'tower of sets' property, provided processing times, release dates, due dates and job weights sa tisfy certain order relations. We then show that the 'tower of sets' p roperty enables dynamic programming recurrences to be solved by O(n lo g n) time procedures, and that this property contributes to simple pro ofs of validity of the procedures.