p. 406 — ordering by increasing attains
ProvedIgnallSchrage.MeanCompletion.sval_eq_shat_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 .
Together with the previous statement, this makes computable with two sorts.
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 => b i ≤ b 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 `(j_1, …, j_{n-r})` of `J̄_r` with `b_{j_1} ≤ b_{j_2} ≤ ⋯ ≤ b_{j_{n-r}}`
attains the minimum `Ŝ_r` of `S_r` over all orderings of `J̄_r`. -/
theorem sval_eq_shat_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 => b i ≤ b j)) :
Sval a b J l = Shat 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, "S_r=constant+Σ_{p=1}^{n−r}(n−r−p+1)b_{j_p} so it is clear that choosing a sequence so that b_{j_1}≦⋯≦b_{j_{n−r}} will minimize S_r"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.