Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

p. 406 — LB(Jr)=∑Jrdi+max⁡(T^r,S^r)LB(J_r)=\sum_{J_r}d_i+\max(\hat T_r,\hat S_r)LB(Jr​)=∑Jr​​di​+max(T^r​,S^r​) is a lower bound on the sum of completion times

Proved
IgnallSchrage.MeanCompletion.lowerBound_le_totalCompletion

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

branch-and-boundflow-shoplower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling

Let 1≤r≤n−11\le r\le n-11≤r≤n−1 and let JrJ_rJr​ be a node. For every full sequence σ\sigmaσ that begins with JrJ_rJr​,

LB(Jr)=∑i∈Jrdi+max⁡(T^r,S^r) ≤ ∑i=1ndi(σ).LB(J_r)=\sum_{i\in J_r}d_i+\max(\hat T_r,\hat S_r)\ \le\ \sum_{i=1}^{n}d_i(\sigma).LB(Jr​)=i∈Jr​∑​di​+max(T^r​,S^r​) ≤ i=1∑n​di​(σ).

This is the property that lets the branch-and-bound procedure discard, implicitly, all sequences that begin with a node whose bound exceeds the value of a known complete sequence.

Formalization Note "LB(⋅)LB(\cdot)LB(⋅) is a lower bound" is read as: for every node with 1≤r≤n−11\le r\le n-11≤r≤n−1, and every one of the (n−r)!(n-r)!(n−r)! full sequences beginning with it, LBLBLB is at most its sum of completion times. The objective is the sum rather than the mean of the completion times; the two differ by the fixed factor 1/n1/n1/n.

Preamble
import Mathlib
import Definitions.Def_IgnallSchrage_MeanCompletion_LowerBound
Formal statement
namespace IgnallSchrage.MeanCompletion

/-- p. 406: for a node `J = J_r` with `1 ≤ r ≤ n - 1`,
`LB(J_r) = Σ_{i ∈ J_r} d_i + max(T̂_r, Ŝ_r)` is at most the sum of the completion times of
every full sequence that begins with `J_r`. -/
theorem lowerBound_le_totalCompletion {n : ℕ} (a b : Fin n → ℝ) (J : List (Fin n))
    (hr : 1 ≤ J.length) (hrn : J.length < n) (σ : Equiv.Perm (Fin n)) (hσ : IgnallSchrage.Makespan.BeginsWith σ J) :
    lowerBound a b J ≤ totalCompletion a b σ := by sorry

end IgnallSchrage.MeanCompletion
Source
Ignall and Schrage, Application of the branch and bound technique to some flow-shop scheduling problems, Oper. Res. 13 (1965), p. 406, "Therefore, LB(J_r)=Σ_{i∈J_r} d_i+max(T̂_r, Ŝ_r) and LB(·) is a lower bound"
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