A SURVEY OF ALGORITHMS FOR THE SINGLE-MACHINE TOTAL WEIGHTED TARDINESS SCHEDULING PROBLEM

This paper surveys algorithms for the problem of scheduling jobs on a single machine to minimize total weighted tardiness. Special attention is given to two dynamic programming and four branch and bound algorithms. The dynamic programming algorithms both use the same recursion defined on sets of jobs, but they generate the sets in lexicographic order and cardinality order respectively. Two of the branch and bound algorithms use the quickly computed but possibly rather weak lower bounds obtained from linear and exponential functions of completion times problems. These algorithms rely heavily on dominance rules to restrict the search. The other two branch and bound algorithms use lower bounds obtained from the Lagrangean relaxation of machine capacity constraints and from dynamic programming state-space relaxation. They invest a substantial amount of computation time at each node of the search tree in an attempt to generate tight lower bounds and thereby generate only small search trees. A computational comparison of all these algorithms on problems with up to 50 jobs is given. © 1990.