Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 — an on-time schedule can be rearranged into batch-EDD order

Proved
BurnInBatch.ReleaseTmax.lemma_1

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

batch-processingexchange-argumentp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling

Consider one batch machine of capacity BBB and nnn jobs with common processing time ppp, release times rir_iri​ and due dates did_idi​, where release times and due dates are agreeable: ri<rjr_i < r_jri​<rj​ implies di≤djd_i \le d_jdi​≤dj​.

If there is a batch schedule of all nnn jobs in which every job is on time (Tmax⁡=0T_{\max} = 0Tmax​=0), then there is a batch schedule of all nnn jobs in which every job is on time and the batches are in batch-EDD order: whenever batch PPP is processed before batch QQQ, no i∈Pi \in Pi∈P and j∈Qj \in Qj∈Q satisfy di>djd_i > d_jdi​>dj​.

The lemma is the exchange argument that makes the batches of an on-time schedule respect the due-date order; it is the first step toward the consecutive structure that Algorithm DP1 exploits.

Formalization Note The paper prints agreeability as "ri≤rjr_i \le r_jri​≤rj​ implies di≤djd_i \le d_jdi​≤dj​", which read literally forces equal due dates for equal release times. The strict form used here is a weaker hypothesis, so the Lean statement implies the printed one. Lemma 1 itself needs no assumption on the job indexing.

Preamble
import Mathlib
import Definitions.Def_BurnInBatch_ReleaseTmax_Model
Formal statement
namespace BurnInBatch.ReleaseTmax

/-- Lemma 1 (p. 767). One batch machine of capacity `B`, `n` jobs with common processing time
`p`, release times `r` and due dates `d` that are agreeable (`r_i < r_j → d_i ≤ d_j`). If some
batch schedule of all `n` jobs has every job on time (`T_max = 0`), then some batch schedule of
all `n` jobs has every job on time and is in batch-EDD order. -/
theorem lemma_1 {n : ℕ} (B p : ℕ) (r d : Fin n → ℕ)
    (hagree : ∀ i j : Fin n, r i < r j → d i ≤ d j)
    (hfeas : ∃ S : List (Finset (Fin n)),
      IsBatchSchedule B Finset.univ S ∧ AllOnTime p r d Finset.univ S) :
    ∃ S : List (Finset (Fin n)),
      IsBatchSchedule B Finset.univ S ∧ AllOnTime p r d Finset.univ S ∧ IsBatchEDD d S := by sorry

end BurnInBatch.ReleaseTmax
Source
Lee, Uzsoy & Martin-Vega, Efficient Algorithms for Scheduling Semiconductor Burn-In Operations, Oper. Res. 40(4) (1992), p. 767, Lemma 1 (with Definition 1)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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