Complexity and Solutions of Some Three-Stage Flow Shop Scheduling Problems
- 1 November 1982
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 7 (4) , 532-544
- https://doi.org/10.1287/moor.7.4.532
Abstract
It is well known that the minimal length non-preemptive scheduling problem for the general three-stage flow shop is NP-complete. This paper presents a study of a special type of flow shop in which a particular stage of each job is the longest (or the shortest as the case may be). In most cases, it is found that the problem remains strongly NP-complete. In other cases, polynomial scheduling algorithms are presented.Keywords
This publication has 0 references indexed in Scilit: