New lower and upper bounds for scheduling around a small common due date

Suppose a set of njobs has to be scheduled on a single machine. which can handle no more than one job at a time. The problem is to find a schedule that minimizes the sum of the deviations of the job completion times from a given common due date that is smaller than the sum of the processing times. This problem is known to be NP-hard. There exists a pseudo-polynomial algorithm that is able to solve instances up to 1000 jobs. Branch-and-bound algorithms can solve instances up to only 25 jobs. We apply Lagrangian relaxation to find new lower and upper bounds in O(n log n) time. This upper bound is used to develop a heuristic with both a good worst-case and empirical behavior: its solution value is guaranteed to be no more than 4/3 times the optimal solution value, and always concurred with the lower bound for n = 50 in our computational experiments with processing times drawn from different distributions over the integers 1, ... , 100. For the case these bounds do not concur, we present a refinement of the lower bound. This is obtained by solving a subset-sum problem to optimality by a pseudo-polynomial algorithm; this subset-sum problem is of considerably smaller dimension than the common due date problem. If these bounds still do not concur, then we apply branch-and-bound; our computational results show that only little branching is needed. Finally, we indicate to what extent the analysis also applies to the case that all early completions are weighted by acommon weight a. and all tardy completions by a common weight \beta. Key Words & Phrases: single-machine scheduling, common due date, Lagrangian relaxation, approximation algorithm, worst-case behavior, empirical behavior.