Complexity and Solutions of Some Three-Stage Flow Shop Scheduling Problems

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.