p. 406 — is a lower bound on the sum of completion times
ProvedIgnallSchrage.MeanCompletion.lowerBound_le_totalCompletionbranch-and-boundflow-shoplower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let and let be a node. For every full sequence that begins with ,
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 " is a lower bound" is read as: for every node with , and every one of the full sequences beginning with it, 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 .
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.