p. 411 — on two machines, adding raises of every sequence by
ProvedIgnallSchrage.Invariance.sumCompletion_shiftflow-shopp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Consider jobs on two machines with nonnegative processing times , and let . Write for the sum of the completion times of the full sequence , and for the same sum after adding to every processing time. Then for every
The same constant is added to the value of every sequence, so the set of optimal sequences is unchanged.
Formalization Note Nonnegative processing times are assumed, as for the completion-time shift.
Preamble
import Mathlib import Definitions.Def_IgnallSchrage_Invariance_TwoMachine
Formal statement
namespace IgnallSchrage.Invariance
/-- p. 411: on two machines, adding `G` to all processing times (all nonnegative) raises the sum of the
completion times of every sequence by `Σ_{r=1}^{n} G (r + 1) = ½ G n (n + 3)`. -/
theorem sumCompletion_shift {n : ℕ} (a b : Fin n → ℝ)
(ha : ∀ i, 0 ≤ a i) (hb : ∀ i, 0 ≤ b i) (G : ℝ) (hG : 0 < G)
(σ : Equiv.Perm (Fin n)) :
sumCompletion (fun i => a i + G) (fun i => b i + G) σ =
sumCompletion a b σ + G * n * (n + 3) / 2 := by sorry
end IgnallSchrage.Invariance
Source
Ignall and Schrage, Application of the branch and bound technique to some flow-shop scheduling problems, Oper. Res. 13 (1965), p. 411, Appendix, proof of the THEOREM (sum of the completion times increased by ½Gn(n+3))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.