Lemma 2.6, p. 795 — E[Σ_{i∈O_j(P)} P_i] = E[Σ_{i∈O_j(P)} E[P_i]]
ProvedStochSchedPrec.CMNS.lemma_2_6Consider the standing stochastic model: machines, acyclic precedence constraints, release dates satisfying Assumption 2.1, and independent, nonnegative, integrable processing times . Let be a linear extension of the precedence constraints, , and let be the CMNS policy with thresholds , nonanticipatory and measurable. For a job let be the random set of jobs after in that are started before . Then
The decision to start out of order is taken before is observed, so in expectation the out-of-order jobs contribute their expected processing times. This is where independence and nonanticipation enter the analysis.
Formalization Note Nonanticipation and measurability of the CMNS policy are taken as hypotheses: the paper asserts both for CMNS without proof (p. 795; §5, p. 800, where it requires universal measurability). The linear-extension hypothesis is the setting of Lemma 2.5 and Theorem 2.8; it is needed when processing times can be with positive probability: if a job were a predecessor of , then would let start at the same instant as , so whether would depend on .
import Mathlib import Definitions.Def_StochSchedPrec_CMNS_Model import Definitions.Def_StochSchedPrec_CMNS_Algorithm open MeasureTheory ProbabilityTheory
namespace StochSchedPrec.CMNS
theorem lemma_2_6 {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 ≤ β)
(σ : (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) :
∫ ω, ∑ i ∈ outOfOrder L (σ (fun k => P k ω)) j, P i ω ∂Pr
= ∫ ω, ∑ i ∈ outOfOrder L (σ (fun k => P k ω)) j, (∫ ω', P i ω' ∂Pr) ∂Pr := by sorry
end StochSchedPrec.CMNS
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.