Lemma (Jackson) — a schedule with no late jobs exists iff every due-date ordering has none

Let $J$ be a finite set of jobs with processing times $t_j\ge0$ and due-dates $D_j\in\mathbb R\cup\{\pm\infty\}$, processed on one machine starting at time $0$. Then

This is Jackson's lemma as used by Moore: the due-date (earliest-due-date) schedule decides feasibility. In the section on maximum deferral cost it is applied with the due-dates $D_i=P_i^*(y)$, some of which are $0$ or $+\infty$.

Formalization Note Two changes relative to the page, both generalizations. (i) Due-dates are extended reals; real due-dates, the page's setting, embed. (ii) The paper's standing assumption $t_i\le D_i$ (p. 102) is not assumed: the deferral-cost problem has no given due-dates, and the lemma holds without it. The hypothesis $t_j\ge 0$ (processing times are durations) is added; the page never writes it, and the lemma is false for negative times. Ties among equal due-dates are arbitrary: the right-hand side quantifies over every due-date ordering.