Lemma 4.4, p. 800 — E[C_j(P)] ≤ (m−1)/m E[ℓ_j(P)] + 1/m Σ_{B_j} E[P_i] under Graham's list scheduling
ProvedStochSchedPrec.InForest.lemma_4_4Consider the stochastic scheduling problem with an acyclic in-forest of precedence constraints on , identical machines, no release dates, and independent, nonnegative, integrable processing times . Let be a priority list that is a linear extension of the precedence constraints, and let be Graham's list scheduling with list : for every realization , is the Graham schedule. Fix for every realization a selector of critical predecessors, and let be the length of the critical chain for . Then for every job , the completion time satisfies
Combined with the LP bound of Lemma 3.3 and the critical-chain lower bound, this gives the performance guarantee of Theorem 4.5.
Formalization Note The page presupposes that and are random variables (§5, p. 800, asserts measurability of the paper's policies without proof); this is taken as the hypothesis that both are almost-everywhere measurable. Integrability of the is assumed so that the expectations on the right are finite.
import Mathlib import Definitions.Def_StochSchedPrec_InForest_Model import Definitions.Def_StochSchedPrec_InForest_LP import Definitions.Def_StochSchedPrec_InForest_Graham open MeasureTheory ProbabilityTheory
namespace StochSchedPrec.InForest
theorem lemma_4_4 {V : Type*} [Fintype V] [DecidableEq V]
{Ω : Type*} [MeasurableSpace Ω] {Pr : Measure Ω} [IsProbabilityMeasure Pr]
(m : ℕ) (hm : 0 < m) (A : V → V → Prop) (hacyc : IsAcyclic A) (hforest : IsInForest A)
(P : V → Ω → ℝ) (hP : IsStochProcTimes P Pr) (hPint : ∀ j, Integrable (P j) Pr)
(L : Fin (Fintype.card V) ≃ V) (hL : StochSchedPrec.CMNS.IsLinearExtension A L)
(γ : (V → ℝ) → (V → ℝ)) (hγ : ∀ p, IsNonneg p → IsGraham A m L p (γ p))
(hγmeas : ∀ j, AEMeasurable (fun ω => γ (fun k => P k ω) j) Pr)
(crit : (V → ℝ) → V → Option V) (hcrit : ∀ p, IsNonneg p → IsCritSelector A p (γ p) (crit p))
(hℓmeas : ∀ j, AEMeasurable
(fun ω => chainLen (crit (fun k => P k ω)) (fun k => P k ω) j) Pr)
(j : V) :
∫ ω, (γ (fun k => P k ω) j + P j ω) ∂Pr ≤
((m : ℝ) - 1) / m * ∫ ω, chainLen (crit (fun k => P k ω)) (fun k => P k ω) j ∂Pr
+ 1 / (m : ℝ) * ∑ i ∈ Bset L j, ∫ ω, P i ω ∂Pr := by sorry
end StochSchedPrec.InForest
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.