Some no-wait shops scheduling problems: Complexity aspect Academic Article uri icon


  • We investigate the computational complexity of no-wait shops scheduling problems. The problem of finding optimal finish time schedules is shown to be NP-hard for flowshops with two machine centres where each machine centre has one or more parallel machines for processing tasks. The complexity results are also reported for no-wait shops scheduling when all nonzero tasks have unit or identical processing time requirement. A polynomial time algorithm for 3-machine flowshops is proposed for optimal finish time schedules. Finding optimal finish time schedules in 2-machine jobshops in NP-hard. Also we establish NP-hard results for 3-machine jobshops for both optimal finish time and mean flow time schedules. Some results are deduced with the present work and with those reported earlier. 1986.

published proceedings

  • European Journal of Operational Research

author list (cited authors)

  • Sriskandarajah, C., & Ladet, P.

citation count

  • 72

complete list of authors

  • Sriskandarajah, Chelliah||Ladet, Pierre

publication date

  • March 1986