Single Machine Tardiness Sequencing Heuristics

This paper presents a collection of heuristics for the single machine total (weighted) tardiness problem. The methods considered range from simple quick and dirty heuristics to more sophisticated algorithms exploiting problem structure. These heuristics are compared to interchange and simulated annealing methods on a large set of test problems. For the total tardiness problem a heuristic based on decomposition performs very well, whereas for the total weighted tardiness problem simulated annealing appears to be a viable approach. Our computational results also indicate that straightforward interchange methods perform remarkably well.