Theorem 3.1, p. 797 — load inequalities Σ_{j∈W} E[P_j] E[C^Π_j] ≥ f(W) for every nonanticipatory policy
ProvedStochSchedPrec.CMNS.theorem_3_1Consider machines, acyclic precedence constraints, release dates and independent nonnegative processing times whose coefficients of variation are bounded by for some . Let be any feasible nonanticipatory scheduling policy with integrable completion times . Then for every
with the set function (3.1).
These load inequalities, due to Möhring, Schulz and Uetz (J. ACM 1999, Cor. 3.1), are the polyhedral lower bound on which the LP relaxation of §3 rests.
Formalization Note Assumption 2.1 plays no role and is dropped. Comparator policies are required to have integrable completion times; a policy with satisfies any upper bound against it trivially, and the requirement prevents the Bochner integral from returning its default value . Comparator policies are also required to be measurable for the law of (almost everywhere equal to a Borel map): §5, p. 800, requires every policy to be a universally measurable map, which implies this. Without it a non-measurable policy on a suitably enlarged probability space can correlate its decisions with unobserved processing times, and the load inequalities fail.
import Mathlib import Definitions.Def_StochSchedPrec_CMNS_Model import Definitions.Def_StochSchedPrec_CMNS_Algorithm open MeasureTheory ProbabilityTheory
namespace StochSchedPrec.CMNS
theorem theorem_3_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 : V → ℝ) (hr : ∀ j, 0 ≤ r j)
(P : V → Ω → ℝ) (hP : IsStochModel Pr P) (Δ : ℝ) (hΔ : 0 ≤ Δ) (hCV : HasCVBound Pr P Δ)
(pol : (V → ℝ) → V → ℝ) (hpol : IsAdmissiblePolicy m A r Pr P pol)
(hpolm : AEMeasurable pol (Pr.map (fun ω k => P k ω))) (W : Finset V) :
loadFn m Δ (fun j => ∫ ω, P j ω ∂Pr) W
≤ ∑ j ∈ W, (∫ ω, P j ω ∂Pr) * ∫ ω, (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.