Some no-wait shops scheduling problems: Complexity aspect
Academic Article
-
- Overview
-
- Identity
-
- Additional Document Info
-
- View All
-
Overview
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.
author list (cited authors)
-
Sriskandarajah, C., & Ladet, P.
citation count
complete list of authors
-
Sriskandarajah, Chelliah||Ladet, Pierre
publication date
publisher
published in
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue