A note on the equivalence of two heuristics to minimize total tardiness

Over the last thirty years, many researchers have studied single machine static and deterministic scheduling with the objective of minimizing total tardiness. It has been established that the tardiness problem is NP-hard. So it is unlikely that a polynomial time algorithm can be found for developing optimal solutions to this problem. The Modified Due Date rule (MDD) is generally considered to be an efficient heuristic that deals with the tardiness problem. Recently, Panwalkar et al. have proposed the PSK rule as effective in dealing with tardiness. The purpose of this paper is to show that the PSK rule is an implementation of the MDD rule. Furthermore, the relationship between the MDD rule and the WI (Wilkeson and Irwin) rule is clarified.