Theorem 4.1, p. 798 — CMNS with an LP-optimal priority list is a (1+β)(1+1/β+max{1,(m−1)Δ/m})-approximation for P|r_j, prec|E[Σ w_j C_j]
ProvedStochSchedPrec.CMNS.theorem_4_1Consider an instance of the stochastic machine scheduling problem : identical machines, acyclic precedence constraints, release dates satisfying Assumption 2.1, weights , and independent nonnegative processing times with for all and some . Let be an optimal solution of the LP relaxation of §3, let be a priority list according to nondecreasing , let , and let be the policy given by Algorithm CMNS with list and thresholds . Then the expected cost of CMNS is finite and, for every feasible nonanticipatory scheduling policy with integrable completion times,
In particular CMNS is an -approximation. For NBUE processing times one may take , and gives .
Formalization Note The comparison is against every admissible policy, which implies the paper's comparison with an optimal policy and does not presuppose that one exists. Nonanticipation and measurability of the CMNS policy are the paper's assertions (p. 795; §5, p. 800), taken as hypotheses; measurability, of the CMNS policy and of the comparators, means measurability for the law of , which §5's universal measurability of every policy implies. The fact that the LP order is a linear extension of the precedence constraints is not assumed: it follows from and the arc constraints of the LP.
import Mathlib import Definitions.Def_StochSchedPrec_CMNS_Model import Definitions.Def_StochSchedPrec_CMNS_Algorithm open MeasureTheory ProbabilityTheory
namespace StochSchedPrec.CMNS
theorem theorem_4_1 {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 w : V → ℝ) (hr : ∀ j, 0 ≤ r j) (hw : ∀ j, 0 ≤ w j)
(hAss : ∀ i j, Relation.TransGen A i j → r i ≤ r j)
(P : V → Ω → ℝ) (hP : IsStochModel Pr P) (Δ : ℝ) (hΔ : 0 ≤ Δ) (hCV : HasCVBound Pr P Δ)
(C : V → ℝ) (hC : IsLPOptimal m A Δ (fun j => ∫ ω, P j ω ∂Pr) w C)
(L : Fin (Fintype.card V) ≃ V) (hL : IsSortedBy L C) (β : ℝ) (hβ : 0 < β)
(σ : (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 ω)))
(pol : (V → ℝ) → V → ℝ) (hpol : IsAdmissiblePolicy m A r Pr P pol)
(hpolm : AEMeasurable pol (Pr.map (fun ω k => P k ω))) :
Integrable (fun ω => ∑ j, w j * (σ (fun k => P k ω) j + P j ω)) Pr ∧
∫ ω, ∑ j, w j * (σ (fun k => P k ω) j + P j ω) ∂Pr
≤ (1 + β) * (1 + 1 / β + max 1 (((m : ℝ) - 1) / m * Δ))
* ∫ ω, ∑ j, w j * (pol (fun k => P k ω) j + P j ω) ∂Pr := by sorry
end StochSchedPrec.CMNS
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.