§2.2, p. 337 — shifting a balanced block does not change total discrepancy
ProvedGTWSched.FixedOrder.shift_cost_eqearliness-tardinessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingsingle-machine
Consider a feasible fixed-order schedule for tasks , whose final block consists of tasks . Suppose this block contains equally many tasks that start later than preferred and tasks that start no later than preferred. Let be no greater than the distance to the first stopping event: the time-zero boundary or the preceding block, and the preferred start of any late task. Shifting the entire final block earlier by preserves total discrepancy:
This is the cost-preservation claim used when the algorithm shifts a balanced block.
Formalization Note Task corresponds to the paper's . The explicit bound on records the algorithm's first stopping event.
Preamble
import Mathlib import Definitions.Def_GTWSched_FixedOrder_Algorithm
Formal statement
namespace GTWSched.FixedOrder
/-- §2.2, p. 337: shifting a balanced final block until the first stopping
event leaves total discrepancy unchanged. -/
theorem shift_cost_eq (a l s : ℕ → ℝ) (m j : ℕ) (δ : ℝ)
(hfeas : FixedFeasible l (m + 1) s)
(hblock : IsBlock l (m + 1) s j m)
(hbalance : decCount a s j m = incCount a s j m)
(hpositive : s j ≠ 0)
(hδ : 0 ≤ δ ∧ δ ≤ shiftAmount a l s j m) :
cost a (m + 1) (shiftRange s j m δ) = cost a (m + 1) s := by sorry
end GTWSched.FixedOrder
Source
Garey, Tarjan & Wilfong, One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties, Math. Oper. Res. 13 (1988), p. 337, §2.2, balanced-block shift
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.