Lemma 1, p. 207 — in a reversed Leontief network,
ProvedMaxPressure.ReversedLeontief.extremeAllocs_eq_intAllocsextreme-allocationinteger-allocationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reversed-leontief
A stochastic processing network is reversed Leontief if each activity requires exactly one processor. For a reversed Leontief network satisfying the standing assumptions of §2, every extreme allocation is an integer allocation, and conversely:
Consequently, maximum pressure policies in reversed Leontief networks never split a processor's capacity, and the throughput optimality of maximum pressure policies (Theorem 2 of the paper) carries over to the non-processor-splitting setting.
Preamble
import Mathlib import Definitions.Def_MaxPressure_ReversedLeontief_Network
Formal statement
namespace MaxPressure.ReversedLeontief
/-- Lemma 1, p. 207: for a reversed Leontief network, every extreme allocation is an integer
allocation; i.e., `ℰ = 𝒩`. -/
theorem extremeAllocs_eq_intAllocs {I J K : ℕ} (N : Network I J K) (hN : N.Standing)
(hRL : IsReversedLeontief N) :
extremeAllocs N = intAllocs N := by sorry
end MaxPressure.ReversedLeontief
Source
Dai & Lin, Maximum pressure policies in stochastic processing networks, Oper. Res. 53(2) (2005), p. 207, Lemma 1 (proof p. 215, Appendix B)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.