Lemma 2.5, p. 794 — per-realization completion-time bound (2.1) for Algorithm CMNS
ProvedStochSchedPrec.CMNS.lemma_2_5Consider an instance with machines, acyclic precedence constraints and release dates satisfying Assumption 2.1. Let be a priority list that is a linear extension of the precedence constraints, , , a realization, and let be the schedule constructed by Algorithm CMNS with completion times . Let be the length of the critical chain of in this schedule (for a fixed tie-breaking rule). Then for every job
where is the set of jobs up to and including in and the set of jobs after in that are started before .
This is the deterministic core of the analysis: after taking expectations it yields Theorem 2.8.
Formalization Note The paper has ; the bound holds for any nonnegative threshold vector.
import Mathlib import Definitions.Def_StochSchedPrec_CMNS_Model import Definitions.Def_StochSchedPrec_CMNS_Algorithm open MeasureTheory ProbabilityTheory
namespace StochSchedPrec.CMNS
theorem lemma_2_5 {V : Type*} [Fintype V] [DecidableEq V]
(m : ℕ) (hm : 0 < m) (A : V → V → Prop) (hacyc : ∀ j, ¬ Relation.TransGen A j j)
(r : V → ℝ) (hr : ∀ j, 0 ≤ r j) (hAss : ∀ i j, Relation.TransGen A i j → r i ≤ r j)
(L : Fin (Fintype.card V) ≃ V) (hLE : IsLinearExtension A L)
(β : ℝ) (hβ : 0 ≤ β) (μ : V → ℝ) (hμ : ∀ j, 0 ≤ μ j)
(tb : V ≃ Fin (Fintype.card V))
(p : V → ℝ) (hp : ∀ j, 0 ≤ p j) (S : V → ℝ) (hS : IsCMNSRun m A r L β μ p S) (j : V) :
S j + p j ≤ ((m : ℝ) - 1) / m * chainLength A r tb p S j + 1 / (m : ℝ) * r j
+ 1 / (m : ℝ) * (∑ i ∈ before L j, (p i + β * μ i) + ∑ i ∈ outOfOrder L S j, p i) := by sorry
end StochSchedPrec.CMNS
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.