New Lower and Upper Bounds for Scheduling Around a Small Common Due Date

J. A. Hoogeveen, H. Oosterhout and S. L. van de Velde
Additional contact information
J. A. Hoogeveen: Eindhoven University of Technology, Eindhoven, The Netherlands
H. Oosterhout: Tilburg University, Tilburg, The Netherlands
S. L. van de Velde: University of Twente, Enschede, The Netherlands

Operations Research, 1994, vol. 42, issue 1, 102-110

Abstract: We 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, we develop a branch-and-bound algorithm based on Lagrangian lower and upper bounds that are found in O ( n log n ) time. We identify conditions under which the bounds concur; these conditions can be expected to be satisfied by many instances with n not too small. In our experiments with processing times drawn from a uniform distribution, the bounds concur for n ≥ 40. For the case where the bounds do not concur, we present a refined lower bound that is obtained by solving a subset-sum problem of small dimension to optimality. We further develop a 4/3-approximation algorithm based upon the Lagrangian upper bound.

Keywords: production/scheduling: one-machine scheduling problem; programming: Lagrangian relaxation (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.1.102 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:42:y:1994:i:1:p:102-110

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().