Shop scheduling problems with multiprocessor tasks on dedicated processors

The computational complexity of shop scheduling problems with multiprocessor tasks on dedicated processors is investigated. The objective is makespan minimization. Preemption of tasks is not allowed. For open and flow-shop problems with three stages, complete classifications into polynomial solvable and Pn-hard problems are given. These classifications depend on the compatibility structures of the problems. Furthermore, results for open-shop problems with unit processing times are derived. Finally, it is shown that most of the special cases of the job-shop problem which are polynomially solvable remain polynomially solvable in the multiprocessor task situation.