THEOREM 4, pp. 342–343 — some optimum schedule has the release time property w.r.t. a maximum-deadline task
ProvedGTWSched.MaxDisc.theorem_4Let tasks on one processor have lengths , release times and deadlines in special form for a constant : for every , either , or and . Let be a task with the largest deadline, for all . If a feasible schedule exists, then there is an optimum schedule (feasible, of minimum makespan among all feasible schedules) such that
where is the starting time of ; that is, the schedule has the release time property.
This is the key normalization result of §3.1; Corollaries 1 and 2 and the paper's algorithm for the maximum-discrepancy problem rest on it. For arbitrary release times and deadlines it is false: the special form is essential.
Formalization Note. Schedules are an execution order (a permutation of the task indices) plus starting times; "executed after" refers to that order. Tasks are indexed by Fin N.
import Mathlib import Definitions.Def_GTWSched_MaxDisc_Model
namespace GTWSched.MaxDisc
theorem theorem_4 {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) (hn : ∀ i, d i ≤ d n)
(hfeas : ∃ (σ : Fin N ≃ Fin N) (s : Fin N → ℝ), Feasible r d l σ s) :
∃ (σ : Fin N ≃ Fin N) (s : Fin N → ℝ),
Optimum r d l σ s ∧ ReleaseTimeProperty r σ s n := by sorry
end GTWSched.MaxDisc
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.