COROLLARY 2, p. 344 — if a feasible schedule exists, some optimum schedule is in standard form and has the release time property
ProvedGTWSched.MaxDisc.corollary_2Let tasks on one processor have lengths , release times and deadlines in special form for a constant (for every , either , or and ), indexed so that ; let , , be the last task. If a feasible schedule exists, then there are an optimum schedule and a split index such that
Standard form means: ; the schedule begins with an optimum schedule of the tasks of index ; then comes , starting at the maximum of and the completion time of that first part; then the tasks of index in this order, without idle time. The release time property means every task after has a release time strictly later than the start of .
This is the statement the paper's algorithm for minimizing the maximum discrepancy is built on: an optimum schedule for a prefix of the tasks is found among the standard-form candidates, one per split index, built from optimum schedules of shorter prefixes.
Formalization Note. Indices are 0-based. The paper's dummy task () is not a task; an empty first part () completes at time . The split index is the number of real tasks before , so its range is the paper's. Ties among deadlines are allowed; the standard form is relative to the given sorted indexing.
import Mathlib import Definitions.Def_GTWSched_MaxDisc_Model
namespace GTWSched.MaxDisc
theorem corollary_2 {N : ℕ} (r d l : Fin N → ℝ) (α : ℝ) (hα : 0 ≤ α)
(hr : ∀ i, 0 ≤ r i) (hl : ∀ i, 0 ≤ l i) (hsf : SpecialForm r d l α)
(hd : Monotone d) (n : Fin N) (hnlast : n.val + 1 = N)
(hfeas : ∃ (σ : Fin N ≃ Fin N) (s : Fin N → ℝ), Feasible r d l σ s) :
∃ (σ : Fin N ≃ Fin N) (s : Fin N → ℝ) (j : ℕ),
Optimum r d l σ s ∧ StandardForm r d l σ s j ∧ ReleaseTimeProperty r σ s n := by sorry
end GTWSched.MaxDisc
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.