Lemma 2.7, p. 795 — (1/m) E[Σ_{i∈O_j(P)} E[P_i]] ≤ (1/β) E[ℓ_j(P)]
ProvedStochSchedPrec.CMNS.lemma_2_7critical-chaindeliberate-idle-timep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-scheduling
In the standing stochastic model (with Assumption 2.1), let be a linear extension of the precedence constraints, , and a measurable CMNS policy with thresholds . For a job let be the random set of jobs after in started before , and the length of the critical chain of in the schedule (for a fixed tie-breaking rule). Then
Each out-of-order job has been charged its full threshold before starts, and that charge fits in the parts of not covered by the critical chain's waiting intervals.
Formalization Note The paper allows in this section; at the right-hand side is on the page but in Lean (), so the statement requires . Measurability of the policy is the paper's §5 assumption.
Preamble
import Mathlib import Definitions.Def_StochSchedPrec_CMNS_Model import Definitions.Def_StochSchedPrec_CMNS_Algorithm open MeasureTheory ProbabilityTheory
Formal statement
namespace StochSchedPrec.CMNS
theorem lemma_2_7 {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σm : AEMeasurable (fun ω => σ (fun k => P k ω)) Pr) (j : V) :
1 / (m : ℝ) * ∫ ω, ∑ i ∈ outOfOrder L (σ (fun k => P k ω)) j, (∫ ω', P i ω' ∂Pr) ∂Pr
≤ 1 / β * ∫ ω, chainLength A r tb (fun k => P k ω) (σ (fun k => P k ω)) j ∂Pr := by sorry
end StochSchedPrec.CMNS
Source
Skutella and Uetz, Stochastic machine scheduling with precedence constraints, SIAM J. Comput. 34(4) (2005) 788–802, p. 795, Lemma 2.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.