§2.1, p. 333 — a minimum cost schedule with a common preferred midtime is ordered
ProvedGTWSched.NPC.min_cost_orderedearliness-tardinessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingsingle-machine
In the setting of the special case (tasks , , common preferred midtime ), every minimum cost schedule is ordered: with and ,
Shorter tasks are scheduled nearer to on each side.
Formalization Note Tasks are Fin (2n+1); schedules have nonnegative starting times.
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 is ordered. -/
theorem min_cost_ordered {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) : Ordered 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. 333, §2.1, "It is easy to show that for any minimum cost schedule …"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.