Lemma 3.3, p. 797 — (1/m) Σ_{k≤j} E[P_k] ≤ (1 + max{1, (m−1)Δ/m}) C^LP_j
ProvedStochSchedPrec.InForest.lemma_3_3lp-relaxationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-scheduling
Let , , and let () be the expected processing times. Let satisfy the first and the last set of inequalities of the LP-relaxation,
and let be a priority list along which is nondecreasing. Then for every job , with the jobs up to and including in ,
The lemma converts the LP solution into a bound on the total expected work ahead of each job in the list, which is the second term in Lemma 4.4.
Formalization Note The page writes the jobs as with and sums over ; here this is the prefix of a list sorted by .
Preamble
import Mathlib import Definitions.Def_StochSchedPrec_InForest_LP
Formal statement
namespace StochSchedPrec.InForest
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, f μ m Δ W ≤ ∑ j ∈ W, μ j * C j)
(hlow : ∀ j, μ j ≤ C j)
(L : Fin (Fintype.card V) ≃ V) (hL : StochSchedPrec.CMNS.IsSortedBy L C) (j : V) :
1 / (m : ℝ) * ∑ k ∈ Bset L j, μ k ≤ (1 + max 1 (((m : ℝ) - 1) / m * Δ)) * C j := by sorry
end StochSchedPrec.InForest
Source
Skutella and Uetz, Stochastic machine scheduling with precedence constraints, SIAM J. Comput. 34(4) (2005) 788–802, p. 797, Lemma 3.3 (see [15, Lemma 4.2])
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.