杰克逊排队网络

排队论中(运筹学的一支),杰克逊排队网络(英语:Jackson network,亦作Jacksonian network[1])是一类排队网络模型,其均衡分布计算形式简单且网络具有积形式解。该模型已被推广,其定理的思想也被运用于寻找其他网络中类似的积形式解。[2]互联网发展中的一些思想亦源于该排队网络。[3]这一网络模型首先由詹姆斯·R·杰克逊英语James R. Jackson提出。[4][5]2004年,杰克逊的文章重载于《管理科学英语Management Science (journal)》,该刊将其誉为“管理科学头50年中最具影响力的十篇论文”之一。[6]

杰克逊受到了柏克英语Burke's theorem和赖克(Reich)工作的启发。[7]但吉恩·华尔兰德(Jean Walrand)指出“积形式解的结果……从柏克定理推过去不是很直接,并没有杰克逊本人在他那篇奠基性文章中所认为的那么直接”。[8]

在串联排队(有限数量的队列,顾客按先后顺序去每个队列等候)和环形排队网络(串联成环的若干队列,顾客按先后顺序去每个队列等候)中,R.R.P. Jackson更早就发现了一个积形式解。[9]

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

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

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

 个相连队列组成的网络被称作杰克逊网络,若它满足下述条件:[11][12]

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

定理

 M/M/1模型的开放杰克逊网络,其中利用率(utilization 对每个队列都小于1,平衡状态概率分布存在,且对状态 ,平衡状态(equilibrium state)概率分布由每个队列的平衡分布之积给出:

 

结果 M/M/c服务站(stations)也成立,其中第 个节点的服务台(servers)数为 ,利用率满足 

定义

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

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

定义  ,我们就可以解出 

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

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

 

其中 表示第 单位向量.。

定理

设独立随机向量 ,每个 都有概率质量函数

 

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

 

对所有的 

 
三节点的开放杰克逊网络

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

 
 

通过定理,可以计算:

 

根据 的定义,有:

 
 
 

因此,每个节点处有一个服务的概率是:

 

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

杰克逊网络的推广

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

布朗近似

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

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

 
  
 

其中符号的定义:

近似公式中符号的定义
符号 含义
  J维向量,每个节点的到达率
  J维向量,每个节点的服务率
  转移矩阵
  第j个节点的有效到达
  第j个节点服务时间的变异系数
  第j个节点服务台间转移到达时间的变异系数
  反映节点间关系的系数

它们是这样定义的:令 为系统的到达过程,则在分布中有 ,其中 是一个无漂移(driftless)的布朗过程,其协方差矩阵为 ,满足对所有的 都有 

参见

参考文献

  1. ^ Walrand, J.; Varaiya, P. Sojourn Times and the Overtaking Condition in Jacksonian Networks. Advances in Applied Probability. 1980, 12 (4): 1000–1018. JSTOR 1426753. doi:10.2307/1426753. 
  2. ^ Kelly, F. P. Networks of Queues. Advances in Applied Probability. June 1976, 8 (2): 416–432. JSTOR 1425912. doi:10.2307/1425912. 
  3. ^ Jackson, James R. Comments on "Jobshop-Like Queueing Systems": The Background. Management Science. December 2004, 50 (12): 1796–1802. JSTOR 30046150. doi:10.1287/mnsc.1040.0268. 
  4. ^ Jackson, James R. Jobshop-like Queueing Systems. Management Science. Oct 1963, 10 (1): 131–142. JSTOR 2627213. doi:10.1287/mnsc.1040.0268.  A version from January 1963 is available at http://www.dtic.mil/dtic/tr/fulltext/u2/296776.pdf页面存档备份,存于互联网档案馆
  5. ^ Jackson, J. R. Networks of Waiting Lines. Operations Research. 1957, 5 (4): 518–521. JSTOR 167249. doi:10.1287/opre.5.4.518. 
  6. ^ Jackson, James R. Jobshop-Like Queueing Systems. Management Science. December 2004, 50 (12): 1796–1802. JSTOR 30046149. doi:10.1287/mnsc.1040.0268. 
  7. ^ Reich, Edgar. Waiting Times When Queues are in Tandem. Annals of Mathematical Statistics. September 1957, 28 (3): 768. JSTOR 2237237. doi:10.1214/aoms/1177706889. 
  8. ^ Walrand, Jean. A Probabilistic Look at Networks of Quasi-Reversible Queues. IEEE Transactions on Information Theory. November 1983, 29 (6): 825. doi:10.1109/TIT.1983.1056762. 
  9. ^ Jackson, R. R. P. Book review: Queueing networks and product forms: a systems approach. IMA Journal of Management Mathematics. 1995, 6 (4): 382–384. doi:10.1093/imaman/6.4.382. 
  10. ^ Gordon, W. J.; Newell, G. F. Closed Queuing Systems with Exponential Servers. Operations Research. 1967, 15 (2): 254. JSTOR 168557. doi:10.1287/opre.15.2.254. 
  11. ^ Goodman, Jonathan B.; Massey, William A. The Non-Ergodic Jackson Network. Journal of Applied Probability. December 1984, 21 (4): 860–869. doi:10.2307/3213702. 
  12. ^ Walrand, J.; Varaiya, P. Sojourn Times and the Overtaking Condition in Jacksonian Networks. Advances in Applied Probability. December 1980, 12 (4): 1000–1018. doi:10.2307/1426753. 
  13. ^ Chen, Hong; Yao, David D. Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer. 2001. ISBN 0-387-95166-0.