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

abstract

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

authors

• Sriskandarajah, Chelliah

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

publisher

• Elsevier  Publisher

published in

• European Journal of Operational Research  Journal

Digital Object Identifier (DOI)

• 10.1016/0377-2217(86)90036-6

start page

• 424

end page

• 438

volume

• 24

issue

• 3