Corollary 2.6 — $Z_D = Z_R$ for all weights $w \ge 0$

Let $n$ jobs have integral processing times $p_j > 0$, integral release dates $r_j \ge 0$ and weights $w_j \ge 0$, and let the horizon $T \in \mathbb N$ bound the makespan of some feasible nonpreemptive schedule. Then the preemptive time-indexed relaxation (D) with horizon $T$ and the mean busy time relaxation (R) have the same optimal value:

Both are lower bounds on the optimum of $1\,|\,r_j\,|\,\sum w_j C_j$. The equality means that the pseudopolynomial LP (D) and the exponentially constrained LP (R) give the same bound, and that both are attained by the LP schedule; the approximation results of the paper are measured against this common value.

Formalization Note No ordering of the jobs is assumed: the statement holds for every nonnegative weight vector, and the LP schedule does not appear in it. The paper takes $T$ to be an upper bound on the makespan of an optimal schedule; here $T$ is only required to bound the makespan of some feasible nonpreemptive schedule (with real start times), which every such $T$ does, so the statement covers the paper's. The paper's second sentence, that the common value can be computed in $O(n \log n)$ time, is a running-time claim and is not formalized.