Evaluation of leading heuristics for the single machine tardiness problem

A recent paper on the single machine tardiness problem by Panwalker, Smith and Koulamas [8] disputes experimental results of Holsenback and Russell [5] that indicated the Net Benefit of Relocation (NBR) heuristic provides significant improvement over the adjacent pairwise interchange (API) routine of Fry et al. [4], which in turn, was reported to show better solution quality than the Wilkerson-Irwin (W-I) heuristic ([13]). Panwalker et al. [8] claim that the P-S-K heuristic yields better results than the other methods over a wide range of problems and suggest that the NBR heuristic is not only inferior to the P-S-K heuristic, but also inferior to the API and W-I routines. This paper will shed new light on the quality of the experimentation of Panwalker et al. [8] and show that in general, the P-S-K heuristic is inferior to the NBR heuristic.