Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

FBEDD optimally solves 1/pi=p,B/Tmax⁡1/p_i=p,B/T_{\max}1/pi​=p,B/Tmax​

Proved
BurnInBatch.AgreeTmax.fbedd_optimal

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

batch-processingeddp2o-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, every job with the same processing time ppp, and due dates indexed so that d1≤d2≤⋯≤dnd_1\le d_2\le\dots\le d_nd1​≤d2​≤⋯≤dn​. Let SFBEDDS_{\mathrm{FBEDD}}SFBEDD​ be the Full-Batch EDD schedule: batches {1,…,B}\{1,\dots,B\}{1,…,B}, {B+1,…,2B}\{B+1,\dots,2B\}{B+1,…,2B}, …\dots…, processed in this order. Then SFBEDDS_{\mathrm{FBEDD}}SFBEDD​ is a valid batch schedule of all jobs, and for every valid batch schedule SSS of all jobs,

Tmax⁡(SFBEDD)≤Tmax⁡(S).T_{\max}(S_{\mathrm{FBEDD}})\le T_{\max}(S).Tmax​(SFBEDD​)≤Tmax​(S).

With equal processing times every batch takes time ppp, so the result says that filling batches in due-date order is optimal for maximum tardiness.

Formalization Note The common processing time is c∈Nc\in\mathbb Nc∈N (any value, 000 included). Tmax⁡T_{\max}Tmax​ is max⁡imax⁡{0,Ci−di}\max_i \max\{0, C_i-d_i\}maxi​max{0,Ci​−di​}, computed with truncated subtraction in N\mathbb NN.

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

/-- Algorithm FBEDD optimally solves `1/p_i = p, B/T_max` (Lee, Uzsoy & Martin-Vega 1992,
p. 769): if every job has processing time `c` and the jobs are indexed in nondecreasing order of
due dates, the full-batch EDD schedule is a valid batch schedule of all jobs, and its maximum
tardiness is at most that of every valid batch schedule of all jobs. -/
theorem fbedd_optimal {n B : ℕ} (hB : 0 < B) (c : ℕ) (d : Fin n → ℕ) (hd : Monotone d) :
    IsValid B Finset.univ (fbedd n B) ∧
      ∀ S : List (Finset (Fin n)), IsValid B Finset.univ S →
        Tmax (fun _ => c) d (fbedd n B) ≤ Tmax (fun _ => c) 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, Algorithm FBEDD and the sentence preceding it
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