Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§4, proof of Theorem (4.5), second claim — (4.6) satisfies equations (3.1)

Proved
JacksonJobshop.Equilibrium.product_form_satisfies_balance

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

balance-equationsp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1product-formqueueing-theory

Let (N,L,M,R)(N, L, M, R)(N,L,M,R) be a jobshop-like queueing system satisfying Assumptions (2.1)–(2.4), and let p(kˉ)=π w(kˉ) W(S(kˉ))p(\bar k) = \pi\, w(\bar k)\, W(S(\bar k))p(kˉ)=πw(kˉ)W(S(kˉ)) be the function (4.6). Then P(kˉ,t)≡p(kˉ)P(\bar k, t) \equiv p(\bar k)P(kˉ,t)≡p(kˉ) is a constant solution of the balance equations (3.1): for every state vector kˉ\bar kkˉ,

0=−[λ(S(kˉ))∑n=1Nr(0,n)+∑nμ(n,kn)(1−r(n,n))]p(kˉ)+∑nλ(S(kˉ)−1) r(0,n) p(hˉ(n))+∑nμ(n,kn+1) r(n,N+1) p(lˉ(n))+∑m≠nμ(n,kn+1) r(n,m) p(jˉ(m,n)),0 = -\Big[\lambda(S(\bar k))\sum_{n=1}^N r(0, n) + \sum_{n} \mu(n, k_n)\big(1 - r(n, n)\big)\Big] p(\bar k) + \sum_n \lambda(S(\bar k) - 1)\, r(0, n)\, p(\bar h(n)) + \sum_n \mu(n, k_n + 1)\, r(n, N+1)\, p(\bar l(n)) + \sum_{m \ne n} \mu(n, k_n + 1)\, r(n, m)\, p(\bar j(m, n)),0=−[λ(S(kˉ))n=1∑N​r(0,n)+n∑​μ(n,kn​)(1−r(n,n))]p(kˉ)+n∑​λ(S(kˉ)−1)r(0,n)p(hˉ(n))+n∑​μ(n,kn​+1)r(n,N+1)p(lˉ(n))+m=n∑​μ(n,kn​+1)r(n,m)p(jˉ​(m,n)),

with the conventions of (3.1): sums over [1,N][1, N][1,N], terms whose state argument has a negative component omitted.

This is the second verification the paper names as the proof of Theorem (4.5), and the substantive one.

Formalization Note The paper prints λ(S(kˉ))\lambda(S(\bar k))λ(S(kˉ)) as the arrival-outflow coefficient in (3.1); this is inconsistent with its own transition probabilities on p. 134 whenever r(0,N+1)>0r(0, N+1) > 0r(0,N+1)>0, and we use λ(S(kˉ))∑nr(0,n)\lambda(S(\bar k)) \sum_n r(0, n)λ(S(kˉ))∑n​r(0,n), which is the equation those transition probabilities give. With the printed coefficient the claim is false (e.g. N=1N = 1N=1, r(0,1)=r(0,2)=1/2r(0,1) = r(0,2) = 1/2r(0,1)=r(0,2)=1/2, r(1,2)=1r(1,2) = 1r(1,2)=1, constant rates, at kˉ=0\bar k = 0kˉ=0). The statement carries no hypothesis on π\piπ: the equations are linear in ppp.

Preamble
import Mathlib
import Definitions.Def_JacksonJobshop_Equilibrium_System
Formal statement
namespace JacksonJobshop.Equilibrium

/-- Jackson (1963), p. 136, second claim of the proof sentence before Theorem (4.5): the
function (4.6) `p(k) = π w(k) W(S(k))` satisfies the stationary equations (3.1) (with the
arrival-outflow coefficient `λ(S(k)) Σ_n r(0, n)`) at every state vector. -/
theorem product_form_satisfies_balance {N : ℕ} (sys : JobshopSystem N) :
    ∀ k, Balance sys (productForm sys) k := by sorry

end JacksonJobshop.Equilibrium
Source
Jackson, Jobshop-Like Queueing Systems, Management Science 10(1) (1963), p. 136, §4, sentence before Theorem (4.5), second claim; equations (3.1), p. 135
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting. Take any NNN and any jobshop system (λ,μ,r,e)(\lambda,\mu,r,e)(λ,μ,r,e) with NNN centers. Its assumptions are:

  • N>0N>0N>0;
  • λ(K)>0\lambda(K)>0λ(K)>0 for all KKK, or λ\lambdaλ is positive up to some K0K_0K0​ and zero after it;
  • μ(n,0)=0\mu(n,0)=0μ(n,0)=0 and μ(n,k)>0\mu(n,k)>0μ(n,k)>0 for k≥1k\ge1k≥1;
  • rrr has non-negative entries, and each row sums to 111 (index 000 is the source, index N+1N+1N+1 is the exit);
  • e≥0e\ge0e≥0 is the unique solution of e(n)=r(0,n)+∑me(m)r(m,n)e(n)=r(0,n)+\sum_m e(m)r(m,n)e(n)=r(0,n)+∑m​e(m)r(m,n).

The function ppp. Let p(k)=π w(k) W(S(k))p(k)=\pi\,w(k)\,W(S(k))p(k)=πw(k)W(S(k)), where

W(K)=∏i=0K−1λ(i),w(k)=∏n=1N∏i=1kne(n)μ(n,i),W(K)=\prod_{i=0}^{K-1}\lambda(i),\qquad w(k)=\prod_{n=1}^N\prod_{i=1}^{k_n}\frac{e(n)}{\mu(n,i)},W(K)=i=0∏K−1​λ(i),w(k)=n=1∏N​i=1∏kn​​μ(n,i)e(n)​,

S(k)=∑nknS(k)=\sum_n k_nS(k)=∑n​kn​, and π=(∑KW(K)T(K))−1\pi=\big(\sum_K W(K)T(K)\big)^{-1}π=(∑K​W(K)T(K))−1 if the series is summable and 000 otherwise, with T(K)=∑S(k)=Kw(k)T(K)=\sum_{S(k)=K}w(k)T(K)=∑S(k)=K​w(k).

Claim. At every state k∈NNk\in\mathbb N^Nk∈NN the following equation holds (δn\delta_nδn​ is the nnn-th unit vector):

0=−(λ(S(k))∑n=1Nr(0,n)+∑n=1Nμ(n,kn)(1−r(n,n)))p(k)+∑n: kn>0λ(S(k)−1) r(0,n) p(k−δn)+∑n=1Nμ(n,kn+1) r(n,N+1) p(k+δn)+∑m≠nkm>0μ(n,kn+1) r(n,m) p(k−δm+δn).\begin{aligned} 0 = {}&-\Big(\lambda(S(k))\sum_{n=1}^N r(0,n)+\sum_{n=1}^N \mu(n,k_n)(1-r(n,n))\Big)p(k) +\sum_{n:\,k_n>0}\lambda(S(k)-1)\,r(0,n)\,p(k-\delta_n)\\ &+\sum_{n=1}^N\mu(n,k_n+1)\,r(n,N+1)\,p(k+\delta_n) +\sum_{\substack{m\ne n\\ k_m>0}}\mu(n,k_n+1)\,r(n,m)\,p(k-\delta_m+\delta_n). \end{aligned}0=​−(λ(S(k))n=1∑N​r(0,n)+n=1∑N​μ(n,kn​)(1−r(n,n)))p(k)+n:kn​>0∑​λ(S(k)−1)r(0,n)p(k−δn​)+n=1∑N​μ(n,kn​+1)r(n,N+1)p(k+δn​)+m=nkm​>0​∑​μ(n,kn​+1)r(n,m)p(k−δm​+δn​).​

The claim asserts only these equations. It does not assert that ppp is non-negative, summable, or normalised.

Degenerate cases. There is no hypothesis on π\piπ. If ∑KW(K)T(K)\sum_K W(K)T(K)∑K​W(K)T(K) is not summable, then π=0\pi=0π=0, so p≡0p\equiv0p≡0 and every equation reads 0=00=00=0. At k=0k=0k=0, the terms with kn>0k_n>0kn​>0 or km>0k_m>0km​>0 are absent. The natural-number subtractions only appear in terms where they do not truncate.

Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me