Observation 2.4, p. 794 — CMNS charges each job at most βE[P_j], charges in [r_j(p), S_j(p)[ go to B_j, and no deliberate idle time is uncharged
ProvedStochSchedPrec.CMNS.observation_2_4deliberate-idle-timelist-schedulingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-scheduling
Consider an instance with machines, acyclic precedence constraints and release dates satisfying Assumption 2.1 ( whenever is a predecessor of ). Let be a priority list, , (the expected processing times in the paper), a realization, and the schedule constructed by Algorithm CMNS. Then for every job :
- job is charged no more than deliberate idle time: for all ;
- the deliberate idle time in is charged only to jobs in : a job deliberately delayed at a time lies in ;
- there is no uncharged deliberate idle time: whenever a machine is idle at while some job of the residual list is available, some job is deliberately delayed at , so the idle machines' time is charged to it.
These three facts are what the completion-time bound of Lemma 2.5 uses about the algorithm.
Formalization Note The paper states the observation for ; the statement here holds for every nonnegative threshold vector , since the algorithm uses only through the threshold. Assumption 2.1 is the standing assumption of §2 and is carried as a hypothesis.
Preamble
import Mathlib import Definitions.Def_StochSchedPrec_CMNS_Model import Definitions.Def_StochSchedPrec_CMNS_Algorithm open MeasureTheory ProbabilityTheory
Formal statement
namespace StochSchedPrec.CMNS
theorem observation_2_4 {V : Type*} [Fintype V] [DecidableEq V]
(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)
(L : Fin (Fintype.card V) ≃ V) (β : ℝ) (hβ : 0 ≤ β) (μ : V → ℝ) (hμ : ∀ j, 0 ≤ μ j)
(p : V → ℝ) (hp : ∀ j, 0 ≤ p j) (S : V → ℝ) (hS : IsCMNSRun m A r L β μ p S) :
(∀ (j : V) (t : ℝ), charge m A r L p S j t ≤ β * μ j) ∧
(∀ (j : V) (t : ℝ), availTime A r p S j ≤ t → t < S j →
∀ k, IsDelayed A r L p S k t → k ∈ before L j) ∧
(∀ t : ℝ, busy p S t < m → (∃ i, t < S i ∧ avail A r p S i t) →
∃ k, IsDelayed A r L p S k t) := by sorry
end StochSchedPrec.CMNS
Source
Skutella and Uetz, Stochastic machine scheduling with precedence constraints, SIAM J. Comput. 34(4) (2005) 788–802, p. 794, Observation 2.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.