THEOREM 2 proof, Case 2, p. 338 — cost of appending a late task
ProvedGTWSched.FixedOrder.case_2_costearliness-tardinessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingsingle-machine
Let be the algorithm's schedule for tasks. If the preceding task finishes after task 's preferred starting time, then the algorithm appends task at that finish time and possibly shifts the final block. The resulting total cost is
This identity isolates the new task's discrepancy in Case 2 of the optimality proof.
Formalization Note The paper's task is task here. Preferred starts and lengths are nonnegative, as in the paper's model.
Preamble
import Mathlib import Definitions.Def_GTWSched_FixedOrder_Algorithm
Formal statement
namespace GTWSched.FixedOrder
/-- Case 2 of THEOREM 2, p. 338: inserting the late new task adds precisely
its discrepancy; a subsequent balanced-block shift costs nothing. -/
theorem case_2_cost (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)) :
cost a (n + 1) (sched a l (n + 1)) =
cost a n (sched a l n) +
(sched a l n (n - 1) + l (n - 1) - a n) := 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
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.