SOME NO-WAIT SHOPS SCHEDULING PROBLEMS - COMPLEXITY ASPECT

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 centers where each machine center 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 is NP-hard. Also we establish NP-hard results for 3-machine jobshops for both optimal finish time and mean flow time schedules.