Lemma 2.1 — Canonical completion times form an interval
ProvedLawlerCompress.TardyJobs.lemma_2_1dynamic-programmingoperations-researchp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let I be an EDD instance on m≥1 machines with n≥1 jobs. For every input job j, the canonical endpoint a_j satisfies
Here priority is weight followed by larger index, and a_j is computed as the least canonical time with the stated empty-set default. This identifies the interval that the later algorithm enumerates.
Formalization Note The endpoint is a shared definition, not an arbitrary witness chosen separately in each theorem.
Differences from the source:
- encoding: jobs and machines numbered from one; positive integral data; a nonempty input with a maximum due date → Fin n jobs and Fin m machines, natural data in Instance, with m,n ≥ 1; reason: zero-based reindexing preserves every schedule and excludes only the undefined empty maximum
Preamble
import Definitions.Def_LawlerCompress_TardyJobs_Canonical set_option autoImplicit false
Formal statement
namespace LawlerCompress.TardyJobs
theorem lemma_2_1 {m : ℕ} (hm : 1 ≤ m) (I : Instance m)
(hn : 1 ≤ I.n) (hedd : EDD I) (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
Klaus Jansen, Björn Schumacher, Corinna Wambsganz, Compressing the Lawler-Moore Dynamic Program for Weighted Tardy Jobs, STOC 2027 submission #354 (October 2026), p. 4, Lemma 2.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.