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.