On the Complexity of Scheduling with Batch Setup Times

Clyde L. Monma and Chris N. Potts
Additional contact information
Clyde L. Monma: Bell Communications Research, Morristown, New Jersey
Chris N. Potts: University of Southampton, Southampton, England

Operations Research, 1989, vol. 37, issue 5, 798-804

Abstract: Many practical scheduling problems involve processing several batches of related jobs on common facilities where a setup time is incurred whenever there is a switch from processing a job in one batch to a job in another batch. We extend various scheduling models to include batch setup times. The models include the one-machine maximum lateness, total weighted completion time, and number of late jobs problems. In all these cases, a dynamic programming approach results in an algorithm that is polynomially bounded in the number of jobs, but is exponential in the number of batches. We also study the parallel machine model with preemption and show that the maximum completion time, maximum lateness, total weighted completion time, and number of late jobs problems are NP-hard, even for the case of two identical parallel machines, and sequence independent setup times.

Keywords: analysis of algorithms; dynamic programming; production/scheduling (search for similar items in EconPapers)
Date: 1989
References: Add references at CitEc
Citations: View citations in EconPapers (42)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.37.5.798 (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:37:y:1989:i:5:p:798-804

Access Statistics for this article

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