Unit Execution Time Shop Problems

The problem of preemptively (and nonpreemptively) scheduling a set of n independent jobs on an m machine open shop, flow shop or job shop is studied. It is shown that the problem of constructing optimal mean finishing time preemptive and nonpreemptive schedules is NP-hard. These problems are not only NP-hard in the strong sense, but remain NP-hard even when all nonzero tasks have identical execution time requirements. These results will also apply to the case when the problem is to construct an optimal finish time preemptive and nonpreemptive schedule for a flow shop or a job shop. We also discuss the problem of constructing no-wait schedules for these problems.