The complexity of scheduling jobs in repetitive manufacturing systems

We 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 any interruption 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. We 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 above 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. 1993.

The complexity of scheduling jobs in repetitive manufacturing systems Academic Article