LEMMA 5, p. 335 — swapping Aᵢ and Bᵢ in [Aₙ, …, A₁, T₀@M, B₁, …, Bₙ] keeps the cost
ProvedGTWSched.NPC.lemma_5earliness-tardinessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingsingle-machine
Let have lengths and common preferred midtime . For a schedule
( with midtime , the 's after it and the 's before it in the indicated order, packed without gaps) and , let be the schedule obtained by swapping and .
LEMMA 5.
Formalization Note The bracket is given by injective maps A B : Fin n → Fin (2n+1) with disjoint ranges avoiding ; A k is the paper's , and is obtained by updating A at to B i and B at to A i. The common midtime satisfies , and is a minimum cost schedule, as in the surrounding special case.
Preamble
import Mathlib import Definitions.Def_GTWSched_NPC_Schedules
Formal statement
namespace GTWSched.NPC
/-- LEMMA 5, p. 335: swapping `Aᵢ` and `Bᵢ` in `[Aₙ, …, A₁, T₀@M, B₁, …, Bₙ]` does not change the
cost. -/
theorem lemma_5 {n : ℕ} (l : Fin (2 * n + 1) → ℝ) (M : ℝ) (hl0 : 0 < l 0)
(hmono : StrictMono l) (hM : ∑ i, l i < M)
(A B : Fin n → Fin (2 * n + 1)) (hAB : IsBracket A B)
(hmin : IsMinCost l M (centered l M A B)) (i : Fin n) :
commonCost l M (centered l M (Function.update A i (B i)) (Function.update B i (A i))) =
commonCost l M (centered l M A B) := by sorry
end GTWSched.NPC
Source
Garey, Tarjan & Wilfong, One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties, Math. Oper. Res. 13 (1988), p. 335, LEMMA 5 (Sᵢ defined on p. 335)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.