§2.1, p. 336 — the cost of a minimum cost schedule is Σᵢ(l₂ᵢ + l₂ᵢ₋₁)(n − i + 1/2) + (l₀)n
ProvedGTWSched.NPC.min_cost_eqearliness-tardinessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingsingle-machine
In the special case (tasks with and common preferred midtime ), the cost of every minimum cost schedule is
This value is the threshold of the instance D in the proof of THEOREM 1.
Formalization Note The right side is kStar l; with the 0-based its summand is .
Preamble
import Mathlib import Definitions.Def_GTWSched_NPC_Schedules
Formal statement
namespace GTWSched.NPC
/-- p. 336: in the special case, the cost of every minimum cost schedule is
`∑ᵢ₌₁ⁿ (l₂ᵢ + l₂ᵢ₋₁)(n − i + 1/2) + (l₀)n`. -/
theorem min_cost_eq {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) : commonCost l M s = kStar l := 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, §2.1, "Given the above characterization …"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.