杰克逊排队网络

在排隊論中（運籌學的一支），**傑克遜排隊網絡**（英語：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}$ 是外部到達和內部轉移的總和： $$ $$

（因為每個節點的利用率均小於 1，且我們觀察的是均衡分布，即長時間運行的平均行為，任務從 $j$ 轉移到 $i$ 速率的界不超過 $j$ 到達率的一部分，我們由此忽略上式中的服務率 $\mu _{j}$ 。） $$
定義 $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}$ 各項服從簡單的幾何分布。

## 傑克遜網絡的推廣

**推廣的傑克遜網絡**允許更新到達過程不一定是一個泊松過程，也允許服務時間是獨立且同種的非指數分布。一般地，網絡不一定要有積形式穩定解，因此需要找近似解

### 布朗近似

在一些平和的條件下，開放的推廣傑克遜網絡的隊長過程 $$ Q(t) $$ 可以用反射布朗運動近似，定義為 $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}$

其中符號的定義：

## 參見

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

## 參考文獻