Preemptive hybrid flowshop scheduling problem of interval orders

The Preemptive Hybrid (multi-processor) Flowshop Scheduling (PHFS) problem consists in preemptively scheduling n jobs in a flowshop subject to precedence constraints with the objective of minimizing the makespan. A special case of the general precedence constraints problems is NP-hard in the strong sense. In this paper a class of precedence constraints is proposed for which the problem is polynomially solvable. The reported results demonstrate the feasibility and reliability of the proposed approach. This should open future prospects for developing approximation algorithms for any class of precedence constraints.