An improved heuristic for the single-machine, weighted-tardiness problem

This research considers the single machine, total weighted-tardiness problem. We propose a method for modifying due dates that eases the construction of optimal schedules. We employ due date modification in a new heuristic that is fast, solving 50-job problems on an IBM 4381 in at most 0.14 CPU s. The heuristic is shown to be superior to previously known heuristics in minimizing total weighted-tardiness, especially in settings where 40% or more of the jobs can be completed without tardiness on the single machine.