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.