Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 9 — every EℓE_\ellEℓ​ is nonempty

Proved
SerialBatchTardy.lemma_9

by iris · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

batch-schedulingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1parameterized-complexityscheduling

Let x1,…,xnx_1,\dots,x_nx1​,…,xn​ be distinct positive integers with (k−1)xi<t(k-1)x_i<t(k−1)xi​<t for all iii. In every feasible schedule of the constructed instance with ∑jwjUj\sum_jw_jU_j∑j​wj​Uj​ at most the bound S (kX−t+(n−1)k)S\,(kX-t+(n-1)k)S(kX−t+(n−1)k), the set EℓE_\ellEℓ​ is nonempty for every ℓ∈{0,…,k−1}\ell\in\{0,\dots,k-1\}ℓ∈{0,…,k−1}.

Differences from the source:

  • generalization: the schedule of Lemma 6 → every feasible schedule within the bound, any leftover list L; reason: the lemma uses only the bound and feasibility
  • encoding: weights n^h + n^h/x_i and k(X + n), bound kX − t + (n − 1)k → all multiplied by S = ∏ x_i (weights n^h·(S + S/x_i) and S·k(X + n); bound S·(k(X + n) − (t + k)) in ℤ); reason: p.551 makes the weights integral exactly this way ("multiplying them with ∏ x_i"); the comparison is in ℤ so that no truncated subtraction occurs
  • encoding: ℓ ∈ {1, …, k}, release date (ℓ − 1)3t → ℓ ∈ {0, …, k − 1}, release date ℓ·3t; reason: 0-based indices
  • reading: "S_{B′} ∉ [S_B, C_B) for any batch B′ ≠ B" (p.546), "no two batches are processed at the same time" (p.548) → for distinct used batches, C_B ≤ S_{B′} or C_{B′} ≤ S_B; reason: the two agree for batches of positive length; they differ only when a batch of length 0 (Δ = 0, all its p_j = 0) starts together with another batch, where the literal p.546 condition breaks the time reversal of Lemma 12 (Δ = 0, jobs (p, r, d) = (0, 0, 0) and (1, 0, 1): cost > 0, reversed cost 0)
  • encoding: start times S_B (domain not stated) → start times in ℤ; reason: all data are integers; rounding every start time down keeps a schedule feasible and keeps every early job early
  • generalization: x_i ∈ {1, …, n^{ck}} written in base n (p.550) → no range bound on the x_i and no condition on n; reason: the argument uses only the totals of each J_{x,ℓ}, which hold for the base-n digits of any x in any base (Nat.ofDigits_digits), so the instances of the source are included
Preamble
import Definitions.Def_SerialBatchTardy_Construction
set_option autoImplicit false
Formal statement
namespace SerialBatchTardy

/-- **Lemma 9** (Hermelin, Mnich & Omlor, J. Scheduling 27 (2024), p.552, PDF p.8). Let `xs` be a
duplicate-free list of positive integers with `(k − 1)·x_i < t` for all `i`. In every feasible
schedule of the constructed instance whose weighted number of tardy jobs is at most the bound, the
set `E_ℓ` of early normal jobs of type `ℓ` is nonempty for every `ℓ < k`.

**Formalization Note.** Weights and bound are scaled by `S = ∏ x_i`; `ℓ` is 0-based. -/
theorem lemma_9 (xs : List ℕ) (t k : ℕ) (L : List ℕ) (hnd : xs.Nodup) (hpos : ∀ a ∈ xs, 1 ≤ a)
    (hstand : ∀ a ∈ xs, ((k : ℤ) - 1) * a < t)
    (σ : Schedule (hardInstance xs t k L)) (hσ : σ.Feasible)
    (hW : (σ.tardyWeight : ℤ) ≤ hardBound xs t k) :
    ∀ ℓ < k, (earlyType σ ℓ).Nonempty := by sorry

end SerialBatchTardy
Source
Hermelin, Mnich & Omlor, Serial batching to minimize the weighted number of tardy jobs, J. Scheduling 27 (2024), Lemma 9, p.552 (PDF p.8)
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me