傑克遜排隊網路

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

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

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

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

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

## 傑克遜排隊網路的必要條件

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

- 若網路是開放的，任意往節點$i$的外部到達都是一個泊松過程。
- 服務時間呈指數分布，排隊規則為先到先得（First come first served）。
- 隊列$i$處的顧客服務結束後，以機率$P_{ij}$轉移到新的隊列$j$或以機率$1-\sum_{j=1}^{m}P_{ij}$離開隊列；對於開放網路來說，離開機率對所有隊列的某個子集是非零的。
- 所有隊列的利用率都小於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}\ge0$且滿足$\sum_{j=1}^J p_{0j}=1$。當節點$i$處的服務完成時，顧客會以機率$p_{ij}$進入另一節點或者以$p_{i0}=1-\sum_{j=1}^J p_{ij}$的機率離開網路。

因此，節點$i$的總到達率$\lambda_i$是外部到達和內部轉移的總和：

$$\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$。）

定義 $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{align} & \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\ne i}\pi(\mathbf{x}+\mathbf{e}_i-\mathbf{e}_j)\mu_i(x_i+1)p_{ij}.\qquad (2) \end{align}$$

其中$\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$。

### 例

<image>

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

$$\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\times5\\ 0.5\times5\\ 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$$

其中符號的定義：

符號｜含義

$\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^0_{ij})$，滿足對所有的$i,j\in \{1,\dots,J\}$都有$\Gamma^0_{ij}=\alpha_i c_{0,i}^2 \delta_{ij}$。