COROLLARY 1, p. 344 — some optimum schedule executes before T_N exactly the tasks with deadline ≤ β
ProvedGTWSched.MaxDisc.corollary_1Let tasks have lengths , release times and deadlines in special form for , and let be a task of maximum deadline. If a feasible schedule exists, then there are an optimum schedule and a real number such that for every task ,
This is the form of Theorem 4 on which the paper's algorithm is built: the set of tasks before the maximum-deadline task is a deadline threshold set.
Formalization Note. The paper says "the set of tasks executed before is exactly the set of all tasks with deadline or less". The set is read as excluding itself: in the proof with the start of , and may hold, in which case would belong to the set of tasks with deadline at most although it is not executed before itself. This is the only reading under which the corollary holds.
import Mathlib import Definitions.Def_GTWSched_MaxDisc_Model
namespace GTWSched.MaxDisc
theorem corollary_1 {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 ∧ 0 ≤ β ∧
∀ i, i ≠ n → (σ.symm i < σ.symm n ↔ d i ≤ β) := by sorry
end GTWSched.MaxDisc
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.