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

• 成果类型: Article
• 署名作者: HOOGEVEEN, JA; OOSTERHOUT, H; VANDEVELDE, SL
• 署名单位: Tilburg University; University of Twente
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.42.1.102
• 发表日期: 1994
• 页码: 102-110
• 关键词: PRODUCTION SCHEDULING; ONE-MACHINE SCHEDULING PROBLEM; programming; Lagrangian relaxation

摘要

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 to small. In our experiments with processing times drawn 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 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.