The due-date schedule $S_D(y^*)$ has minimal maximum deferral cost

Let $J$ be a nonempty finite set of jobs with processing times $t_j\ge 0$, processed on one machine from time $0$, and let each job have a continuous, bounded, non-decreasing deferral cost $P_j$, where $P_j(s)$ is the cost of completing $j$ at time $s$. For each $y>0$ let $S_D(y)$ be a schedule of $J$ ordered by non-decreasing due-dates $D_j=P_j^*(y)$ (ties broken arbitrarily). Let $y^*>0$ be such that

1. $S_D(y^*)$ has no late jobs, and
2. for all $0<y<y^*$, $S_D(y)$ has at least one late job.

Then for every schedule $S$ of $J$,

where $C_j^{S}$ is the completion time of $j$ in $S$: the schedule $S_D(y^*)$ has minimal maximum deferral cost.

This reduces the single-machine min–max deferral cost problem to a one-parameter family of due-date sorts, searched over the cost level $y$.

Formalization Note $y^*$ is given together with its two defining properties; its existence is the separate milestone exists_ystar. The minimum is over all schedules of $J$, not only over the $S_D(y)$. The family $y\mapsto S_D(y)$ is arbitrary subject to the ordering condition, so every tie-break is covered. "For all $y<y^*$" is read as $0<y<y^*$. Times are measured from $0$, and $P_j^*$ is computed over times $s\ge0$ (see the definition of $P^*$). $t_j\ge0$ is added (processing times are durations).