Lemma 2.4 — the shifted parallel inequalities (2.3) and their equality case

Let $n$ jobs have integral processing times $p_j > 0$ and integral release dates $r_j \ge 0$. Let $(A_j)_j$ be any preemptive schedule, with mean busy times $M_j = \frac{1}{p_j}\int_{A_j} t\,dt$, and let $S$ be a nonempty set of jobs, with $p(S) = \sum_{j\in S} p_j$ and $r_{\min}(S) = \min_{j \in S} r_j$. Then

and equality holds if and only if the jobs of $S$ occupy the machine without interruption from $r_{\min}(S)$ to $r_{\min}(S) + p(S)$, that is, $\bigcup_{j \in S} A_j$ coincides with $[r_{\min}(S), r_{\min}(S) + p(S))$ up to a set of measure zero.

The inequality shows that the mean busy time vector of every preemptive schedule is feasible for (R), so $Z_R$ is a lower bound; the equality case is what makes the LP schedule's mean busy times attain it.

Formalization Note Processing sets are determined only up to null sets as far as $M_j$ is concerned, so "scheduled without interruption" is rendered as almost-everywhere equality of sets for Lebesgue measure. The paper's statement ranges over all sets $S$; for $S = \emptyset$ it is $0 \ge 0$ and $r_{\min}(\emptyset)$ is undefined, so $S$ is nonempty here.