Exactness of at depth (needed by the stopping rule, p. 402)
ProvedIgnallSchrage.MeanCompletion.lowerBound_eq_totalCompletion_of_terminalbranch-and-boundflow-shoplower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let be a node that has scheduled of the jobs, so that is a single job, and let be the full sequence followed by . Then
The paper's stopping rule declares a terminal node's sequence optimal as soon as the node is first on the list; that conclusion needs the bound of such a node to be the value of its sequence, which is this statement.
Formalization Note The paper does not state this for two machines; it is the general form of what its stopping rule (p. 402) relies on, and is labelled as such. It holds for arbitrary real processing times and also for , where the node is the root (with read as ).
Preamble
import Mathlib import Definitions.Def_IgnallSchrage_MeanCompletion_LowerBound
Formal statement
namespace IgnallSchrage.MeanCompletion
/-- Exactness of the bound at depth `n - 1` (needed by the stopping rule of p. 402): if the
node `J` has scheduled `n - 1` of the `n` jobs, then for the (unique) full sequence `σ` that
begins with `J`, `LB(J) = Σ_i d_i(σ)`. -/
theorem lowerBound_eq_totalCompletion_of_terminal {n : ℕ} (a b : Fin n → ℝ)
(J : List (Fin n)) (hJ : J.length + 1 = 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. 402, "The Branch-and-Bound Technique", stopping rule (general form needed for the bound of p. 406)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.