§3.1, p. 344 — after T_N: no idle time and nondecreasing deadlines, without moving T_N later
ProvedGTWSched.MaxDisc.normalize_afterLet tasks have lengths , release times and deadlines in special form for , indexed so that , and let be the last task, . Let be an optimum schedule with the release time property with respect to . Then there is an optimum schedule such that:
- it has the release time property with respect to , and occupies the same position as in ;
- the tasks before are executed in the same order and at the same times as in ;
- starts no later than before, , and in fact as early as possible:
with the inner maximum when no task precedes ; 4. the tasks after are executed in increasing order of index (hence of nondecreasing deadline); 5. from the start of on there is no idle time: each later task starts when its predecessor finishes.
These are the transformations by which the paper passes from a schedule given by Corollary 1 to a schedule in standard form.
Formalization Note. Indices are 0-based; the paper's is the index , expressed by a task with .
import Mathlib import Definitions.Def_GTWSched_MaxDisc_Model
namespace GTWSched.MaxDisc
theorem normalize_after {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)
(σ : Fin N ≃ Fin N) (s : Fin N → ℝ)
(hopt : Optimum r d l σ s) (hrtp : ReleaseTimeProperty r σ s n) :
∃ (σ' : Fin N ≃ Fin N) (s' : Fin N → ℝ),
Optimum r d l σ' s' ∧ ReleaseTimeProperty r σ' s' n ∧
σ'.symm n = σ.symm n ∧
(∀ p : Fin N, p < σ.symm n → σ' p = σ p ∧ s' (σ p) = s (σ p)) ∧
s' n ≤ s n ∧
s' n = max (r n) (⨆ i : {i : Fin N // σ'.symm i < σ'.symm n}, s' i.1 + l i.1) ∧
(∀ p q : Fin N, σ'.symm n < p → p < q → σ' p < σ' q) ∧
(∀ p q : Fin N, σ'.symm n ≤ p → q.val = p.val + 1 →
s' (σ' q) = s' (σ' p) + l (σ' p)) := by sorry
end GTWSched.MaxDisc
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.