Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

pp. 405–406 — the sum of completion times over Jˉr\bar J_rJˉr​ is at least TrT_rTr​ of its order, hence at least T^r\hat T_rT^r​

Proved
IgnallSchrage.MeanCompletion.tval_le_sum_completion

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

flow-shoplower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling

Let 1≤r≤n−11\le r\le n-11≤r≤n−1, let JrJ_rJr​ be a node and let σ\sigmaσ be any full sequence that begins with JrJ_rJr​. Let (i1,…,in−r)(i_1,\dots,i_{n-r})(i1​,…,in−r​) be the order in which σ\sigmaσ processes the jobs of Jˉr\bar J_rJˉr​, and let di(σ)d_i(\sigma)di​(σ) be the completion times of σ\sigmaσ on machine BBB. Then

Tr(i1,…,in−r) ≤ ∑i∈Jˉrdi(σ)andT^r ≤ ∑i∈Jˉrdi(σ).T_r(i_1,\dots,i_{n-r})\ \le\ \sum_{i\in\bar J_r}d_i(\sigma) \qquad\text{and}\qquad \hat T_r\ \le\ \sum_{i\in\bar J_r}d_i(\sigma).Tr​(i1​,…,in−r​) ≤ i∈Jˉr​∑​di​(σ)andT^r​ ≤ i∈Jˉr​∑​di​(σ).

TrT_rTr​ is the value the sum would have if no job of Jˉr\bar J_rJˉr​ waited for machine BBB; delays can only increase the actual sum. This is the first half of the bound LB(Jr)LB(J_r)LB(Jr​).

Formalization Note The paper writes that with delays "the actual sum of completion times will exceed TrT_rTr​"; the statement makes this the non-strict inequality ≤\le≤, with equality when no delay occurs. The barred Jˉr\bar J_rJˉr​ under the paper's "∑Jrdi\sum_{J_r} d_i∑Jr​​di​" on p. 406 is invisible in the scan; the sum is over Jˉr\bar J_rJˉr​, as the paper's p. 405 decomposition into ∑i∈Jrdi+∑i∈Jˉrdi\sum_{i\in J_r}d_i+\sum_{i\in\bar J_r}d_i∑i∈Jr​​di​+∑i∈Jˉr​​di​ requires.

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

/-- pp. 405–406: for a node `J = J_r` with `1 ≤ r ≤ n - 1` and every full sequence `σ` that
begins with `J`, let `l = (i_1, …, i_{n-r})` be the order in which `σ` processes `J̄_r` (the
positions after the first `r`). Then `T_r(l) ≤ Σ_{i ∈ J̄_r} d_i(σ)`, and hence
`T̂_r ≤ Σ_{i ∈ J̄_r} d_i(σ)`. -/
theorem tval_le_sum_completion {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) :
    Tval a b J ((List.ofFn σ).drop J.length) ≤ ∑ i ∈ IgnallSchrage.Makespan.unscheduled J, completionTime a b σ i ∧
    That a b J ≤ ∑ i ∈ IgnallSchrage.Makespan.unscheduled J, completionTime a b σ i := 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), pp. 405–406, "M=2; A Lower Bound on Mean Completion Time for All Nodes Emanating from a Given Node", T_r and "the minimum possible value for T_r, call it T̂_r, 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