pp. 405–406 — the sum of completion times over is at least of its order, hence at least
ProvedIgnallSchrage.MeanCompletion.tval_le_sum_completionflow-shoplower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let , let be a node and let be any full sequence that begins with . Let be the order in which processes the jobs of , and let be the completion times of on machine . Then
is the value the sum would have if no job of waited for machine ; delays can only increase the actual sum. This is the first half of the bound .
Formalization Note The paper writes that with delays "the actual sum of completion times will exceed "; the statement makes this the non-strict inequality , with equality when no delay occurs. The barred under the paper's "" on p. 406 is invisible in the scan; the sum is over , as the paper's p. 405 decomposition into requires.
Preamble
import Mathlib import Definitions.Def_IgnallSchrage_MeanCompletion_LowerBound
Formal statement
namespace IgnallSchrage.MeanCompletion
/-- pp. 405–406: for a node `J = J_r` with `1 ≤ r ≤ n - 1` and every full sequence `σ` that
begins with `J`, let `l = (i_1, …, i_{n-r})` be the order in which `σ` processes `J̄_r` (the
positions after the first `r`). Then `T_r(l) ≤ Σ_{i ∈ J̄_r} d_i(σ)`, and hence
`T̂_r ≤ Σ_{i ∈ J̄_r} d_i(σ)`. -/
theorem tval_le_sum_completion {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) :
Tval a b J ((List.ofFn σ).drop J.length) ≤ ∑ i ∈ IgnallSchrage.Makespan.unscheduled J, completionTime a b σ i ∧
That a b J ≤ ∑ i ∈ IgnallSchrage.Makespan.unscheduled J, completionTime a b σ i := 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), pp. 405–406, "M=2; A Lower Bound on Mean Completion Time for All Nodes Emanating from a Given Node", T_r and "the minimum possible value for T_r, call it T̂_r, is a lower bound"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.