杰克逊排队网络

在排队论中（运筹学的一支），杰克逊排队网络（Template:Lang-en，亦作Template:Lang）是一类排队网络模型，其均衡分布计算形式简单且网络具有积形式解。该模型已被推广，其定理的思想也被运用于寻找其他网络中类似的积形式解。互联网发展中的一些思想亦源于该排队网络。这一网络模型首先由Template:Tsl提出。2004年，杰克逊的文章重载于《Template:Tsl》，该刊将其誉为“管理科学头50年中最具影响力的十篇论文”之一。

杰克逊受到了Template:Translink和赖克（Template:Lang）工作的启发。但吉恩·华尔兰德（Template:Lang）指出“积形式解的结果……从柏克定理推过去不是很直接，并没有杰克逊本人在他那篇奠基性文章中所认为的那么直接”。

在串联排队（有限数量的队列，顾客按先后顺序去每个队列等候）和环形排队网络（串联成环的若干队列，顾客按先后顺序去每个队列等候）中，Template:Lang更早就发现了一个积形式解。

杰克逊网络包括一定数量的节点，每个节点表示一个队列，队列的服务率既可以是状态无关的（不同的节点有不同的服务率），也可以是状态相关的（服务率的变化与队长相关）。任务（Template:Lang）按照一个固定的路由矩阵（Template:Lang）在节点间转移。每个节点处的任务都属于单一的“类”（Template:Lang），任务都服从相同都服务时间分布和路由机制。因此，并没有引入任务服务的优先级：每个节点处的所有工作都以先到先得（Template:Lang）方式进行。

有限任务、闭合网络的杰克逊网络也有积形式解，该结论由Gordon–Newell定理阐明。

杰克逊排队网络的必要条件

$m$个相连队列组成的网络被称作杰克逊网络，若它满足下述条件：

1. 若网络是开放的，任意往节点$i$的外部到达都是一个泊松过程，
2. 服务时间呈指数分布，排队规则为先到先得（Template:Lang），
3. 队列$i$处的顾客服务结束后，以概率$P_{ij}$转移到新的队列$j$或以概率$1-\sum _{j=1}^m{P}_{ij}$离开队列；对于开放网络来说，离开概率对所有队列的某个子集是非零的，
4. 所有队列的利用率都小于1。

定理

$m$为M/M/1模型的开放杰克逊网络，其中利用率（Template:Lang）${\rho }_i$对每个队列都小于1，平衡状态概率分布存在，且对状态$(k_1,k_2,\dots ,k_m)$，平衡状态（Template:Lang）概率分布由每个队列的平衡分布之积给出：

$\pi (k_1,k_2,\dots ,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,\dots ,k_m)=\prod _{i=1}^m{\pi }_i(k_i)$对M/M/c服务站（Template:Lang）也成立，其中第$i$个节点的服务台（Template:Lang）数为$c_i$，利用率满足${\rho }_i<c_i$。

定义

在一个开放网络中，顾客自系统外部以泊松流方式到达，到达率为$\alpha >0$。每个往节点j的到达是相互独立的，有概率 $p_{0j}\ge 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,\dots ,J.(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$的任务数，$𝐗=(X_i{)}_{i=1}^J$。$𝐗$的均衡分布，$\pi (𝐱)=P(𝐗=𝐱)$由如下系统平衡方程给出：

$\begin{array}{cc}& \pi (𝐱)\sum _{i=1}^J[\alpha p_{0i}+{\mu }_i(x_i)(1-p_{ii})]\\ =& \sum _{i=1}^J[\pi (𝐱-{𝐞}_i)\alpha p_{0i}+\pi (𝐱+{𝐞}_i){\mu }_i(x_i+1)p_{i0}]+\sum _{i=1}^J\sum _{j\ne i}\pi (𝐱+{𝐞}_i-{𝐞}_j){\mu }_i(x_i+1)p_{ij}.(2)\end{array}$

其中${𝐞}_i$表示第$i$个单位向量.。

定理

设独立随机向量$(Y_1,\dots ,Y_J)$，每个$Y_i$都有概率质量函数：

$P(Y_i=n)=p(Y_i=0)\cdot \frac{{\lambda }_i^n}{M_i(n)},(3)$

其中$M_i(n)=\prod _{j=1}^n{\mu }_i(j)$。当$\sum _{n=1}^{\mathrm{\infty }}\frac{{\lambda }_i^n}{M_i(n)}<\mathrm{\infty }$即$P(Y_i=0)={(1+\sum _{n=1}^{\mathrm{\infty }}\frac{{\lambda }_i^n}{M_i(n)})}^{-1}$是良定义的，开放杰克逊网络的平衡分布有如下的积形式：

$\pi (𝐱)=\prod _{i=1}^{J}P(Y_i=x_i).$

对所有的$𝐱\in {𝒵}_{+}^J$。

例

三节点的开放杰克逊网络

设图中有一三节点的杰克逊网络，系数分别是：

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

$P=\left[\begin{array}{ccc}0& 0.5& 0.5\\ 0& 0& 0\\ 0& 0& 0\end{array}\right],\mu =\left[\begin{array}{c}{\mu }_1(x_1)\\ {\mu }_2(x_2)\\ {\mu }_3(x_3)\end{array}\right]=\left[\begin{array}{c}15\\ 12\\ 10\end{array}\right]\text{ for all }{x}_i>0$

通过定理，可以计算：

$\lambda =(I-P^T{)}^{-1}a={\left[\begin{array}{ccc}1& 0& 0\\ -0.5& 1& 0\\ -0.5& 0& 1\end{array}\right]}^{-1}\left[\begin{array}{c}0.5\times 5\\ 0.5\times 5\\ 0\end{array}\right]=\left[\begin{array}{ccc}1& 0& 0\\ 0.5& 1& 0\\ 0.5& 0& 1\end{array}\right]\left[\begin{array}{c}2.5\\ 2.5\\ 0\end{array}\right]=\left[\begin{array}{c}2.5\\ 3.75\\ 1.25\end{array}\right]$

根据$𝐘$的定义，有：

$P(Y_1=0)={\left(\sum _{n=0}^{\mathrm{\infty }}{\left(\frac{2.5}{15}\right)}^n\right)}^{-1}=\frac{5}{6}$

$P(Y_2=0)={\left(\sum _{n=0}^{\mathrm{\infty }}{\left(\frac{3.75}{12}\right)}^n\right)}^{-1}=\frac{11}{16}$

$P(Y_3=0)={\left(\sum _{n=0}^{\mathrm{\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$各项服从简单的几何分布。

杰克逊网络的推广

推广的杰克逊网络允许Template:Tsl不一定是一个泊松过程，也允许服务时间是独立且同种的非指数分布。一般地，网络不一定要有Template:Tsl，因此需要找近似解

布朗近似

在一些平和的条件下，开放的推广杰克逊网络的队长过程${\displaystyle }$Q(t)${\displaystyle }$可以用Template:Tsl近似，定义为$RB{M}_{Q(0)}(\theta ,\mathrm{\Gamma };R)$，其中$\theta$是过程的漂移（Template:Lang），$\mathrm{\Gamma }$是协方差矩阵，$R$是反射矩阵。这一二阶近似是从均质流体（Template:Lang）的推广杰克逊网络和反射布朗运动间的关系得到的。

反射布朗过程的参数如下所述：

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

$\mathrm{\Gamma }=({\mathrm{\Gamma }}_{kl})$有${\mathrm{\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}$	反映节点间关系的系数Template:Hidden begin 它们是这样定义的：令$A(t)$为系统的到达过程，则在分布中有$A(t)-\alpha t\approx \hat{A}(t)$，其中$\hat{A}(t)$是一个无漂移（Template:Lang）的布朗过程，其协方差矩阵为${\mathrm{\Gamma }}^0=({\mathrm{\Gamma }}_{ij}^0)$，满足对所有的$i,j\in \{1,\dots ,J\}$都有${\mathrm{\Gamma }}_{ij}^0={\alpha }_i{c}_{0,i}^2{\delta }_{ij}$。 Template:Hidden end

参见

• Gordon–Newell网络
• BCMP网络
• G-网络
• Little法则