An improved dynamic programming algorithm for the single-machine mean absolute deviation problem with a restrictive common due date

In 1991, Hall et al showed that the problem of minimizing the mean earliness and tardiness of n jobs scheduled on a single machine around a restrictive common due date is NP-complete. They proposed a pseudo-polynomial dynamic programming algorithm, called Optcet, for identifying an optimal schedule. This paper points out that two of the three subroutines in Optcet can be eliminated and, consequently, the total computational effort can be reduced significantly.