在排隊論 中（運籌學 的一支），傑克遜排隊網絡 （英語：Jackson network ，亦作Jacksonian network [ 1] [ 2] 互聯網 發展中的一些思想亦源於該排隊網絡。[ 3] 詹姆斯·R·傑克遜 [ 4] [ 5] 管理科學 管理科學 頭50年中最具影響力的十篇論文」之一。[ 6]
傑克遜受到了柏克 Reich ）工作的啟發。[ 7] Jean Walrand ）指出「積形式解的結果……從柏克定理推過去不是很直接，並沒有傑克遜本人在他那篇奠基性文章中所認為的那麼直接」。[ 8]
在串聯排隊（有限數量的隊列，顧客按先後順序去每個隊列等候）和環形排隊網絡（串聯成環的若干隊列，顧客按先後順序去每個隊列等候）中，R.R.P. Jackson 更早就發現了一個積形式解。[ 9]
傑克遜網絡包括一定數量的節點，每個節點表示一個隊列，隊列的服務率既可以是狀態無關的（不同的節點有不同的服務率），也可以是狀態相關的（服務率的變化與隊長相關）。任務（jobs ）按照一個固定的路由矩陣（routing matrix ）在節點間轉移。每個節點處的任務都屬於單一的「類」（class ），任務都服從相同都服務時間分布和路由機制。因此，並沒有引入任務服務的優先級：每個節點處的所有工作都以先到先得（FIFS, First In First Severed ）方式進行。
有限任務、閉合網絡的傑克遜網絡也有積形式解，該結論由Gordon–Newell定理闡明。[ 10]
m
{\displaystyle m}
[ 11] [ 12]
若網絡是開放的，任意往節點
i
{\displaystyle i}
泊松過程 ，
服務時間呈指數分布，排隊規則為先到先得（First come first served ），
隊列
i
{\displaystyle i}
P
i
j
{\displaystyle P_{ij}}
j
{\displaystyle j}
1
−
∑
j
=
1
m
P
i
j
{\displaystyle 1-\sum _{j=1}^{m}P_{ij}}
所有隊列的利用率都小於1。
m
{\displaystyle m}
M/M/1模型 的開放傑克遜網絡，其中利用率（utilization ）
ρ
i
{\displaystyle \rho _{i}}
(
k
1
,
k
2
,
…
,
k
m
)
{\displaystyle \scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}}
equilibrium state ）概率分布由每個隊列的平衡分布之積給出：
π
(
k
1
,
k
2
,
…
,
k
m
)
=
∏
i
=
1
m
π
i
(
k
i
)
=
∏
i
=
1
m
[
ρ
i
k
i
(
1
−
ρ
i
)
]
.
{\displaystyle \pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})=\prod _{i=1}^{m}[\rho _{i}^{k_{i}}(1-\rho _{i})].}
結果
π
(
k
1
,
k
2
,
…
,
k
m
)
=
∏
i
=
1
m
π
i
(
k
i
)
{\displaystyle \pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})}
M/M/c 服務站（stations ）也成立，其中第
i
{\displaystyle i}
servers ）數為
c
i
{\displaystyle c_{i}}
ρ
i
<
c
i
{\displaystyle \rho _{i}<c_{i}}
在一個開放網絡中，顧客自系統外部以泊松流方式到達，到達率為
α
>
0
{\displaystyle \alpha >0}
j 的到達是相互獨立的，有概率
p
0
j
≥
0
{\displaystyle p_{0j}\geq 0}
∑
j
=
1
J
p
0
j
=
1
{\displaystyle \sum _{j=1}^{J}p_{0j}=1}
i
{\displaystyle i}
p
i
j
{\displaystyle p_{ij}}
p
i
0
=
1
−
∑
j
=
1
J
p
i
j
{\displaystyle p_{i0}=1-\sum _{j=1}^{J}p_{ij}}
因此，節點
i
{\displaystyle i}
λ
i
{\displaystyle \lambda _{i}}
{\displaystyle }
{\displaystyle }
λ
i
=
α
p
0
i
+
∑
j
=
1
J
λ
j
p
j
i
,
i
=
1
,
…
,
J
.
(
1
)
{\displaystyle \lambda _{i}=\alpha p_{0i}+\sum _{j=1}^{J}\lambda _{j}p_{ji},i=1,\ldots ,J.\qquad (1)}
j
{\displaystyle j}
i
{\displaystyle i}
j
{\displaystyle j}
μ
j
{\displaystyle \mu _{j}}
{\displaystyle }
定義
a
=
(
α
p
0
i
)
i
=
1
J
{\displaystyle a=(\alpha p_{0i})_{i=1}^{J}}
λ
=
(
I
−
P
T
)
−
1
a
{\displaystyle \lambda =(I-P^{T})^{-1}a}
所有任務在後續泊松過程中會離開其節點，節點
i
{\displaystyle i}
x
i
{\displaystyle x_{i}}
μ
i
(
x
i
)
{\displaystyle \mu _{i}(x_{i})}
令
X
i
(
t
)
{\displaystyle X_{i}(t)}
i
{\displaystyle i}
t
{\displaystyle t}
X
=
(
X
i
)
i
=
1
J
{\displaystyle \mathbf {X} =(X_{i})_{i=1}^{J}}
X
{\displaystyle \mathbf {X} }
均衡分布 ，
π
(
x
)
=
P
(
X
=
x
)
{\displaystyle \pi (\mathbf {x} )=P(\mathbf {X} =\mathbf {x} )}
π
(
x
)
∑
i
=
1
J
[
α
p
0
i
+
μ
i
(
x
i
)
(
1
−
p
i
i
)
]
=
∑
i
=
1
J
[
π
(
x
−
e
i
)
α
p
0
i
+
π
(
x
+
e
i
)
μ
i
(
x
i
+
1
)
p
i
0
]
+
∑
i
=
1
J
∑
j
≠
i
π
(
x
+
e
i
−
e
j
)
μ
i
(
x
i
+
1
)
p
i
j
.
(
2
)
{\displaystyle {\begin{aligned}&\pi (\mathbf {x} )\sum _{i=1}^{J}[\alpha p_{0i}+\mu _{i}(x_{i})(1-p_{ii})]\\={}&\sum _{i=1}^{J}[\pi (\mathbf {x} -\mathbf {e} _{i})\alpha p_{0i}+\pi (\mathbf {x} +\mathbf {e} _{i})\mu _{i}(x_{i}+1)p_{i0}]+\sum _{i=1}^{J}\sum _{j\neq i}\pi (\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i}(x_{i}+1)p_{ij}.\qquad (2)\end{aligned}}}
其中
e
i
{\displaystyle \mathbf {e} _{i}}
i
{\displaystyle i}
單位向量 .。
設獨立隨機向量
(
Y
1
,
…
,
Y
J
)
{\displaystyle (Y_{1},\ldots ,Y_{J})}
Y
i
{\displaystyle Y_{i}}
概率質量函數 ：
P
(
Y
i
=
n
)
=
p
(
Y
i
=
0
)
⋅
λ
i
n
M
i
(
n
)
,
(
3
)
{\displaystyle P(Y_{i}=n)=p(Y_{i}=0)\cdot {\frac {\lambda _{i}^{n}}{M_{i}(n)}},\quad (3)}
其中
M
i
(
n
)
=
∏
j
=
1
n
μ
i
(
j
)
{\displaystyle M_{i}(n)=\prod _{j=1}^{n}\mu _{i}(j)}
∑
n
=
1
∞
λ
i
n
M
i
(
n
)
<
∞
{\displaystyle \sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}<\infty }
P
(
Y
i
=
0
)
=
(
1
+
∑
n
=
1
∞
λ
i
n
M
i
(
n
)
)
−
1
{\displaystyle P(Y_{i}=0)=\left(1+\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}\right)^{-1}}
π
(
x
)
=
∏
i
=
1
J
P
(
Y
i
=
x
i
)
.
{\displaystyle \pi (\mathbf {x} )=\prod _{i=1}^{J}P(Y_{i}=x_{i}).}
對所有的
x
∈
Z
+
J
{\displaystyle \mathbf {x} \in {\mathcal {Z}}_{+}^{J}}
三節點的開放傑克遜網絡 設圖中有一三節點的傑克遜網絡，係數分別是：
α
=
5
,
p
01
=
p
02
=
0.5
,
p
03
=
0
,
{\displaystyle \alpha =5,\quad p_{01}=p_{02}=0.5,\quad p_{03}=0,\quad }
P
=
[
0
0.5
0.5
0
0
0
0
0
0
]
,
μ
=
[
μ
1
(
x
1
)
μ
2
(
x
2
)
μ
3
(
x
3
)
]
=
[
15
12
10
]
for all
x
i
>
0
{\displaystyle P={\begin{bmatrix}0&0.5&0.5\\0&0&0\\0&0&0\end{bmatrix}},\quad \mu ={\begin{bmatrix}\mu _{1}(x_{1})\\\mu _{2}(x_{2})\\\mu _{3}(x_{3})\end{bmatrix}}={\begin{bmatrix}15\\12\\10\end{bmatrix}}{\text{ for all }}x_{i}>0}
通過定理，可以計算：
λ
=
(
I
−
P
T
)
−
1
a
=
[
1
0
0
−
0.5
1
0
−
0.5
0
1
]
−
1
[
0.5
×
5
0.5
×
5
0
]
=
[
1
0
0
0.5
1
0
0.5
0
1
]
[
2.5
2.5
0
]
=
[
2.5
3.75
1.25
]
{\displaystyle \lambda =(I-P^{T})^{-1}a={\begin{bmatrix}1&0&0\\-0.5&1&0\\-0.5&0&1\end{bmatrix}}^{-1}{\begin{bmatrix}0.5\times 5\\0.5\times 5\\0\end{bmatrix}}={\begin{bmatrix}1&0&0\\0.5&1&0\\0.5&0&1\end{bmatrix}}{\begin{bmatrix}2.5\\2.5\\0\end{bmatrix}}={\begin{bmatrix}2.5\\3.75\\1.25\end{bmatrix}}}
根據
Y
{\displaystyle \mathbf {Y} }
P
(
Y
1
=
0
)
=
(
∑
n
=
0
∞
(
2.5
15
)
n
)
−
1
=
5
6
{\displaystyle P(Y_{1}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {2.5}{15}}\right)^{n}\right)^{-1}={\frac {5}{6}}}
P
(
Y
2
=
0
)
=
(
∑
n
=
0
∞
(
3.75
12
)
n
)
−
1
=
11
16
{\displaystyle P(Y_{2}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {3.75}{12}}\right)^{n}\right)^{-1}={\frac {11}{16}}}
P
(
Y
3
=
0
)
=
(
∑
n
=
0
∞
(
1.25
10
)
n
)
−
1
=
7
8
{\displaystyle P(Y_{3}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {1.25}{10}}\right)^{n}\right)^{-1}={\frac {7}{8}}}
因此，每個節點處有一個服務的概率是：
π
(
1
,
1
,
1
)
=
5
6
⋅
2.5
15
⋅
11
16
⋅
3.75
12
⋅
7
8
⋅
1.25
10
≈
0.00326
{\displaystyle \pi (1,1,1)={\frac {5}{6}}\cdot {\frac {2.5}{15}}\cdot {\frac {11}{16}}\cdot {\frac {3.75}{12}}\cdot {\frac {7}{8}}\cdot {\frac {1.25}{10}}\approx 0.00326}
由於這裡的服務率是狀態無關的，
Y
i
{\displaystyle Y_{i}}
幾何分布 。
推廣的傑克遜網絡 允許更新到達過程 積形式穩定解 [ 13]
在一些平和的條件下，開放的推廣傑克遜網絡的隊長過程
{\displaystyle }
{\displaystyle }
反射布朗運動
R
B
M
Q
(
0
)
(
θ
,
Γ
;
R
)
{\displaystyle RBM_{Q(0)}(\theta ,\Gamma ;R)}
θ
{\displaystyle \theta }
drift ），
Γ
{\displaystyle \Gamma }
R
{\displaystyle R}
homogeneous fluid network ）的推廣傑克遜網絡和反射布朗運動間的關係得到的。
反射布朗過程的參數如下所述：
θ
=
α
−
(
I
−
P
T
)
μ
{\displaystyle \theta =\alpha -(I-P^{T})\mu }
Γ
=
(
Γ
k
l
)
{\displaystyle \Gamma =(\Gamma _{kl})}
Γ
k
l
=
∑
j
=
1
J
(
λ
j
∧
μ
j
)
[
p
j
k
(
δ
k
l
−
p
j
l
)
+
c
j
2
(
p
j
k
−
δ
j
k
)
(
p
j
l
−
δ
j
l
)
]
+
α
k
c
0
,
k
2
δ
k
l
{\displaystyle \Gamma _{kl}=\sum _{j=1}^{J}(\lambda _{j}\wedge \mu _{j})[p_{jk}(\delta _{kl}-p_{jl})+c_{j}^{2}(p_{jk}-\delta _{jk})(p_{jl}-\delta _{jl})]+\alpha _{k}c_{0,k}^{2}\delta _{kl}}
R
=
I
−
P
T
{\displaystyle R=I-P^{T}}
其中符號的定義：
近似公式中符號的定義
符號
含義
α
=
(
α
j
)
j
=
1
J
{\displaystyle \alpha =(\alpha _{j})_{j=1}^{J}}
J維向量，每個節點的到達率
μ
=
(
μ
)
j
=
1
J
{\displaystyle \mu =(\mu )_{j=1}^{J}}
J維向量，每個節點的服務率
P
{\displaystyle P}
轉移矩陣
λ
j
{\displaystyle \lambda _{j}}
第j個節點的有效到達
c
j
{\displaystyle c_{j}}
第j個節點服務時間的變異係數
c
0
,
j
{\displaystyle c_{0,j}}
第j個節點服務台間轉移到達時間的變異係數
δ
i
j
{\displaystyle \delta _{ij}}
反映節點間關係的係數
^ Walrand, J. ; Varaiya, P. Sojourn Times and the Overtaking Condition in Jacksonian Networks. Advances in Applied Probability. 1980, 12 (4): 1000–1018. JSTOR 1426753 doi:10.2307/1426753 ^ Kelly, F. P. Networks of Queues. Advances in Applied Probability. June 1976, 8 (2): 416–432. JSTOR 1425912 doi:10.2307/1425912 ^ Jackson, James R. Comments on "Jobshop-Like Queueing Systems": The Background. Management Science . December 2004, 50 (12): 1796–1802. JSTOR 30046150 doi:10.1287/mnsc.1040.0268 ^ Jackson, James R. Jobshop-like Queueing Systems. Management Science . Oct 1963, 10 (1): 131–142. JSTOR 2627213 doi:10.1287/mnsc.1040.0268 http://www.dtic.mil/dtic/tr/fulltext/u2/296776.pdf （頁面存檔備份 ，存於網際網路檔案館 ）^ Jackson, J. R. Networks of Waiting Lines. Operations Research. 1957, 5 (4): 518–521. JSTOR 167249 doi:10.1287/opre.5.4.518 ^ Jackson, James R. Jobshop-Like Queueing Systems. Management Science . December 2004, 50 (12): 1796–1802. JSTOR 30046149 doi:10.1287/mnsc.1040.0268 ^ Reich, Edgar. Waiting Times When Queues are in Tandem . Annals of Mathematical Statistics . September 1957, 28 (3): 768. JSTOR 2237237 doi:10.1214/aoms/1177706889 ^ Walrand, Jean. A Probabilistic Look at Networks of Quasi-Reversible Queues. IEEE Transactions on Information Theory . November 1983, 29 (6): 825. doi:10.1109/TIT.1983.1056762 ^ Jackson, R. R. P. Book review: Queueing networks and product forms: a systems approach. IMA Journal of Management Mathematics. 1995, 6 (4): 382–384. doi:10.1093/imaman/6.4.382 ^ Gordon, W. J.; Newell, G. F. Closed Queuing Systems with Exponential Servers. Operations Research . 1967, 15 (2): 254. JSTOR 168557 doi:10.1287/opre.15.2.254 ^ Goodman, Jonathan B.; Massey, William A. The Non-Ergodic Jackson Network. Journal of Applied Probability. December 1984, 21 (4): 860–869. doi:10.2307/3213702 ^ Walrand, J.; Varaiya, P. Sojourn Times and the Overtaking Condition in Jacksonian Networks. Advances in Applied Probability. December 1980, 12 (4): 1000–1018. doi:10.2307/1426753 ^ Chen, Hong; Yao, David D. Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer. 2001. ISBN 0-387-95166-0
![{\displaystyle \pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})=\prod _{i=1}^{m}[\rho _{i}^{k_{i}}(1-\rho _{i})].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c9cb3ffbe3a81de75cfbc30bbfe828c5ee75e34)
![{\displaystyle {\begin{aligned}&\pi (\mathbf {x} )\sum _{i=1}^{J}[\alpha p_{0i}+\mu _{i}(x_{i})(1-p_{ii})]\\={}&\sum _{i=1}^{J}[\pi (\mathbf {x} -\mathbf {e} _{i})\alpha p_{0i}+\pi (\mathbf {x} +\mathbf {e} _{i})\mu _{i}(x_{i}+1)p_{i0}]+\sum _{i=1}^{J}\sum _{j\neq i}\pi (\mathbf {x} +\mathbf {e} _{i}-\mathbf {e} _{j})\mu _{i}(x_{i}+1)p_{ij}.\qquad (2)\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf9a9294ac3a056f8f9844aca3c3ab4a48c2263c)
.png)
![{\displaystyle \Gamma _{kl}=\sum _{j=1}^{J}(\lambda _{j}\wedge \mu _{j})[p_{jk}(\delta _{kl}-p_{jl})+c_{j}^{2}(p_{jk}-\delta _{jk})(p_{jl}-\delta _{jl})]+\alpha _{k}c_{0,k}^{2}\delta _{kl}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c665ffe0ea2cc388e69428c1e21ff8bf24813996)
