LEMMA 3, p. 334 — in a minimum cost schedule |A(S)| = |B(S)|
ProvedGTWSched.NPC.lemma_3earliness-tardinessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingsingle-machine
LEMMA 3. In the special case (tasks with and common preferred midtime ), if is a minimum cost schedule then
where and : as many tasks have their midtimes before as after.
Formalization Note Tasks are Fin (2n+1); , are Finsets of indices; schedules have nonnegative starting times.
Preamble
import Mathlib import Definitions.Def_GTWSched_NPC_Schedules
Formal statement
namespace GTWSched.NPC
/-- LEMMA 3, p. 334: in the special case, a minimum cost schedule has `|A(S)| = |B(S)|`. -/
theorem lemma_3 {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) : (setA l M s).card = (setB l M s).card := by sorry
end GTWSched.NPC
Source
Garey, Tarjan & Wilfong, One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties, Math. Oper. Res. 13 (1988), p. 334, LEMMA 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.