Lemma 2.1 — (D) has an optimal $0/1$ solution

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) has an optimal solution with integral entries: there is a feasible $y^*$ with

such that $\sum_j w_j C_j(y^*) \le \sum_j w_j C_j(y)$ for every feasible $y$, where $C_j(\cdot)$ is given by (2.1).

The lemma reflects that, after eliminating $C_j$ with (2.1), (D) is a transportation problem. It is the starting point of the interchange argument for Theorem 2.2.

Formalization Note Optimality is stated directly (the solution attains the minimum over all feasible $y$), not through the value $Z_D$. The paper's standing assumption is $w_j > 0$; the statement is made for $w_j \ge 0$.