  The non-preemptive job scheduling problem with release times and deadlines on
a single machine is fundamental to many scheduling problems. We parameterize
this problem by the set of job lengths the jobs can have. The case where all
job 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 in
which the short jobs have unit job length, which was already known to be
efficiently solvable. The proof uses a reduction from satisfiability to an
auxiliary scheduling problem that includes a set of paired jobs that each have
both an early and a late deadline, and of which at least one should be
scheduled before the early deadline. This reduction is enabled by not only
these pairwise dependencies between jobs, but also by dependencies introduced
by specifically constructed sets of jobs which have deadlines close to each
other. The auxiliary scheduling problem in its turn can be reduced to the
scheduling problem with two job lengths by representing each pair of jobs with
two deadlines by four different jobs.
