Single-Machine Scheduling with Release Dates, Due Dates and Family Setup Times

J. M. J. Schutten, S. L. van de Velde and W. H. M. Zijm
Additional contact information
J. M. J. Schutten: Faculty of Mechanical Engineering, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands
S. L. van de Velde: Faculty of Mechanical Engineering, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands
W. H. M. Zijm: Faculty of Mechanical Engineering, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands

Management Science, 1996, vol. 42, issue 8, 1165-1174

Abstract: We address the NP-hard problem of scheduling n independent jobs with release dates, due dates, and family setup times on a single machine to minimize the maximum lateness. This problem arises from the constant tug-of-war going on in manufacturing between efficient production and delivery performance, between maximizing machine utilization by batching similar jobs and maximizing customers' satisfaction by completing jobs before their due dates. We develop a branch-and-bound algorithm, and our computational results show that it solves almost all instances with up to about 40 jobs to optimality. The main algorithmic contribution is our lower bounding strategy to deal with family setup times. The key idea is to see a setup time as a setup job with a specific processing time, release date, due date, and precedence relations. We develop several sufficient conditions to derive setup jobs. We specify their parameters and precedence relations such that the optimal solution value of the modified problem obtained by ignoring the setup times, not the setup jobs, is no larger than the optimal solution value of the original problem. One lower bound for the modified problem proceeds by allowing preemption. Due to the agreeable precedence structure, the preemptive problem is solvable in O(n log n) time.

Keywords: scheduling; maximum lateness; family setup times; branch-and-bound; setup jobs; preemption (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.42.8.1165 (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:ormnsc:v:42:y:1996:i:8:p:1165-1174

Access Statistics for this article

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