带有中途退出的M/M/1/N单重工作休假排队系统

赵晓华　樊剑武

【摘 要】研究了一个带有中途退出的M/M/1/N单重工作休假排队系统。服务员在假期中以较低的速率服务顾客而非停止工作。利用马尔科夫过程理论和矩阵解法求出了稳态概率的矩阵解，并得到了系统的平均队长、平均等待队长以及顾客的消失概率等性能指标。

【关键词】单重工作休假；止步；稳态概率；矩阵解法；性能指标

【Abstract】An M/M/1/N queuing system was considered with reneging and single working vacation. The server works at a lower rate rather than completely stops service during the vacation period. First， the matrix form solution of the steady-state probability was derived by the Markfov process method and the matrix solution method. Some performance measures of the system such as the expected number of customers in the system or in the queue and the loss probability of the customer were also presented.

【Key words】Single working vacation；Reneging；Teady-state probability；Matrix solution method；Performance measures

0 引言

在过去的20年里，休假排队[1]已经得到了广泛、深入的研究并形成了理论框架。在各种各样的休假排队模型中，服务员在假期中完全停止服务，但是他可以从事辅助工作。休假排队的研究成果已应用到很多的领域，像计算机系统、通信网络、生产制造系统等。详细内容可以参见Doshi的综述，Takagi，Tian和Zhang的专著。Servi和Finn[2]在2002年引入了一种半休假策略：服务员在假期中并未完全停止工作，而是以较低的速率为顾客服务，这种休假策略称为工作休假（working vacation WV ）。如果让服务员在工作休假中服务率减小为零，则工作休假排队就成为了一个经典休假排队模型，因此工作休假排队是经典休假排队的一个扩展。近年来工作休假排队系统[3-6]受到了国内外学者的关注。但对有限等待场所研究的还不多，因此本文考虑一个等待场所有限的M/M/1/N单重工作休假排队系统。

本文结构安排如下：第二节描述了系统模型；第三节利用马尔科夫过程理论建立了系统稳态概率满足的方程组；第四节将转移率矩阵写成了分块矩阵的形式，并证明了相关矩阵的可逆性。在此基础上，利用分块矩阵解法求出了稳态概率的矩阵解；第五节利用稳态概率的矩阵解，得到了系统的平均队长、平均等待队长及顾客的消失概率等性能指标。

1 模型描述

考虑一个M/M/1/N排队系统，系统中只有一个服务台，每次只能接待一位顾客，系统容量为N，一旦系统中顾客数达到N个，再到达的顾客就将消失。因此这也是一个消失系统。顾客按照参数为λ的Poisson流到达。每个顾客所需的服务时间服从负指数分布。在忙期中服务员的服务率为μb。相继两次假期之间的时间称为服务期或正规忙期。现加入下列单重工作休假规则：一旦系统中没有顾客即正规忙期结束，服务员立即进入一个随机长度为V的工作休假中，休假时间V服从参数为θ的负指数分布。与通常的休假策略不同，服务员在假期内并未完全停止工作，而是以较低的速率μv（μv<μb）为顾客服务。当一次工作休假结束时，如果系统中已有顾客在等待，服务员立即停止工作休假，服务率由μv提高到μb，一个正规忙期开始；否则就进入闲期，直到有顾客到达，正规的忙期才开始。令n表示系统中的顾客数。若n≤1，则系统中的顾客立即可以得到服务，此时不会发生中途退出的情况；反之n>1，若，则一个顾客在接受服务，其余n-1个顾客在队列中等待服务，这时顾客可能因为等待的不耐烦而在没有接受服务的情况下离开系统（中途退出）。假设顾客在进入系统后直到中途退出的这段等待时间服从参数为α的负指数分布，由于每个顾客的到达和离去都是独立的，则可得顾客的中途退出率：

r（n）=（n-1）α， 2≤n≤N

假定到达间隔T，工作休假时间V，正规忙期中的服务时间Sb和工作休假的服务时间Sv均相互独立，服务规则为先到先服务（FCFS）。

2 稳态概率方程组

令L（t）表示时刻t系统中的顾客数即时刻t系统的队长，t≥0。令J（t）表示时刻t服务员的工作状态，定义如下：

J（t）=0，时刻t服务员处于工作休假状态1，时刻t服务员处于非工作休假状态

则{L（t），J（t），t≥}为一马尔科夫过程， 其状态空间为：

Ω={（n，0）∶0≤n≤N}∪{（n，1）∶0≤n≤N}

这里状态（0，1）表示系统处在闲期；状态n，1，1≤n≤N表示系统处在正规忙期；状态n，0，0≤n≤N表示系统处在工作休假期，其中n表示系统中的顾客数。

系统的稳态概率定义如下：

给出了排队系统的稳态指标，我们就可以通过数值分析，了解系统中的某些参数对这些稳态指标的影响，从而使排队系统尽可能达到最优。

【参考文献】

[1]田乃硕. 休假随机服务系统[M]. 北京：北京大学出版社，2001.

[2]Servi L D， Finn S G. M/M/1 queue with working vacations（M/M/1/WV）[J]. Perform. Evaluation， 2002， 50： 41-52.

[3]Liu W Y， Xu X L， Tian N S. Stochastic decompositions in the M/M/1 queue with working vacations[J]. Operation Research Letters， 2007，35（5）：595-600.

[4]Li J， Tian N. Analysis of the discrete time Geo/Geo/1 queue with single working vacation[J]. Quality Technology and Quantitative Management， 2008，5（1）：77-89.

[5]赵晓华，樊剑武，田乃硕，田瑞玲.带有止步和中途退出的M/M/1/N多重工作休假排队系统[J].山东大学学报，2008，43（10）：46-51.

[6]赵晓华，樊剑武，田乃硕. 带有止步的成批到达MX/M/1/N多重工作休假排队系统[J].燕山大学学报，2009，33（2）：178-183.

[7]樊剑武，赵晓华，李旭红，李秀菊.M/M/1/N单重工作休假排队系统的性能分析[J].四川理工学院学报，2009，22（3）：113-116.

[8]北京大学数学系几何与代数教研室代数小组.高等代数.2版[M].北京：高等教育出版社，12，158.

[9]林记.关于n阶循环矩阵可逆问题的几点讨论[J].四川理工学院学报，2007，20（2）：21-24.

[责任编辑：曹明明]