LEMMA 7, p. 338 — each algorithmic block has more Increase than Decrease tasks or starts at zero
ProvedGTWSched.FixedOrder.lemma_7earliness-tardinessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingsingle-machine
Let and be the preferred starts and lengths, and let be the schedule produced by the block-shifting algorithm for the first tasks. For every maximal contiguous block of , either its number of Decrease tasks is strictly less than its number of Increase tasks, or the first task starts at zero:
This is the invariant cited in the correctness proof of the algorithm.
Formalization Note Task represents the paper's ; a block is determined by equality of successive completion and starting times.
Preamble
import Mathlib import Definitions.Def_GTWSched_FixedOrder_Algorithm
Formal statement
namespace GTWSched.FixedOrder
/-- LEMMA 7, p. 338: every algorithmic block is weighted toward Increase,
unless its first task starts at zero. -/
theorem lemma_7 (a l : ℕ → ℝ) (ha : ∀ i, 0 ≤ a i) (hl : ∀ i, 0 ≤ l i)
(n j k : ℕ) (hblock : IsBlock l n (sched a l n) j k) :
decCount a (sched a l n) j k < incCount a (sched a l n) j k ∨
sched a l n j = 0 := by sorry
end GTWSched.FixedOrder
Source
Garey, Tarjan & Wilfong, One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties, Math. Oper. Res. 13 (1988), p. 338, LEMMA 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.