New Lower and Upper Bounds for Scheduling around a Small Common Date

摘要

Suppose a set of n jobs has to be scheduled on a single machine which can handleno 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. Lagrangian relaxation is applied to find new lower and upper bounds in O(nlog 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 equal to or greater than 50 in computational experiments with processing times drawn from different distributions over the integers 1,...,100. For the case where these bounds do not concur, a refinement of the lower bound is presented. This is obtained by solving a subset sum problem to optimality by a pseudo polynomial algorithm. If these bounds still do not concur, then branch-and-bound is applied; the computational results show that only little branching is needed. It is indicated to what extent the analysis also applies to the case that all early completions are weighted by a common weight alpha and all tardy completions by a common weight beta.