Scheduling about a common due date with earliness and tardiness penalties (Q908845)

The authors present a branch and bound algorithm for scheduling a set of independent jobs on a single machine where the objective is to minimize the mean squared derivation of the completion times about a common due date. They use a recursive scheme to compute the bounds. This procedure is relatively time consuming, but they provide a slightly different approach which computes weaker bounds in less time. A modification of this branch and bound algorithm yields a heuristic with constant performance guarantee. The paper is concluded by a test of the algorithm on job sets drawn from six different distributions of processing times. The authors compare their approach with an enumerative scheme of \textit{U. Bagchi}, \textit{R. S. Sullivan} and \textit{Y.-L. Chang} [Manage. Sci. 33, 894-906 (1987; Zbl 0636.90049)] and conclude that their branch and bound algorithm is significantly better than the existing method. It is interesting that the branch and bound algorithm begins to show some deterioration with job sets of more than 40 jobs and a large proportion of large processing times.