Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3, justification of DP1 — some minimum-makespan on-time schedule has consecutive batches

Proved
BurnInBatch.ReleaseTmax.consecutive_batches

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

batch-processingconsecutive-partitionp2o-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≤d2≤⋯≤dnandr1≤r2≤⋯≤rn.d_1 \le d_2 \le \dots \le d_n \quad\text{and}\quad r_1 \le r_2 \le \dots \le r_n .d1​≤d2​≤⋯≤dn​andr1​≤r2​≤⋯≤rn​.

Fix 0≤j≤n0 \le j \le n0≤j≤n and let SSS be a batch schedule of jobs 1,…,j1, \dots, j1,…,j in which every job is on time. Then there is a batch schedule S′S'S′ of jobs 1,…,j1, \dots, j1,…,j in which every job is on time, every batch consists of consecutively indexed jobs {i,i+1,…,k}\{i, i+1, \dots, k\}{i,i+1,…,k} (at most BBB of them), the batches appear in increasing index order, and

Cmax⁡(S′)≤Cmax⁡(S).C_{\max}(S') \le C_{\max}(S).Cmax​(S′)≤Cmax​(S).

In particular, if an on-time schedule of jobs 1,…,j1, \dots, j1,…,j exists, some on-time schedule of minimum makespan is a consecutive partition of 1,…,j1, \dots, j1,…,j into blocks of at most BBB jobs. This is the claim that turns the problem into the consecutive partition problem solved by Algorithm DP1.

Formalization Note The paper assumes that the jobs are indexed in increasing order of due dates. Here the index order is nondecreasing in both ddd and rrr: with ties in ddd ordered against rrr the claim fails (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): the consecutive DP value is 111 but no schedule finishes before 222). Such an indexing exists whenever release times and due dates are agreeable (sort by (d,r)(d, r)(d,r)), and the two monotonicity conditions imply strict-form agreeability. The makespan clause is the content of the proof of Lemma 1 ("the completion times of the batches after the exchange … will not be greater"), which the justification of DP1 relies on.

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

/-- Justification of DP1 (§3, p. 768): with the jobs indexed in nondecreasing order of due dates
and of release times, every on-time batch schedule `S` of the first `j` jobs can be replaced by
an on-time batch schedule `S'` of the same jobs whose batches are blocks of consecutively indexed
jobs (at most `B` each, as in every batch schedule), in increasing index order, with makespan no
larger than that of `S`. -/
theorem consecutive_batches {n : ℕ} (B p : ℕ) (r d : Fin n → ℕ) (hB : 0 < B)
    (hd : Monotone d) (hr : Monotone r) (j : ℕ) (hj : j ≤ n)
    (S : List (Finset (Fin n))) (hS : IsBatchSchedule B (prefixJobs n j) S)
    (hon : AllOnTime p r d (prefixJobs n j) S) :
    ∃ S' : List (Finset (Fin n)),
      IsBatchSchedule B (prefixJobs n j) S' ∧ AllOnTime p r d (prefixJobs n j) S' ∧
      IsConsecutive S' ∧ makespan p r 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, justification of DP1 ("To justify DP1, note that each batch will contain no more than B consecutively indexed jobs …")
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