杰克逊排队网络

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

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

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

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

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

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

 若网络是开放的，任意往节点的外部到达都是一个泊松过程，
 服务时间呈指数分布，排队规则为先到先得（），
 队列处的顾客服务结束后，以概率转移到新的队列或以概率离开队列；对于开放网络来说，离开概率对所有队列的某个子集是非零的，
 所有队列的利用率都小于1。

 定理 

为M/M/1模型的开放杰克逊网络，其中利用率（）对每个队列都小于1，平衡状态概率分布存在，且对状态，平衡状态（）概率分布由每个队列的平衡分布之积给出：

结果对M/M/c服务站（）也成立，其中第个节点的服务台（）数为，利用率满足。

 定义 
在一个开放网络中，顾客自系统外部以泊松流方式到达，到达率为。每个往节点j的到达是相互独立的，有概率 且满足。当节点处的服务完成时，顾客会以概率进入另一节点或者以的概率离开网络。

因此，节点的总到达率是外部到达和内部转移的总和：

（因为每个节点的利用率均小于1，且我们观察的是均衡分布，即长时间运行的平均行为，任务从转移到速率的界不超过到达率的一部分，我们由此忽略上式中的服务率。）

定义 ，我们就可以解出。

所有任务在后续泊松过程中会离开其节点，节点处有个任务，定义其服务率为。

令表示节点在时间的任务数，。的均衡分布，由如下系统平衡方程给出：

其中表示第个单位向量.。

 定理 
设独立随机向量，每个都有概率质量函数：

其中。当即是良定义的，开放杰克逊网络的平衡分布有如下的积形式：

对所有的。

 例 
缩略图|三节点的开放杰克逊网络
设图中有一三节点的杰克逊网络，系数分别是：

通过定理，可以计算：



根据的定义，有：

因此，每个节点处有一个服务的概率是：

由于这里的服务率是状态无关的，各项服从简单的几何分布。

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

 布朗近似 
在一些平和的条件下，开放的推广杰克逊网络的队长过程可以用近似，定义为，其中是过程的漂移（），是协方差矩阵，是反射矩阵。这一二阶近似是从均质流体（）的推广杰克逊网络和反射布朗运动间的关系得到的。

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

有

其中符号的定义：
+近似公式中符号的定义 符号   含义 J维向量，每个节点的到达率  J维向量，每个节点的服务率  转移矩阵 第j个节点的有效到达  第j个节点服务时间的变异系数 第j个节点服务台间转移到达时间的变异系数   反映节点间关系的系数
它们是这样定义的：令为系统的到达过程，则在分布中有，其中是一个无漂移（）的布朗过程，其协方差矩阵为，满足对所有的都有。

 参见 

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

 参考文献 

Category:等候理論