LEMMA 6, p. 335 — in a minimum cost bracket schedule {Aᵢ, Bᵢ} = {T₂ᵢ, T₂ᵢ₋₁}
ProvedGTWSched.NPC.lemma_6earliness-tardinessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingsingle-machine
In the special case (tasks with and common preferred midtime ):
LEMMA 6. If is a minimum cost schedule, then for every , ,
So in an optimal schedule the -th tasks on either side of are the -th pair of lengths.
Formalization Note The bracket is given by injective maps A B : Fin n → Fin (2n+1) with disjoint ranges avoiding (index 0); for the 0-based the conclusion is {A k, B k} = {evenTask k, oddTask k}, the indices and . The bracket schedule is packed against , which is the minimum cost schedule with that order and at .
Preamble
import Mathlib import Definitions.Def_GTWSched_NPC_Schedules
Formal statement
namespace GTWSched.NPC
/-- LEMMA 6, p. 335: if `[Aₙ, …, A₁, T₀@M, B₁, …, Bₙ]` is a minimum cost schedule, then
`{Aᵢ, Bᵢ} = {T₂ᵢ, T₂ᵢ₋₁}` for every `i` (0-based `i`: the tasks `2i + 2` and `2i + 1`). -/
theorem lemma_6 {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) :
({A i, B i} : Finset (Fin (2 * n + 1))) = {evenTask i, oddTask i} := 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 6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.