The complexity of scheduling jobs in repetitive manufacturing systems Academic Article uri icon


  • 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.

published proceedings

  • European Journal of Operational Research

author list (cited authors)

  • Kamoun, H., & Sriskandarajah, C.

citation count

  • 56

complete list of authors

  • Kamoun, H||Sriskandarajah, C

publication date

  • November 1993