THE COMPLEXITY OF SCHEDULING JOBS IN REPETITIVE MANUFACTURING SYSTEMS

We study the problem of finding cyclic schedules in the flowshop, open shop and jobshop where jobs are processed in a repetitive cycle. Three types of cyclic scheduling problems are considered: The no-wait probl em maximizes the throughput rate subject to the constraint that the jo bs must be processed, from their start to their completion, without an y interruption on or between machines; the minimum-wait problem minimi zes the average work-in-process inventory of partially finished jobs s ubject to the constraint that the jobs have to be produced at the maxi mum throughput rate; the blocking problem maximizes the throughput rat e subject to the constraint that the partially finished jobs cannot le ave the machine where they are processed unless a downstream buffer sp ace or machine is available. We show that the problem of finding maxim um throughput schedules is NP-hard for no-wait flowshops with two mach ine centers having one or more parallel machines. The blocking problem in the three machine flowshop is shown to be NP-hard. All the above p roblems in two-machine openshop and jobshop are also shown to be NP-ha rd even if each job has only two tasks. Some results are deduced with the present work and with those reported earlier.