The complexity of cyclic shop scheduling problems

We consider scheduling problems for shops in which a job set is manufactured repetitively. Jobs are scheduled to minimize the cycle time of the job set, which is equivalent to maximizing the throughput rate. We characterize the complexity of the scheduling problem for several types of job shops. Polynomial time algorithms are presented for open shops, and for job shops where each job has at most two operations. When there are two machines and the maximum number of operations of any job is a constant k greater than or equal to 3, the recognition version of the job shop problem is shown to be binary NP-complete. We describe a pseudopolynomial time algorithm for a special case of the problem when k = 3. We also establish that some generalizations of this problem are unary NP-complete. One consequence of these results is that the recognition version of the two machine job shop makespan problem with at most five operations per job is unary NP-complete. This resolves a question posed by Lenstra et al. (Ann. Discrete Math. 1977; 1:343). More generally, our results provide a map of the computational complexity of cycle time minimization problems that is analogous to that in the literature for makespan problems. Copyright (C) 2002 John Wiley Sons, Ltd.
Publisher
JOHN WILEY SONS LTD
Issue Date
2002
Language
ENG
Keywords

FLOW-SHOP; JOB SHOPS; BLOCKING

Citation

JOURNAL OF SCHEDULING, v.5, no.4, pp.307 - 327

ISSN
1094-6136
URI
http://hdl.handle.net/10203/3094
Appears in Collection
IE-Journal Papers(저널논문)
  • Hit : 894
  • Download : 48
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 22 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0