Article ID: | iaor20041571 |
Country: | United Kingdom |
Volume: | 5 |
Issue: | 4 |
Start Page Number: | 307 |
End Page Number: | 327 |
Publication Date: | Jul 2002 |
Journal: | Journal of Scheduling |
Authors: | Posner Marc E., Hall Nicholas G., Lee Tae-Eog |
Keywords: | production |
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