Proof of THEOREM 1, p. 336 — every schedule of T₀, …, T₂ₙ costs at least k, and equality forces the optimal form
ProvedGTWSched.NPC.cost_ge_k_and_eq_caseearliness-tardinessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingsingle-machine
Let have lengths and the common preferred midtime used in the construction of , and let
For every schedule of these tasks (nonnegative starting times, no overlaps):
- ;
- If , then is ordered, has no gaps, has , and for each , , exactly one of is in and the other is in .
This is the form in which the proof of THEOREM 1 uses Lemmas 2–6 and the minimum cost formula.
Formalization Note The midtime is fixed to the value used in . The earlier special case assumes ; this proof step applies its cost bound and necessary equality conditions at . For the 0-based , and are oddTask k' and evenTask k'.
Preamble
import Mathlib import Definitions.Def_GTWSched_NPC_Schedules
Formal statement
namespace GTWSched.NPC
/-- p. 336, proof of THEOREM 1: at the constructed common preferred midtime
`M = (∑ᵢ lᵢ)/2`, every schedule of `T₀, …, T₂ₙ` costs at least `k`. A schedule of cost
exactly `k` is ordered, has no gaps, has `m₀(S) = M`, and places one task of each pair on
either side of `M`. -/
theorem cost_ge_k_and_eq_case {n : ℕ} (l : Fin (2 * n + 1) → ℝ) (M : ℝ) (hl0 : 0 < l 0)
(hmono : StrictMono l) (hM : M = (∑ i, l i) / 2)
(s : Fin (2 * n + 1) → ℝ) (hs : IsSchedule l s) :
kStar l ≤ commonCost l M s ∧
(commonCost l M s = kStar l →
Ordered l M s ∧ NoGaps l s ∧ mid l s 0 = M ∧
∀ i : Fin n,
(oddTask i ∈ setA l M s ∧ evenTask i ∈ setB l M s) ∨
(evenTask i ∈ setA l M s ∧ oddTask i ∈ setB l M s)) := by sorry
end GTWSched.NPC
Source
Garey, Tarjan & Wilfong, One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties, Math. Oper. Res. 13 (1988), p. 336, proof of THEOREM 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.