Article ID: | iaor199787 |
Country: | Netherlands |
Volume: | 70 |
Issue: | 3 |
Start Page Number: | 350 |
End Page Number: | 364 |
Publication Date: | Nov 1993 |
Journal: | European Journal of Operational Research |
Authors: | Sriskandarajah C., Kamoun H. |
The authors study the problem of finding cyclic schedules in the flowshop, openshop and jobshop where jobs are processed in a repetitive cycle. Three types of cyclic scheduling problems are considered: The no-wait problem maximizes the throughput rate subject to the constraint that the jobs must be processed, from their start to their completion, without anyinterruption on or between machines; the minimum-wait problem minimizes the average work-in-process inventory of partially finished jobs subject to the constraint that the jobs have to be produced at the maximum throughput rate; the blocking problem maximizes the throughput rate subject to the constraint that the partially finished jobs cannot leave the machine where they are processed unless a downstream buffer space or machine is available. The authors show that the problem of finding maximum throughput schedules is NP-hard for no-wait flowshops with two machine centers having one or more parallel machines. The blocking problem in the three machine flowshop is shown to be NP-hard. All the aove problems in two-machine openshop and jobshop are also shown to be NP-hard even if each job has only two tasks. Some results are deduced with the present work and with those reported earlier.