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$.

For any two integer job lengths $p > q > 1$, the problem $\mathrm{AUX}(p, q)$ is NP-complete.

Hardness is by reduction from satisfiability of formulas in conjunctive normal form. A satisfying assignment yields a solution in which the sections of the false literals are delayed by one unit: every clause has a true literal, whose section is not delayed and whose clause block is active, and at that block the chain of connected pairs of the clause can switch from completing short jobs early to completing long jobs early. Conversely, in any solution every job runs inside its own block, one of the sections of $x_i$ and $\neg x_i$ is delayed for every $i$, and a chain of clause blocks can be scheduled only if it passes an active block in a section that is not delayed; setting the literals of the delayed sections to false satisfies the formula.

The assumption $q > 1$ is needed: one unit of delay must not leave room for a short job.

The instance of $\mathrm{AUX}(p, q)$ built from a formula in conjunctive normal form with $n$ variables and $m$ clauses $C_0, \dots, C_{m-1}$.

The time line is cut into $2n$ sections of equal length $S = (p + 2q) + m(p + q) + 1 + q$, one for every literal, in the order $x_0, \neg x_0, x_1, \neg x_1, \dots$ A section consists of a literal block of total job length $p + 2q$, then one clause block of total job length $p + q$ for every clause, then one unit of idle time, then a separator: an ordinary short job whose availability interval is exactly the last $q$ time units of the section.

Relative to the start of its section, the literal block of a positive literal, of type $V^+$, consists of the ordinary jobs $([1, 2q],\, q)$ and $([0,\, p + 2q + 1],\, q)$ and a long pending job with early deadline $p + q + 1$ and late deadline $p + 2q$. The block of a negative literal, of type $V^-$, consists of the ordinary jobs $([q + 1,\, p + q],\, q)$ and $([0,\, p + 2q + 1],\, p)$ and a short pending job with early deadline $q$ and late deadline $p + 2q$. In either block the pending job can complete early only at the price of one unit of idle time that no other job can fill.

Relative to the point $p + 2q + j(p + q)$ of its section, the clause block of the clause $C_j$ consists of a long and a short pending job, both with late deadline $p + q + 1$ and both with early deadline $p + q$ if the literal of the section occurs in $C_j$ — the block is then active — and $p + q - 1$ otherwise. Both jobs of an active block can complete early if the section has not been delayed; in a delayed section, or in an inactive block, only one of them can.

Pending jobs are connected as follows. The long pending job of the literal block of $x_i$ is connected with the short pending job of the literal block of $\neg x_i$. For every clause, the long pending job of its clause block in a section is connected with the short pending job of its clause block in the next section. This leaves the long pending jobs of the clause blocks of the last section and the short ones of the first section unconnected; they are required to meet their early deadline, which makes them ordinary jobs released at $0$.

A connected pair of literal blocks forces a delay of one unit in the section of $x_i$ or in that of $\neg x_i$; the literal whose section is not delayed is the one set to true. The chain of clause blocks of a clause through all sections can be scheduled only if the clause block is active in some section that is not delayed, that is, if the clause contains a true literal.

For any two integer job lengths $p > q \ge 1$, the problem $\mathrm{AUX}(p, q)$ is polynomial-time reducible to single machine scheduling with release times and deadlines on the job lengths $\{p, q\}$.

The reduction replaces every connected pair of pending jobs by the five jobs of the stacked construction. Its correctness is proved by an exchange argument: a feasible schedule of the stacked instance is rearranged, pair by pair in order of urgency, until every bin holds two jobs of its own pair, and the jobs left after time $0$ are then read as a solution of the auxiliary instance.

The scheduling instance built from an instance of $\mathrm{AUX}(p, q)$, in which the two deadlines of a pending job are expressed by ordinary availability intervals. The construction buys the second deadline with room on the time line before time $0$.

Let $w = q$ and let $t_i = -(p + q + w)\, i$ for $i = 1, \dots, N$. For every connected pair $i$ the instance contains five jobs:

• a separator with availability interval $[t_i + p + q,\; t_i + p + q + w]$ and length $w$, which is thereby pinned in place;
• an inner long job $([t_i + q,\; d'_{p,i}],\, p)$ and an outer long job $([t_i,\; d_{p,i}],\, p)$;
• an inner short job $([t_i + p,\; d'_{q,i}],\, q)$ and an outer short job $([t_i,\; d_{q,i}],\, q)$.

The ordinary jobs are kept unchanged. The separators cut the time before $0$ into $N$ bins $[t_i,\, t_i + p + q)$, each with room for exactly one long and one short job. The availability intervals of the four jobs of a pair are nested, the inner ones carrying the early deadlines. A feasible schedule parks two jobs of each pair in its bin and runs the other two, one long and one short, after time $0$. The inner long job and the inner short job of a pair do not fit into its bin together, so one of the two jobs running after $0$ is an inner job and meets an early deadline — the condition on connected pairs.

An instance has a feasible schedule with real start times if and only if it has one with integer start times. Rounding every start time up to the next integer preserves feasibility, because release times, deadlines and processing times are integers.