Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

p. 402 — branch and bound with the two-machine bound of p. 406 stops at a sequence of least mean completion time

Proved
IgnallSchrage.MeanCompletion.branch_and_bound_optimal

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

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

Let n≥1n\ge1n≥1 jobs have arbitrary real processing times aia_iai​ on machine AAA and bib_ibi​ on machine BBB. Run the branch-and-bound procedure of p. 402, ranking nodes by

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

Then:

  1. the procedure stops: after some number kkk of steps, the first node of the list is terminal (it has scheduled n−1n-1n−1 jobs);
  2. whenever the first node PPP of the list is terminal, the sequence σ∗\sigma^\astσ∗ consisting of PPP followed by its one unscheduled job satisfies
∑i=1ndi(σ∗) ≤ ∑i=1ndi(σ)for every permutation σ of the n jobs.\sum_{i=1}^{n}d_i(\sigma^\ast)\ \le\ \sum_{i=1}^{n}d_i(\sigma)\qquad\text{for every permutation }\sigma\text{ of the }n\text{ jobs}.i=1∑n​di​(σ∗) ≤ i=1∑n​di​(σ)for every permutation σ of the n jobs.

Since nnn is fixed, σ∗\sigma^\astσ∗ also minimizes the mean completion time 1n∑idi\frac1n\sum_i d_in1​∑i​di​, the paper's objective. This is the correctness of the paper's method for the two-machine mean-completion-time problem.

Formalization Note "The problem is solved: that node's sequence is an optimal one" is read as termination (some kkk) together with optimality over all n!n!n! permutation sequences. Terminal nodes are those at depth n−1n-1n−1, whose last job is forced, as the paper's example (p. 403) and node counts show. The tie rule is that of p. 403 (a new node precedes old nodes with the same bound); the statement holds for any real data, without a sign condition.

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

/-- p. 402, stopping rule, with the two-machine bound of p. 406: for `n ≥ 1` jobs and any real
processing times, (i) the branch-and-bound IgnallSchrage.Makespan.run ranked by `LB(J_r) = Σ_{J_r} d_i + max(T̂_r, Ŝ_r)`
reaches a list whose first node is terminal, and (ii) whenever the first node `P` of the list
is terminal, `P` is the beginning of a full sequence `σ*` (namely `P` followed by its one
IgnallSchrage.Makespan.unscheduled job) whose sum of completion times is at most that of every one of the `n!`
sequences. -/
theorem branch_and_bound_optimal {n : ℕ} (hn : 1 ≤ n) (a b : Fin n → ℝ) :
    (∃ k P, (IgnallSchrage.Makespan.run (lowerBound a b) k).head? = some P ∧ IgnallSchrage.Makespan.IsTerminal P) ∧
    ∀ k P, (IgnallSchrage.Makespan.run (lowerBound a b) k).head? = some P → IgnallSchrage.Makespan.IsTerminal P →
      ∃ σstar : Equiv.Perm (Fin n), IgnallSchrage.Makespan.BeginsWith σstar P ∧
        ∀ σ : Equiv.Perm (Fin n), totalCompletion a b σstar ≤ 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. 402, "The Branch-and-Bound Technique", stopping rule; with the bound of p. 406, "M=2; A Lower Bound on Mean Completion Time for All Nodes Emanating from a Given Node"
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