Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3 — Algorithm DP1 computes the minimum makespan of an on-time batch schedule, and ∞\infty∞ when none exists

Proved
BurnInBatch.ReleaseTmax.dp1_correct

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

batch-processingdynamic-programmingp2o-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​, indexed so that

d1≤⋯≤dnandr1≤⋯≤rn.d_1 \le \dots \le d_n \quad\text{and}\quad r_1 \le \dots \le r_n .d1​≤⋯≤dn​andr1​≤⋯≤rn​.

Let fff be the value of Algorithm DP1. Then for every 0≤j≤n0 \le j \le n0≤j≤n,

f(j)=min⁡{ Cmax⁡(S)  :  S a batch schedule of jobs 1,…,j with Ci≤di for all i≤j },f(j) = \min\bigl\{\, C_{\max}(S) \;:\; S \text{ a batch schedule of jobs } 1, \dots, j \text{ with } C_i \le d_i \text{ for all } i \le j \,\bigr\},f(j)=min{Cmax​(S):S a batch schedule of jobs 1,…,j with Ci​≤di​ for all i≤j},

with the minimum of the empty set equal to ∞\infty∞. That is, f(j)f(j)f(j) is finite exactly when jobs 1,…,j1, \dots, j1,…,j can be scheduled with no tardy job, and then it is the minimum makespan of such a schedule; the minimum ranges over all batch schedules (any batching, any order). For j=nj = nj=n this is the paper's claim that DP1 "will find a feasible schedule with minimum makespan if a feasible schedule exists".

The result solves the feasibility version of 1/ri,pi=p,B/Tmax⁡1/r_i, p_i = p, B/T_{\max}1/ri​,pi​=p,B/Tmax​, and with due dates shifted by a trial value of Tmax⁡T_{\max}Tmax​ it is the subroutine of the bisection procedure for minimizing Tmax⁡T_{\max}Tmax​.

Formalization Note The paper's "jobs are indexed in increasing order of due dates" is formalized as an index order nondecreasing in both ddd and rrr; DP1 uses rjr_jrj​ as the release time of the batch {i,…,j}\{i, \dots, j\}{i,…,j}, and with ties in ddd ordered against rrr the claim is false (two jobs, B=2B = 2B=2, p=1p = 1p=1, d=(2,2)d = (2,2)d=(2,2), r=(1,0)r = (1,0)r=(1,0): f(2)=1f(2) = 1f(2)=1, optimum 222). This index order exists whenever release times and due dates are agreeable, and implies agreeability. The minimum is an infimum in N∞\mathbb N_\inftyN∞​, where the infimum of the empty set is ⊤=∞\top = \infty⊤=∞. The paper's remark "if f(j)≤djf(j) \le d_jf(j)≤dj​ … none are tardy" is not part of the statement. The O(nB)O(nB)O(nB) running time is not formalized.

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

/-- Correctness of Algorithm DP1 (§3, p. 768). One batch machine of capacity `B ≥ 1`, `n` jobs
with common processing time `p`, release times `r` and due dates `d`, indexed so that both `d`
and `r` are nondecreasing. For every prefix length `j ≤ n`, the DP1 value `f(j)` equals the
minimum makespan over all batch schedules of jobs `1, …, j` in which every job is on time, and
it is `⊤ = ∞` exactly when there is no such schedule (an infimum over the empty set in `ℕ∞`). -/
theorem dp1_correct {n : ℕ} (B p : ℕ) (r d : Fin n → ℕ) (hB : 0 < B)
    (hd : Monotone d) (hr : Monotone r) (j : ℕ) (hj : j ≤ n) :
    dp1 B p r d j =
      ⨅ (S : List (Finset (Fin n)))
        (_ : IsBatchSchedule B (prefixJobs n j) S ∧ AllOnTime p r d (prefixJobs n j) S),
        (makespan p r 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. 768, §3 ("We can now state the dynamic programming algorithm DP1 which will find a feasible schedule with minimum makespan if a feasible schedule exists"), Algorithm DP1; p. 767, §3 ("will find the feasible sequence with minimum completion time if one exists")
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