THEOREM 2 proof, Case 2.2, p. 338 — an earlier new task cannot lower the last block's discrepancy
ProvedGTWSched.FixedOrder.case_2_2_blockearliness-tardinessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingsingle-machine
In Case 2, let append the new task to at the preceding task's completion time, and let be the final block of . For any feasible fixed-order schedule with the new task starting earlier than in , every task of this final block starts no later in than in , and its total block discrepancy cannot be smaller:
The claim is applied to the actual block formed by the algorithm; the count condition on an arbitrary block would not suffice.
Formalization Note Task is the paper's . Feasibility includes nonnegative starts and the prescribed task order.
Preamble
import Mathlib import Definitions.Def_GTWSched_FixedOrder_Algorithm
Formal statement
namespace GTWSched.FixedOrder
/-- Case 2.2 of THEOREM 2, p. 338: an alternative that places the new task
earlier moves every task of R's final block earlier and cannot lower that
block's total discrepancy. -/
theorem case_2_2_block (a l : ℕ → ℝ) (ha : ∀ i, 0 ≤ a i)
(hl : ∀ i, 0 ≤ l i) (n : ℕ) (hn : 0 < n)
(hlate : a n < sched a l n (n - 1) + l (n - 1))
(s : ℕ → ℝ) (hs : FixedFeasible l (n + 1) s) :
let r := place (sched a l n) n (sched a l n (n - 1) + l (n - 1))
let j := blockStart l r n
s n < r n →
(∀ i, j ≤ i → i ≤ n → s i ≤ r i) ∧
(∑ i ∈ Finset.Icc j n, |r i - a i|) ≤
∑ i ∈ Finset.Icc j n, |s i - a i| := 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, THEOREM 2 proof, Case 2.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.