On the complexity of the process shop

The authors consider the problem of scheduling a two-stage processing system where each stage consists of a set of independent parallel processors. A job requires processing on a processor from each set and no-wait schedules are required. The authors show that this problem is hard for it generalizes jobshop and flowshop scheduling. This observation provides a new conceptual framework for process scheduling and allows several solvable special cases to be identified.