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 he Wilkerson-Irwin, Holsenback-Russel, 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.