Lemma 5, p. 214 — maximum-pressure fluid-limit equations (52)–(55)
ProvedMaxPressure.Throughput.extended_fluid_limit_equationsfluid-limitmaximum-pressurep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Assume EAA and take a fluid limit of a preemptive, processor-splitting maximum-pressure process, retaining the allocation-time coordinates for all extreme allocations . It satisfies the fluid network equations and
At every positive time when has strictly smaller pressure than some extreme allocation, has derivative zero. This is (55), including existence of that derivative. These relations are the policy-specific input to Lemma 4.
Formalization Note The fluid network predicate also includes (18), which follows from (52)–(54) and the same fluid-limit construction. The sum uses a finite set exactly equal to the paper's extreme allocations.
Preamble
import Mathlib import Definitions.Def_MaxPressure_Throughput_Dynamics
Formal statement
namespace MaxPressure.Throughput
/-- Lemma 5, p. 214: an extended maximum-pressure fluid limit satisfies
(14)–(17), (52)–(55). The derivative clause includes its existence when
the allocation is strictly dominated. -/
theorem extended_fluid_limit_equations {I J K : ℕ} {Ω : Type*}
(N : Network I J K) (hN : N.Standing) (hEAA : EAA N)
(E : Finset (Fin J → ℝ)) (hE : (E : Set (Fin J → ℝ)) = extremeAllocs N)
(P : Primitives I J Ω) (Z : Ω → ℝ → Fin I → ℝ)
(Ta : Ω → (Fin J → ℝ) → ℝ → ℝ) (ω : Ω)
(heq : NetworkEquations N P Z (activityTime E Ta) ω)
(hmp : MPProcess N E Z Ta ω)
(Zb : ℝ → Fin I → ℝ) (Tb : ℝ → Fin J → ℝ)
(Tab : (Fin J → ℝ) → ℝ → ℝ)
(hlim : IsMPFluidLimit N P E Z Ta ω Zb Tb Tab) :
IsFluidSolution N Zb Tb ∧
(∀ t, 0 ≤ t → ∀ j, Tb t j = ∑ a ∈ E, a j * Tab a t) ∧
(∀ a ∈ E, MonotoneOn (Tab a) (Set.Ici (0 : ℝ))) ∧
(∀ t, 0 ≤ t → ∑ a ∈ E, Tab a t = t) ∧
(∀ t, 0 < t → ∀ a ∈ E,
(∃ a' ∈ E, pressure N a (Zb t) < pressure N a' (Zb t)) →
HasDerivAt (Tab a) 0 t) := by sorry
end MaxPressure.Throughput
Source
Dai & Lin, Maximum pressure policies in stochastic processing networks, Oper. Res. 53(2) (2005), p. 214, Lemma 5, (52)–(55); https://doi.org/10.1287/opre.1040.0170
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.