傑克遜排隊網絡

在排隊論中（運籌學的一支），傑克遜排隊網絡（英語：Jackson network，亦作Jacksonian network）是一類排隊網絡模型，其均衡分布計算形式簡單且網絡具有積形式解。該模型已被推廣，其定理的思想也被運用於尋找其他網絡中類似的積形式解。網際網路發展中的一些思想亦源於該排隊網絡。這一網絡模型首先由詹姆斯·R·傑克遜提出。2004年，傑克遜的文章重載於《管理科學》，該刊將其譽為「管理科學頭50年中最具影響力的十篇論文」之一。

傑克遜受到了柏克和賴克（Reich）工作的啟發。但吉恩·華爾蘭德（Jean Walrand）指出「積形式解的結果……從柏克定理推過去不是很直接，並沒有傑克遜本人在他那篇奠基性文章中所認為的那麼直接」。

在串聯排隊（有限數量的隊列，顧客按先後順序去每個隊列等候）和環形排隊網絡（串聯成環的若干隊列，顧客按先後順序去每個隊列等候）中，R.R.P. Jackson更早就發現了一個積形式解。

傑克遜網絡包括一定數量的節點，每個節點表示一個隊列，隊列的服務率既可以是狀態無關的（不同的節點有不同的服務率），也可以是狀態相關的（服務率的變化與隊長相關）。任務（jobs）按照一個固定的路由矩陣（routing matrix）在節點間轉移。每個節點處的任務都屬於單一的「類」（class），任務都服從相同都服務時間分布和路由機制。因此，並沒有引入任務服務的優先級：每個節點處的所有工作都以先到先得（FIFS, First In First Severed）方式進行。

有限任務、閉合網絡的傑克遜網絡也有積形式解，該結論由Gordon–Newell定理闡明。

傑克遜排隊網絡的必要條件

$m$個相連隊列組成的網絡被稱作傑克遜網絡，若它滿足下述條件：

1. 若網絡是開放的，任意往節點$i$的外部到達都是一個泊松過程，
2. 服務時間呈指數分布，排隊規則為先到先得（First come first served），
3. 隊列$i$處的顧客服務結束後，以概率$P_{ij}$轉移到新的隊列$j$或以概率$1-\sum _{j=1}^{m}P_{ij}$離開隊列；對於開放網絡來說，離開概率對所有隊列的某個子集是非零的，
4. 所有隊列的利用率都小於1。

定理

$m$為M/M/1模型的開放傑克遜網絡，其中利用率（utilization）$\rho _{i}$對每個隊列都小於1，平衡狀態概率分布存在，且對狀態$\scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}$，平衡狀態（equilibrium state）概率分布由每個隊列的平衡分布之積給出：

$\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})].$

結果$\pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})$對M/M/c服務站（stations）也成立，其中第$i$個節點的服務台（servers）數為$c_{i}$，利用率滿足$\rho _{i}<c_{i}$。

定義

在一個開放網絡中，顧客自系統外部以泊松流方式到達，到達率為$\alpha >0$。每個往節點j的到達是相互獨立的，有概率 $p_{0j}\geq 0$且滿足$\sum _{j=1}^{J}p_{0j}=1$。當節點$i$處的服務完成時，顧客會以概率$p_{ij}$進入另一節點或者以$p_{i0}=1-\sum _{j=1}^{J}p_{ij}$的概率離開網絡。

因此，節點$i$的總到達率$\lambda _{i}$是外部到達和內部轉移的總和：${\displaystyle }$${\displaystyle }$$$\lambda _{i}=\alpha p_{0i}+\sum _{j=1}^{J}\lambda _{j}p_{ji},i=1,\ldots ,J.\qquad (1)$$（因為每個節點的利用率均小於1，且我們觀察的是均衡分布，即長時間運行的平均行為，任務從$j$轉移到$i$速率的界不超過$j$到達率的一部分，我們由此忽略上式中的服務率$\mu _{j}$。）${\displaystyle }$

定義 $a=(\alpha p_{0i})_{i=1}^{J}$，我們就可以解出$\lambda =(I-P^{T})^{-1}a$。

所有任務在後續泊松過程中會離開其節點，節點$i$處有$x_{i}$個任務，定義其服務率為$\mu _{i}(x_{i})$。

令$X_{i}(t)$表示節點$i$在時間$t$的任務數，$\mathbf {X} =(X_{i})_{i=1}^{J}$。$\mathbf {X}$的均衡分布，$\pi (\mathbf {x} )=P(\mathbf {X} =\mathbf {x} )$由如下系統平衡方程給出：

${\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}}$

其中$\mathbf {e} _{i}$表示第$i$個單位向量.。

定理

設獨立隨機向量$(Y_{1},\ldots ,Y_{J})$，每個$Y_{i}$都有概率質量函數：

$P(Y_{i}=n)=p(Y_{i}=0)\cdot {\frac {\lambda _{i}^{n}}{M_{i}(n)}},\quad (3)$

其中$M_{i}(n)=\prod _{j=1}^{n}\mu _{i}(j)$。當$\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}<\infty$即$P(Y_{i}=0)=\left(1+\sum _{n=1}^{\infty }{\frac {\lambda _{i}^{n}}{M_{i}(n)}}\right)^{-1}$是良定義的，開放傑克遜網絡的平衡分布有如下的積形式：

$\pi (\mathbf {x} )=\prod _{i=1}^{J}P(Y_{i}=x_{i}).$

對所有的$\mathbf {x} \in {\mathcal {Z}}_{+}^{J}$。

例

三節點的開放傑克遜網絡

設圖中有一三節點的傑克遜網絡，係數分別是：

$\alpha =5,\quad p_{01}=p_{02}=0.5,\quad p_{03}=0,\quad$

$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$

通過定理，可以計算：

$\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}}$

根據$\mathbf {Y}$的定義，有：

$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)=\left(\sum _{n=0}^{\infty }\left({\frac {3.75}{12}}\right)^{n}\right)^{-1}={\frac {11}{16}}$

$P(Y_{3}=0)=\left(\sum _{n=0}^{\infty }\left({\frac {1.25}{10}}\right)^{n}\right)^{-1}={\frac {7}{8}}$

因此，每個節點處有一個服務的概率是：

$\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 }$Q(t)${\displaystyle }$可以用反射布朗運動近似，定義為$RBM_{Q(0)}(\theta ,\Gamma ;R)$，其中$\theta$是過程的漂移（drift），$\Gamma$是協方差矩陣，$R$是反射矩陣。這一二階近似是從均質流體（homogeneous fluid network）的推廣傑克遜網絡和反射布朗運動間的關係得到的。

反射布朗過程的參數如下所述：

$\theta =\alpha -(I-P^{T})\mu$

$\Gamma =(\Gamma _{kl})$有$\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}$

其中符號的定義：

近似公式中符號的定義

符號	含義
$\alpha =(\alpha _{j})_{j=1}^{J}$	J維向量，每個節點的到達率
$\mu =(\mu )_{j=1}^{J}$	J維向量，每個節點的服務率
$P$	轉移矩陣
$\lambda _{j}$	第j個節點的有效到達
$c_{j}$	第j個節點服務時間的變異係數
$c_{0,j}$	第j個節點服務台間轉移到達時間的變異係數
$\delta _{ij}$	反映節點間關係的係數 它們是這樣定義的：令$A(t)$為系統的到達過程，則在分布中有$A(t)-\alpha t{}\approx {\hat {A}}(t)$，其中${\hat {A}}(t)$是一個無漂移（driftless）的布朗過程，其協方差矩陣為$\Gamma ^{0}=(\Gamma _{ij}^{0})$，滿足對所有的$i,j\in \{1,\dots ,J\}$都有$\Gamma _{ij}^{0}=\alpha _{i}c_{0,i}^{2}\delta _{ij}$。

參見

• Gordon–Newell網絡
• BCMP網絡
• G-網絡
• Little法則