Theorem 2.8, p. 796 — expected completion-time bound (2.5) for Algorithm CMNS
ProvedStochSchedPrec.CMNS.theorem_2_8Consider an instance of in the standing stochastic model, with Assumption 2.1, a priority list that is a linear extension of the precedence constraints, , and the CMNS policy with thresholds (nonanticipatory and measurable). Then the completion time of every job is integrable and
where is the length of the critical chain of in and the set of jobs up to and including in .
This is the upper-bound half of the approximation guarantee of Theorem 4.1; no assumption on the distributions beyond independence and finite means is needed.
Formalization Note The page writes ; at the bound is vacuous on the page () but would be false in Lean (), so is assumed. Integrability of is part of the conclusion. Nonanticipation and measurability of the CMNS policy are the paper's assertions (p. 795; §5, p. 800), taken as hypotheses.
import Mathlib import Definitions.Def_StochSchedPrec_CMNS_Model import Definitions.Def_StochSchedPrec_CMNS_Algorithm open MeasureTheory ProbabilityTheory
namespace StochSchedPrec.CMNS
theorem theorem_2_8 {V : Type*} [Fintype V] [DecidableEq V]
{Ω : Type*} [MeasurableSpace Ω] {Pr : Measure Ω} [IsProbabilityMeasure Pr]
(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)
(P : V → Ω → ℝ) (hP : IsStochModel Pr P)
(L : Fin (Fintype.card V) ≃ V) (hLE : IsLinearExtension A L) (β : ℝ) (hβ : 0 < β)
(tb : V ≃ Fin (Fintype.card V))
(σ : (V → ℝ) → V → ℝ) (hσ : IsCMNSPolicy m A r L β (fun j => ∫ ω, P j ω ∂Pr) σ)
(hσna : IsNonanticipatory σ)
(hσm : AEMeasurable σ (Pr.map (fun ω k => P k ω))) (j : V) :
Integrable (fun ω => σ (fun k => P k ω) j + P j ω) Pr ∧
∫ ω, (σ (fun k => P k ω) j + P j ω) ∂Pr
≤ (((m : ℝ) - 1) / m + 1 / β)
* ∫ ω, chainLength A r tb (fun k => P k ω) (σ (fun k => P k ω)) j ∂Pr
+ (1 + β) / m * ∑ i ∈ before L j, ∫ ω, P i ω ∂Pr + 1 / (m : ℝ) * r j := by sorry
end StochSchedPrec.CMNS
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.