THEOREM 2, p. 338 — the block-shifting algorithm minimizes total discrepancy in a fixed order
ProvedGTWSched.FixedOrder.theorem_2earliness-tardinessoptimalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingsingle-machine
Let tasks have nonnegative preferred starting times and nonnegative lengths . For any , the block-shifting algorithm of §2.2 produces a feasible schedule for the first tasks in their prescribed order, and its total discrepancy is no greater than that of every other feasible schedule in the same order:
Feasibility and optimality together characterize the algorithm's output, including the empty schedule.
Formalization Note Task corresponds to . Every start is nonnegative; idle time is allowed, and the comparison class contains all schedules respecting the fixed order.
Preamble
import Mathlib import Definitions.Def_GTWSched_FixedOrder_Algorithm
Formal statement
namespace GTWSched.FixedOrder
/-- THEOREM 2, p. 338: the algorithm returns a feasible minimum-cost
schedule among all schedules of the first n tasks in the prescribed order. -/
theorem theorem_2 (a l : ℕ → ℝ) (ha : ∀ i, 0 ≤ a i) (hl : ∀ i, 0 ≤ l i)
(n : ℕ) :
FixedFeasible l n (sched a l n) ∧
∀ s : ℕ → ℝ, FixedFeasible l n s →
cost a n (sched a l n) ≤ cost a n 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. 338, THEOREM 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.