Lemma 4.3, p. 799 — Graham's schedule processes no job of A_j in [r_j(p), S_j(p)[ for in-forests
ProvedStochSchedPrec.InForest.lemma_4_3Let the precedence constraints on the job set form an acyclic in-forest (each job has at most one successor), let , and let be a priority list that is a linear extension of the precedence constraints. Let be any realization of the processing times and the schedule constructed by Graham's list scheduling with list on machines (no release dates). For a job let be the earliest time at which is available, and the set of jobs after in . Then no job of is in process during :
The lemma is the in-forest substitute for deliberate idle time: in the interval where waits, the machines are occupied only by jobs of higher priority. It drives the per-realization completion-time bound of Lemma 4.4.
Formalization Note Zero processing times are allowed (), as in the paper.
import Mathlib import Definitions.Def_StochSchedPrec_InForest_Model import Definitions.Def_StochSchedPrec_InForest_LP import Definitions.Def_StochSchedPrec_InForest_Graham
namespace StochSchedPrec.InForest
theorem lemma_4_3 {V : Type*} [Fintype V] [DecidableEq V]
(m : ℕ) (hm : 0 < m) (A : V → V → Prop) (hacyc : IsAcyclic A) (hforest : IsInForest A)
(L : Fin (Fintype.card V) ≃ V) (hL : StochSchedPrec.CMNS.IsLinearExtension A L)
(p : V → ℝ) (hp : IsNonneg p) (S : V → ℝ) (hS : IsGraham A m L p S)
(j k : V) (hk : k ∈ Aset L j) (t : ℝ) (ht₁ : availTime A p S j ≤ t) (ht₂ : t < S j) :
¬ (S k ≤ t ∧ t < S k + p k) := by sorry
end StochSchedPrec.InForest
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.