Parallel Machine Scheduling with Batch Setup Times

T. C. E. Cheng and Z.-L. Chen
Additional contact information
T. C. E. Cheng: Hong Kong Polytechnic, Hung Horn, Kowloon, Hong Kong
Z.-L. Chen: Shanghai Transportation Planning Institute, Shanghai, People's Republic of China

Operations Research, 1994, vol. 42, issue 6, 1171-1174

Abstract: We consider a problem of scheduling several batches of jobs on two identical parallel machines to minimize the total completion time of jobs. A setup time is incurred whenever there is a switch from processing a job in one batch to a job in another batch. When the number of jobs is arbitrary, the computational complexity of the problem is posed as an open problem in the literature. We show in this note that the problem is binary NP-hard even when the setup times are sequence independent and all processing times are equal.

Keywords: analysis of algorithms; computational complexity: NP-hardness; production/scheduling: parallel machine scheduling (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.6.1171 (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:6:p:1171-1174

Access Statistics for this article

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