Lemma 3.3, p. 797 — (1/m) Σ_{k≤j} E[P_k] ≤ (1 + max{1, (m−1)Δ/m}) C^LP_j for points sorted by C^LP
ProvedStochSchedPrec.CMNS.lemma_3_3load-inequalitieslp-relaxationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , and (). Let satisfy the first and the last set of inequalities of the LP relaxation,
and let be a list along which is nondecreasing. Then for every job
where is the set of jobs up to and including in .
This lemma of Möhring, Schulz and Uetz converts the load-dependent term of Theorem 2.8 into a multiple of the LP value.
Formalization Note The paper has and numbers the jobs so that ; here the numbering is a list sorted by , and is any nonnegative vector.
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_3_3 {V : Type*} [Fintype V] [DecidableEq V]
(m : ℕ) (hm : 0 < m) (Δ : ℝ) (hΔ : 0 ≤ Δ) (μ : V → ℝ) (hμ : ∀ j, 0 ≤ μ j)
(C : V → ℝ) (hload : ∀ W : Finset V, loadFn m Δ μ W ≤ ∑ j ∈ W, μ j * C j)
(hlow : ∀ j, μ j ≤ C j)
(L : Fin (Fintype.card V) ≃ V) (hL : IsSortedBy L C) (j : V) :
1 / (m : ℝ) * ∑ i ∈ before L j, μ i ≤ (1 + max 1 (((m : ℝ) - 1) / m * Δ)) * C j := 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, Lemma 3.3 (citing Möhring, Schulz, Uetz, J. ACM 46 (1999), Lemma 4.2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.