Scheduling with two non-unit task lengths is NP-complete (Not published)

The non-preemptive job scheduling problem with release times and deadlines ona single machine is fundamental to many scheduling problems. We parameterizethis problem by the set of job lengths the jobs can have. The case where alljob lengths are identical is known to be solvable in polynomial time. We prove that the problem with two job lengths is NP-complete, except for the case inwhich the short jobs have unit job length, which was already known to beefficiently solvable. The proof uses a reduction from satisfiability to anauxiliary scheduling problem that includes a set of paired jobs that each haveboth an early and a late deadline, and of which at least one should bescheduled before the early deadline. This reduction is enabled by not onlythese pairwise dependencies between jobs, but also by dependencies introducedby specifically constructed sets of jobs which have deadlines close to eachother. The auxiliary scheduling problem in its turn can be reduced to thescheduling problem with two job lengths by representing each pair of jobs withtwo deadlines by four different jobs.