A HEURISTIC FOR THE SINGLE-MACHINE TARDINESS PROBLEM

A heuristic (P-S-K) is presented in this paper for minimizing the mean tardiness for the single machine sequencing problem. This heuristic is compared with other available construction heuristics from the literature like the Wilkerson-Irwin (W-I), Holsenback-Russell (H-R), and API heuristics. It is shown that P-S-K yields better results than the other methods on a wide range of problems. Furthermore, as due dates become tight, P-S-K is substantially better than the other methods with respect to computational time.