Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3 — with agreeable processing times and due dates, a schedule with Tmax⁡=0T_{\max}=0Tmax​=0 can be taken in batch-EDD order

Proved
BurnInBatch.AgreeTmax.lemma_3

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

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

Consider nnn jobs on a single batch processing machine of capacity B≥1B\ge 1B≥1, all available at time 000, with processing times pip_ipi​ and due dates did_idi​ that are agreeable: pi<pjp_i<p_jpi​<pj​ implies di≤djd_i\le d_jdi​≤dj​. A batch takes the processing time of its longest job, and batches run back to back.

If some batch schedule of all nnn jobs has maximum tardiness Tmax⁡=0T_{\max}=0Tmax​=0, then some batch schedule SSS of all nnn jobs has

Tmax⁡(S)=0andS is in batch-EDD order,T_{\max}(S)=0\quad\text{and}\quad S \text{ is in batch-EDD order,}Tmax​(S)=0andS is in batch-EDD order,

that is, whenever batch PPP is processed before batch QQQ, no i∈Pi\in Pi∈P, j∈Qj\in Qj∈Q have di>djd_i>d_jdi​>dj​.

This is the structural property that turns the search for a feasible schedule into a search over sequences ordered by due date, on which Algorithm DP2 is built.

Formalization Note The paper states agreeability as "pi≤pjp_i\le p_jpi​≤pj​ implies di≤djd_i\le d_jdi​≤dj​"; the hypothesis here is the strict form pi<pj⇒di≤djp_i<p_j\Rightarrow d_i\le d_jpi​<pj​⇒di​≤dj​, which is weaker, so this statement implies the printed lemma. No indexing assumption is needed.

Preamble
import Mathlib
import Definitions.Def_BurnInBatch_AgreeTmax_Model
Formal statement
namespace BurnInBatch.AgreeTmax

/-- Lemma 3 of Lee, Uzsoy & Martin-Vega (1992), p. 769: in `1/B/T_max` with agreeable processing
times and due dates (strict form `p i < p j → d i ≤ d j`), if some valid batch schedule of all `n`
jobs has `T_max = 0`, then some valid batch schedule with `T_max = 0` is in batch-EDD order. -/
theorem lemma_3 {n B : ℕ} (hB : 0 < B) (p d : Fin n → ℕ) (hagr : Agreeable p d)
    (hfeas : ∃ S : List (Finset (Fin n)), IsValid B Finset.univ S ∧ Tmax p d S = 0) :
    ∃ S : List (Finset (Fin n)), IsValid B Finset.univ S ∧ Tmax p d S = 0 ∧ IsBatchEDD d S := by sorry

end BurnInBatch.AgreeTmax
Source
Lee, Uzsoy & Martin-Vega, Efficient Algorithms for Scheduling Semiconductor Burn-In Operations, Oper. Res. 40(4) (1992), p. 769, Lemma 3
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