p. 411 — on three machines, adding raises every makespan and every non-root by
ProvedIgnallSchrage.Invariance.threeMachine_shiftflow-shoplower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Consider jobs on three machines with nonnegative processing times, and let . Add to every processing time. Then
- the makespan of every full sequence increases by ;
- the lower bound of p. 401 of every node ( distinct jobs) with increases by :
Together with the two-machine shift, this is the paper's "the same arguments hold for the 3-machine case".
Formalization Note The page says "all lower bounds". At the root the claim is false, because does not move. For example , , , , gives before the shift and after, not . The root is never compared with another node, so the statement is restricted to . Nonnegative processing times are assumed, as for the completion-time shift.
Preamble
import Mathlib import Definitions.Def_IgnallSchrage_Invariance_ThreeMachine
Formal statement
namespace IgnallSchrage.Invariance
/-- p. 411: on three machines, adding `G` to all processing times (all nonnegative) raises the makespan of every
sequence by `G (n + 2)` (for `n ≥ 1`), and the lower bound `LB(J_r)` of every node with
`1 ≤ r ≤ n - 1` by `G (n + 2)`. The page says "all lower bounds"; at the root `r = 0` the
claim is false (`TIMEB(∅) = 0` rises by `0`, not `G`), so the root is excluded. -/
theorem threeMachine_shift {n : ℕ} (hn : 1 ≤ n) (a b c : Fin n → ℝ)
(ha : ∀ i, 0 ≤ a i) (hb : ∀ i, 0 ≤ b i) (hc : ∀ i, 0 ≤ c i) (G : ℝ) (hG : 0 < G) :
(∀ σ : Equiv.Perm (Fin n),
IgnallSchrage.Makespan.makespan (fun i => a i + G) (fun i => b i + G) (fun i => c i + G) σ =
IgnallSchrage.Makespan.makespan a b c σ + G * (n + 2)) ∧
(∀ J : List (Fin n), J.Nodup → 1 ≤ J.length → J.length + 1 ≤ n →
lowerBound3 (fun i => a i + G) (fun i => b i + G) (fun i => c i + G) J =
lowerBound3 a b c J + G * (n + 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 (3-machine lower bounds and makespans increased by G(n+2))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.