杰克逊排队网络

${\displaystyle m}$ 个相连队列组成的网络被称作杰克逊网络，若它满足下述条件：^[11][12]

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

${\displaystyle m}$ 为M/M/1模型的开放杰克逊网络，其中利用率（utilization）${\displaystyle \rho _{i}}$ 对每个队列都小于1，平衡状态概率分布存在，且对状态${\displaystyle \scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}}$ ，平衡状态（equilibrium state）概率分布由每个队列的平衡分布之积给出：

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

结果${\displaystyle \pi (k_{1},k_{2},\ldots ,k_{m})=\prod _{i=1}^{m}\pi _{i}(k_{i})}$ 对M/M/c服务站（stations）也成立，其中第${\displaystyle i}$ 个节点的服务台（servers）数为${\displaystyle c_{i}}$ ，利用率满足${\displaystyle \rho _{i}<c_{i}}$ 。

在一个开放网络中，顾客自系统外部以泊松流方式到达，到达率为${\displaystyle \alpha >0}$ 。每个往节点j的到达是相互独立的，有概率 ${\displaystyle p_{0j}\geq 0}$ 且满足${\displaystyle \sum _{j=1}^{J}p_{0j}=1}$ 。当节点${\displaystyle i}$ 处的服务完成时，顾客会以概率${\displaystyle p_{ij}}$ 进入另一节点或者以${\displaystyle p_{i0}=1-\sum _{j=1}^{J}p_{ij}}$ 的概率离开网络。

因此，节点${\displaystyle i}$ 的总到达率${\displaystyle \lambda _{i}}$ 是外部到达和内部转移的总和：${\displaystyle }$${\displaystyle }$

${\displaystyle }$

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

所有任务在后续泊松过程中会离开其节点，节点${\displaystyle i}$ 处有${\displaystyle x_{i}}$ 个任务，定义其服务率为${\displaystyle \mu _{i}(x_{i})}$ 。

令${\displaystyle X_{i}(t)}$ 表示节点${\displaystyle i}$ 在时间${\displaystyle t}$ 的任务数，${\displaystyle \mathbf {X} =(X_{i})_{i=1}^{J}}$ 。${\displaystyle \mathbf {X} }$ 的均衡分布，${\displaystyle \pi (\mathbf {x} )=P(\mathbf {X} =\mathbf {x} )}$ 由如下系统平衡方程给出：

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

其中${\displaystyle \mathbf {e} _{i}}$ 表示第${\displaystyle i}$ 个单位向量.。

定理

设独立随机向量${\displaystyle (Y_{1},\ldots ,Y_{J})}$ ，每个${\displaystyle Y_{i}}$ 都有概率质量函数：

${\displaystyle P(Y_i=n)=p(Y_i=0)\cdot \frac{{\lambda }_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)}  

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

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

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

例

由于这里的服务率是状态无关的，${\displaystyle Y_{i}}$ 各项服从简单的几何分布。

推广的杰克逊网络允许更新到达过程（英语：Renewal theory）不一定是一个泊松过程，也允许服务时间是独立且同种的非指数分布。一般地，网络不一定要有积形式稳定解（英语：Product-form solution），因此需要找近似解 ^[13]

布朗近似

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

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

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

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

${\displaystyle R=I-P^{T}}$ 

其中符号的定义：

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