Let $p > q > 1$ be two integer job lengths. Single machine scheduling with release times and deadlines, restricted to instances whose processing times all lie in $\{p, q\}$, is NP-complete.

Hardness is obtained by composing the reduction from satisfiability to the auxiliary problem $\mathrm{AUX}(p, q)$ with the reduction from the auxiliary problem to scheduling on the lengths $\{p, q\}$. Since $p$ and $q$ are constants, every number of the constructed instance is bounded by a polynomial in the size of the formula, so the source concludes that the problem is even strongly NP-complete. The two bounds are stated as $SatConstruction.times_le$ and $StackedConstruction.times_le$; strong NP-completeness itself, which would need a unary encoding of the instance, is not stated here.

The cases left out are polynomial-time solvable: a single job length, and two job lengths of which the shorter is $1$.