NEW LOWER AND UPPER-BOUNDS FOR SCHEDULING AROUND A SMALL COMMON DUE-DATE

We consider the single-machine problem of scheduling n jobs to minimiz e the sum of the deviations of the job completion times from a given s mall common due date. For this NP-hard problem, we develop a branch-an d-bound algorithm based on Lagrangian lower and upper bounds that are found in O(n log n) time. We identify conditions under which the bound s concur; these conditions can be expected to be satisfied by many ins tances with n not to small. In our experiments with processing times d rawn from a uniform distribution, the bounds concur for n greater-than -or-equal-to 40. For the case where the bounds do not concur, we prese nt a refined lower bound that is obtained by solving a subset-sum prob lem of small dimension to optimality. We further develop a 4/3-approxi mation algorithm based upon the Lagrangian upper bound.