A recent paper on the single machine tardiness problem by Panwalker et al. disputes experimental results of Holsenback and Russell that indicated the Net Benefit of Relocation (NBR) heuristic provides significant improvement over the adjacent pairwise interchange (API) routine of Fry et al., which in turn, was reported to show better solution quality than the Wilkerson–Irwin (W–I) heuristic. Panwalker et al. 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 experimentaton of Panwalker et al. and show that in general, the P–S–K heuristic is inferior to the NBR heuristic.
