Proof of COROLLARY 1, p. 344 — with the release time property, the tasks before T_N are those with deadline ≤ t + α
ProvedGTWSched.MaxDisc.rtp_implies_deadline_splitLet tasks have lengths , release times and deadlines in special form for (for every , either , or and ). Let be any task and take a feasible schedule with the release time property with respect to ; let be the starting time of . Then for every task ,
The paper observes that its proof of Corollary 1 shows exactly this: every optimum schedule with the release time property splits the tasks around by deadline, which is what the standard form and the algorithm of §3.2 exploit.
Formalization Note. The paper argues for optimum schedules with of maximum deadline; the statement here is for every feasible schedule and every task , since the argument uses only feasibility, the special form and the release time property.
import Mathlib import Definitions.Def_GTWSched_MaxDisc_Model
namespace GTWSched.MaxDisc
theorem rtp_implies_deadline_split {N : ℕ} (r d l : Fin N → ℝ) (α : ℝ) (hα : 0 ≤ α)
(hr : ∀ i, 0 ≤ r i) (hl : ∀ i, 0 ≤ l i) (hsf : SpecialForm r d l α)
(n : Fin N) (σ : Fin N ≃ Fin N) (s : Fin N → ℝ)
(hS : Feasible r d l σ s) (hrtp : ReleaseTimeProperty r σ s n) :
∀ i, i ≠ n → (σ.symm i < σ.symm n ↔ d i ≤ s n + α) := by sorry
end GTWSched.MaxDisc
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.