p. 406 — ordering by increasing attains
ProvedIgnallSchrage.MeanCompletion.tval_eq_that_of_sortedflow-shoplower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let be a node and an ordering of with
Then , the minimum of over all orderings of .
This makes computable by a sort instead of a minimization over orderings.
Formalization Note The ordering is a list that is a permutation of the list of the jobs of ; "sorted" is List.Pairwise (fun i j => a i ≤ a j). The statement holds for any node, including the root.
Preamble
import Mathlib import Definitions.Def_IgnallSchrage_MeanCompletion_LowerBound
Formal statement
namespace IgnallSchrage.MeanCompletion
/-- p. 406: an ordering `(i_1, …, i_{n-r})` of `J̄_r` with `a_{i_1} ≤ a_{i_2} ≤ ⋯ ≤ a_{i_{n-r}}`
attains the minimum `T̂_r` of `T_r` over all orderings of `J̄_r`. -/
theorem tval_eq_that_of_sorted {n : ℕ} (a b : Fin n → ℝ) (J : List (Fin n))
(l : List (Fin n)) (hl : l ∈ orderings J) (hsort : l.Pairwise (fun i j => a i ≤ a j)) :
Tval a b J l = That a b J := 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, "Since T_r=constant+Σ_p (n−r−p+1)a_{i_p}, …"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.