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

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

0.00 Avg rating0 Votes
Article ID: iaor1995130
Country: United States
Volume: 42
Issue: 1
Start Page Number: 102
End Page Number: 110
Publication Date: Jan 1994
Journal: Operations Research
Authors: , ,
Keywords: Lagrangean relaxation
Abstract:

The authors consider the single-machine problem of scheduling n jobs to minimize the sum of the deviations of the job completion times from a given small common due date. For this NP-hard problem, they develop a branch-and-bound algorithm based on Lagrangean lower and upper bounds that are found in O(nlogn) time. The authors identify conditions under which the bounds concur; these conditions can be expected to be satisfied by many instances with n not too small. In the present experiments with processing times drawn from a uniform distribution, the bounds concur for n≥40. For the case where the bounds do not concur, the authors present a refined lower bound that is obtained by solving a subset-sum problem of small dimension to optimality. They further develop a 4/3-approximation algorithm based upon the Lagrangean upper bound.

Reviews

Required fields are marked *. Your email address will not be published.