§3, p. 797 — the expected completion times of any nonanticipatory policy are LP-feasible, so the LP optimum is a lower bound
ProvedStochSchedPrec.CMNS.lp_relaxationlower-boundlp-relaxationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-scheduling
Under the assumptions of Theorem 3.1 (independent nonnegative processing times with , ; release dates ; weights ), let be any feasible nonanticipatory policy with integrable completion times. Then the vector satisfies all constraints of the LP relaxation
and consequently every optimal solution of the LP satisfies
The LP is therefore a relaxation of , and its optimal value is a lower bound on the expected cost of every nonanticipatory policy.
Formalization Note As in Theorem 3.1, comparator policies have integrable completion times and are measurable for the law of (§5, p. 800, requires universal measurability of every policy).
Preamble
import Mathlib import Definitions.Def_StochSchedPrec_CMNS_Model import Definitions.Def_StochSchedPrec_CMNS_Algorithm open MeasureTheory ProbabilityTheory
Formal statement
namespace StochSchedPrec.CMNS
theorem lp_relaxation {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)
(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 ω))) :
IsLPFeasible m A Δ (fun j => ∫ ω, P j ω ∂Pr)
(fun j => ∫ ω, (pol (fun k => P k ω) j + P j ω) ∂Pr) ∧
∀ C : V → ℝ, IsLPOptimal m A Δ (fun j => ∫ ω, P j ω ∂Pr) w C →
∑ j, w j * C j ≤ ∫ ω, ∑ j, w j * (pol (fun k => P k ω) j + P 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. 797, §3, paragraph "Observe that under any scheduling policy Π" and the LP relaxation
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.