Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2 — some schedule has Tmax⁡≤(n−1)pT_{\max} \le (n-1)pTmax​≤(n−1)p (assuming rj+p≤djr_j + p \le d_jrj​+p≤dj​)

Proved
BurnInBatch.ReleaseTmax.lemma_2

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

batch-processingmaximum-tardinessp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling

Consider one batch machine of capacity B≥1B \ge 1B≥1 and nnn jobs with common processing time ppp, release times rir_iri​ and due dates did_idi​ that are agreeable (ri<rjr_i < r_jri​<rj​ implies di≤djd_i \le d_jdi​≤dj​), and assume that every job can meet its due date if it is started at its release time:

rj+p≤dj(j=1,…,n).r_j + p \le d_j \qquad (j = 1, \dots, n).rj​+p≤dj​(j=1,…,n).

Then some batch schedule of all nnn jobs has maximum tardiness

Tmax⁡=max⁡jmax⁡{0,Cj−dj}≤(n−1)p.T_{\max} = \max_j \max\{0, C_j - d_j\} \le (n-1)p .Tmax​=jmax​max{0,Cj​−dj​}≤(n−1)p.

The lemma supplies the upper end of the search interval for the bisection on Tmax⁡T_{\max}Tmax​ (Algorithm 1).

Formalization Note The hypothesis rj+p≤djr_j + p \le d_jrj​+p≤dj​ is not in the printed statement of Lemma 2; its proof says "Since by assumption rj+p<djr_j + p < d_jrj​+p<dj​", and the lemma is false without it (one job with r=d=0r = d = 0r=d=0, p=1p = 1p=1 has Tmax⁡=1>0=(n−1)pT_{\max} = 1 > 0 = (n-1)pTmax​=1>0=(n−1)p). The weak inequality used here is a weaker hypothesis than the strict one of the proof. "An upper bound on the value of Tmax⁡T_{\max}Tmax​" is read as a bound on the optimal value: some schedule achieves it, not every schedule. Agreeability is in the paper's statement and is kept. The time bound of Corollary 1 is not formalized.

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

/-- Lemma 2 (p. 769), with the assumption `r_j + p ≤ d_j` of its proof. One batch machine of
capacity `B ≥ 1`, `n` jobs with common processing time `p`, agreeable release times and due
dates, and `r_j + p ≤ d_j` for every job. Then some batch schedule of all `n` jobs has maximum
tardiness at most `(n − 1)p`. -/
theorem lemma_2 {n : ℕ} (B p : ℕ) (r d : Fin n → ℕ) (hB : 0 < B)
    (hagree : ∀ i j : Fin n, r i < r j → d i ≤ d j)
    (hrd : ∀ j : Fin n, r j + p ≤ d j) :
    ∃ S : List (Finset (Fin n)),
      IsBatchSchedule B Finset.univ S ∧ tmax p r d Finset.univ S ≤ (n - 1) * p := by sorry

end BurnInBatch.ReleaseTmax
Source
Lee, Uzsoy & Martin-Vega, Efficient Algorithms for Scheduling Semiconductor Burn-In Operations, Oper. Res. 40(4) (1992), p. 769, Lemma 2 and its proof ("by assumption r_j + p < d_j")
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