§3.1, p. 344 — every task after T_N is released by the time T_N finishes
ProvedGTWSched.MaxDisc.release_le_finishdeadlinesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1release-timesschedulingsingle-machine
Let tasks have lengths , release times and deadlines in special form for , and let be a task of maximum deadline. In every feasible schedule, every task executed after satisfies
i.e. it is released no later than the time at which finishes.
The paper derives from this that there is no need for idle time after starts and that the tasks after can be taken in nondecreasing order of deadlines; both steps lead to the standard form.
Formalization Note. The paper states this for optimum schedules of the form given by Corollary 1. The statement here holds for every feasible schedule, since the argument uses only the special form, the maximality of and .
Preamble
import Mathlib import Definitions.Def_GTWSched_MaxDisc_Model
Formal statement
namespace GTWSched.MaxDisc
theorem release_le_finish {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) (σ : Fin N ≃ Fin N) (s : Fin N → ℝ)
(hS : Feasible r d l σ s) :
∀ i, σ.symm n < σ.symm i → r i ≤ s n + l n := by sorry
end GTWSched.MaxDisc
Source
Garey, Tarjan & Wilfong, One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties, Math. Oper. Res. 13 (1988), p. 344, paragraph after the proof of COROLLARY 1 ("In particular, this says that all tasks executed after T_N must have release times no greater than the time at which T_N finishes")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.