§2.1, p. 333 — a minimum cost schedule with a common preferred midtime has no gaps
ProvedGTWSched.NPC.min_cost_no_gapsearliness-tardinessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingsingle-machine
Consider tasks with lengths and one common preferred midtime , with cost . If is a minimum cost schedule, then has no gaps between tasks:
This is the first structural property of optimal schedules used in the proof of THEOREM 1.
Formalization Note Tasks are Fin (2n+1), is index 0; schedules have nonnegative starting times (a standing assumption, which never binds when ).
Preamble
import Mathlib import Definitions.Def_GTWSched_NPC_Schedules
Formal statement
namespace GTWSched.NPC
/-- p. 333: in the special case (tasks `T₀, …, T₂ₙ` with `0 < l₀ < l₁ < ⋯ < l₂ₙ` and one common
preferred midtime `M > ∑ᵢ lᵢ`), a minimum cost schedule has no gaps between tasks. -/
theorem min_cost_no_gaps {n : ℕ} (l : Fin (2 * n + 1) → ℝ) (M : ℝ) (hl0 : 0 < l 0)
(hmono : StrictMono l) (hM : ∑ i, l i < M) (s : Fin (2 * n + 1) → ℝ)
(hs : IsMinCost l M s) : NoGaps l 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. 333, §2.1, "The first observation we make …"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.