An instance consists of $n$ jobs and $m$ identical second-stage machines. Job $j$ has a preprocessing time $p_j \in \mathbb{N}$, a processing time $q_j \in \mathbb{N}$, a due date $d_j \in \mathbb{N}$ and a weight $w_j \in \mathbb{N}$. It is run in two operations, in this order and without preemption: a preprocessing operation of length $p_j$ on the single first-stage machine, and a processing operation of length $q_j$ on one of the $m$ identical second-stage machines. Job $j$ is completed just in time when its second operation finishes exactly at $d_j$, and the objective is to maximize the total weight of the just-in-time jobs. In the three-field notation the problem is $FF(1,m) \mid\mid \sum_j w_j Z_j$.

Just-in-time completion pins the second operation of $j$ to the interval $[s_j, d_j)$, where $s_j = d_j - q_j$; the first operation must therefore be finished by $s_j$, which acts as a deadline for it. Two jobs conflict when those two intervals overlap, and conflicting jobs cannot share a second-stage machine.

Since the objective counts only the just-in-time jobs, a solution is the set $Z$ of jobs completed just in time, and $Z$ is feasible when its jobs — and no others — admit a schedule completing every one of them exactly at its due date.

Two standing conventions of the paper's algorithmic sections, and the rescaling that establishes the second.

An instance is in earliest-start-time order when its jobs are numbered so that the start times $s_1 \le \dots \le s_n$ are nondecreasing. Every algorithm of the paper begins by sorting the jobs this way, and its tables are indexed by the resulting order.

The endpoints of an instance are the $2n$ numbers $s_j$ and $d_j$. They are distinct when no two of them coincide. Section 4 assumes this, and obtains it by the rescaling

which leaves the weights alone.

Two conditions on a set $Z$ of jobs, one for each stage of the shop.

Condition 1, $Z$ can be preprocessed in time: for every $j \in Z$, the jobs of $Z$ whose second operations start no later than $j$'s fit, together, into $[0, s_j)$.

Condition 2, $Z$ can be scheduled on $m$ machines: the jobs of $Z$ can be partitioned into $m$ sets, no one of which contains two conflicting jobs.

An instance is handed to a word random access machine as a word of numbers: the number $n$ of jobs, the number $m$ of machines, then the $n$ preprocessing times, the $n$ processing times, the $n$ due dates and the $n$ weights, in that order. A decision instance appends the threshold $W$ as a final entry.

An instance as a binary word, the representation against which classical complexity measures running time. A number is written as its binary digits preceded by their number in unary, which makes the encoding self-delimiting; an instance is the number of jobs, the number of machines, and then the four arrays of preprocessing times, processing times, due dates and weights, in that order.

The decision problem: given an encoded instance and a threshold $W$, is there a feasible set of jobs of total weight at least $W$? As a parameterized problem it is taken with the number $m$ of machines as its parameter, which is the parameterization of the paper's fourth corollary.

Four further quantities of an instance appear in the running times of the paper's algorithms and are defined here as functions of the word: the threshold $W$ itself, the largest processing time $q_{\max}$, the total preprocessing time $P$, and the width $\omega$ — the largest number of jobs whose second operations are alive at one instant.

The algorithm behind the second theorem. The jobs are in earliest-start-time order and are considered one at a time, from the last to the first. The state carried is a set $X$ of at most $m$ thresholds, one per second-stage machine: the smallest index a job on that machine may have. The table entry

is the earliest instant at which the first-stage machine may begin, if a set of jobs of total weight $W'$ compatible with $X$ is still to be preprocessed in time. It is $-\infty$ when no such set exists, and $+\infty$ when the empty set will do.

A set $Z$ is compatible with $X$ when each of its jobs can be assigned a threshold in $X$ not exceeding it, with no two conflicting jobs sharing a threshold. Taking $X$ to be the first $m$ indices asks for nothing beyond schedulability on $m$ machines, which is how the table is read off at the end.

The recursion removes the smallest threshold $j$ of $X$ and decides whether job $j$ is selected. If it is not, $j$ is replaced by the smallest index above it that is not already a threshold — the paper's $j_1$ — and the table is consulted at the resulting $X_1$. If it is, the weight drops by $w_j$ and the budget by $p_j$, and $j$ is replaced by the smallest index not already a threshold whose second operation starts at or after $d_j$ — the paper's $j_2$ — giving $X_2$.

The algorithm behind the first half of the third theorem. The time axis is swept from left to right through the $2n$ endpoints — the start times and the due dates — and the state carried at an instant $t$ is the set $X$ of selected jobs alive then, together with the weight selected so far and the preprocessing time spent. The table entry

records whether a feasible selection of weight $W'$, all of whose jobs have started by $t$, is alive at $t$ in exactly $X$ and costs at most $P'$ to preprocess.

Between two consecutive endpoints nothing happens, and at an endpoint exactly one thing does: a job becomes due, or a job starts. The two recursions of Section 4 say what each does to the table.

Since $X$ is a set of jobs alive at one instant, it has at most $\omega$ members, so the table has $2^\omega$ columns — which is where the running time comes from.

The algorithm behind the second half of the third theorem. It sweeps the start times in order, and at the start time of job $j$ it carries, instead of the set of selected jobs alive then, only their profile: the vector $\vec{x}$ whose $i$-th coordinate counts the selected jobs due at $s_j + i$. Since a job's second operation is at most $q_{\max}$ long, only the coordinates $1, \dots, q_{\max}$ can be nonzero, and each is at most $m$; the table therefore has $m^{q_{\max}}$ columns.

Stepping from the previous start time to $s_j$ moves the reference point by $\delta_j = s_j - s_{j-1}$, so a profile at $s_{j-1}$ becomes a profile at $s_j$ shifted down by $\delta_j$. The paper writes $\vec{x}[\delta]$ for the vectors that shift to $\vec{x}$, and recursion (5) has the two branches of every such sweep: job $j$ is passed over, or job $j$ is selected, in which case its own coordinate $q_j$ drops by one.