Shop scheduling problems under precedence constraints

This paper considers a scheduling model that generalizes the well-known open shop, flow shop, and job shop models. For that model, called the super shop, the authors study the complexity of finding a time-optimal schedule in both preemptive and non-preemptive cases assuming that precedence constraints are imposed over the set of jobs. Two types of precedence relations are considered. Most of the arising problems are proved to be NP-hard, while for some of them polynomial-time algorithms are presented.