NP-complete scheduling problems

摘要

We show that the problem of finding an optimal schedule for a set of jobs is NP-complete even in the following two restricted cases.o(1)All jobs require one time unit.(2)All jobs require one or two time units, and there are only two processor resolving (in the negative a conjecture of R. L. Graham, Proc. SJCC, 1972, pp. 205–218).As a consequence, the general preemptive scheduling problem is also NP-complete.These results are tantamount to showing that the scheduling problems mentioned are intractable.