Existence of the least feasible cost level $y^*$

Let $J$ be a finite set of jobs with processing times $t_j\ge 0$ and continuous non-decreasing deferral costs $P_j$. For each $y>0$ let $S_D(y)$ be a schedule of $J$ ordered by non-decreasing due-dates $D_j=P_j^*(y)$. Assume

1. some level $y_1>0$ has $S_D(y_1)$ without late jobs, and
2. some level $y_0>0$ has $S_D(y_0)$ with at least one late job.

Then there is $y^*>0$ such that

The level $y^*$ is the least cost level at which the due-date schedule is feasible; the main theorem shows that $S_D(y^*)$ minimizes the maximum deferral cost.

Formalization Note Hypothesis 1 is the paper's footnote 3, which replaces boundedness ("It is sufficient if there exists $y>0$ such that $S_D(y)$ has no late jobs"); this is the stronger of the paper's two versions, and the bounded version follows from the milestone bounded_exists_feasible_level. Hypothesis 2 is added: without it the statement is false (with all costs identically $0$, $P_j^*(y)=+\infty$ for every $y>0$, every $S_D(y)$ is on time, and no $y^*>0$ has the second property). "For all $y<y^*$" is read as $0<y<y^*$, because $S_D(y)$ is defined only for $y>0$. $t_j\ge 0$ is added.