Canonical completion times form an interval without EDD
ProvedLawlerCompress.TardyJobs.lemma_2_1_without_EDDdynamic-programmingoperations-researchscheduling
Let be any instance of the weighted tardy-jobs scheduling problem and let be one of its jobs. Without assuming that the jobs are listed in earliest-due-date order, the canonical completion times of still form an interval: there is an endpoint with such that
ar C_j=\{a_j,a_j+1,\ldots,d_j\},with the convention that when ar C_j is empty. Here and are the processing time and due date of job , and ar C_j is the set of times at which belongs to the canonical high-priority set. The result follows from the nesting of the eligible job sets as the time threshold increases; the EDD hypothesis used elsewhere in the paper is not needed for this interval property.
Preamble
import Definitions.Def_LawlerCompress_TardyJobs_Canonical set_option autoImplicit false
Formal statement
namespace LawlerCompress.TardyJobs
theorem lemma_2_1_without_EDD {m : ℕ} (I : Instance m) (j : Fin I.n) :
I.p j ≤ a I j ∧ a I j ≤ I.d j + 1 ∧
cbar I j = Finset.Icc (a I j) (I.d j) ∧
(cbar I j = ∅ → a I j = I.d j + 1) := by sorry
end LawlerCompress.TardyJobs
Source
K. Jansen, B. Schumacher, and C. Wambsganz, Compressing the Lawler-Moore Dynamic Program for Weighted Tardy Jobs, STOC 2027 submission #354 (October 2026), §2, Lemma 2.1, p. 4. The source states the result in the surrounding EDD-ordered setting; this formal statement removes EDD because its proof uses only the nested eligible sets.