张莹+刘建民

摘  要： 为了得到多服务台队列中流失率的高负荷极限，通过对有顾客流失的[G/G/1/K]队列进行推广得到[G/GI/m/K]队列，在高负荷条件下，获得了有[m]个服务台的队列系统中队长过程、流失过程的极限定理与流失比例的高负荷极限。以[M/M/m/K]队列为例，用Matlab编程进行模拟仿真，验证了理论结果的合理性，这是分析多服务台队列系统的一种新方法。

关 键 词： [G/GI/m/K]队列; 高负荷; 队长过程; 流失比例; 模拟仿真

中图分类号： TN911?34                   文献标识码： A                            文章编号： 1004?373X（2014）24?0028?03

Analog simulation for heavy?traffic limit of loss proportion in many?server queues

ZHANG Ying， LIU Jian?min

（College of Science， Changan University， Xian 710064， China）

Abstract： To get the heavy?traffic limit for the loss proportion in many?server queues， the model of [G/G/1/K]queue with customer loss is extended to the model of[G/GI/m/K]. The limit theorems for the queue?length process， loss process and the heavy?traffic limit for the loss proportion in the system were obtained under the condition of heavy traffic. Taking the[M/M/m/K]queue as an example， the analog simulation was conducted with Matlab programming to verify the reasonability of the theoretical result. It is a new way to analyze the many?server queues.

Keyword： [G/GI/m/K]queue; heavy?traffic; queue?length process; loss proportion; simulation

0  引  言

在现实生活中大家经常遇到的是多服务台排队系统且队伍较长的现象，例如银行和医院中的排队现象，这其实就是高负荷条件下的多服务台排队系统。在高负荷情况下研究多服务台的排队系统已有很多文章，如Whitt研究了带放弃的多服务台的流体模型[1]，Whitt给出[G/GI/n/m]队列的扩散逼近[2]。Whitt和Hal fin研究了多指数服务台队列的高负荷极限[3]。Whitt研究有阻塞的服务系统的高负荷极限，讨论了局部高负荷极限[4]。Whitt研究了单服务台队列中流失比例的高负荷极限[5]。关于高负荷条件下多服务台排队系统的模拟仿真研究的也比较多，例如霍明的并联多服务台排队系统的仿真建模研究[6]以及邓年华的基于Matlab的多服务台排队系统的计算机模拟[5]，陈实的多服务台混合制排队模型[M/G/s/k]的仿真研究[7]。本文是在高负荷情况下，对有顾客流失的[G/GI/m/K]队列模型进行了研究，给出队长过程、流失过程及流失比例的高负荷极限，同时给出基于Matlab编程的仿真算法，进行模拟仿真。

1  模型建立

本文研究的是[G/GI/m/K]队列模型，一个一般平稳到达过程，到达率为[λ]，独立同分布的服务时间且服从一般分布，[m]个服务台，平均服务率为[μii=1，2，…，m]，等待空间的额外最大容量为[K]，服务规则为先到先服务（FCFS）。设到达过程与服务过程是相互独立的，服务强度为[ρ]，则有：

[ρ=λμ1+μ2+…+μm] （1）

设[Uk，V1，k，V2，k，…，Vm，k：k≥1]是一非负随机变量序列，其中[Uk]表示的是第[k-1]个顾客与第[k]个顾客的到达时间间隔，[Vi，ki=1，2，…，m]表示的是第[i]个服务台潜在服务时间序列，则相应的部分和为：

[Suk=U1+U2+…+Uk] （2）

[Svi，k=Vi，1+Vi，2+…+Vi，k;   i=1，2，…，m] （3）

且：

[Su0=Svi，0=U0=Vi，0=0] （4）

相应的计数过程为：

[At=maxk≥0：Suk≤t] （5）

[Nit=maxk≥0：Svi，k≤t，  t≥0] （6）

令[N]为叠加过程，定义为：

[Nt=N1t+N2t+…+Nmt，   t≥0]     （7）

由以上的定义可知：[At]表示的是[0，t]内共到达的顾客数，[Nt]表示的是[0，t]内共服务完的顾客数，记[Qt]为[t]时刻的队长，[Lt]为[0，t]内共流失的顾客数，考虑一个上面描述的队列系统序列，则相应的刻画随机过程为时间用[n]来刻画，空间用[cn]来刻画，[t]表示向下取整：

[Sunt=c-1nSun，nt-λ-1nnt] （8）

[Svn，it=c-1nSvn，i，nt-μ-1n，intAnt=c-1nAnnt-λnnt] （9）

[Nn，it=c-1nNn，int-μn，int] （10）

[Nnt=c-1nNnnt-μnnt] （11）

[Qnt=c-1n?Qnnt] （12）

[Lnt=c-1n?Lnnt] （13）

式中[μn=μn，1+…+μn，m]。

为了陈述结论，令[?]表示依分布收敛，[D≡D0，+∞，R，M1≡D，M1]表示在[M1]拓扑下在[0，+∞]上除0点外左极限存在的右连续实值函数空间，[Dk=D，M1k]为[k]维[D]乘积空间，[Dm+1，WM1]表示的是在[WM1]拓扑下的[m+1]维[D]乘积空间，[Discx]表示函数[x]的不连续点的集合，[=d]表示依分布相等，[e]表示在[D]上的恒等函数，即[et=t]，[x?y]表示复合函数。

令[?0，ψL0：D→D2]的一维反射映射，且在0处有下界，满足：

[?0x=x+ψL0x]

且令[?0，k，ψL0，ψUk：D→D3]的二维反射映射，且在0处有下界，在[k]处有上界，满足[8]：

[?0，kx=x+ψL0x-ψUkx]

式中：[ψL0x]为下界修正函数;[ψUkx]为上界修正函数。

2  [G/GI/m/K]队列的随机过程极限

2.1  队长过程与流失过程的随机过程极限

定理1 （队长过程与流失过程的高负荷极限） 考虑上面所述的[G/GI/m/K]队列模型序列，假定系统初始状态为空，在[Dm+1，WM1]上：

[Sun，Svn，1，Svn，2，…，Svn，m?Su，Sv1，Sv2，…，Svm] （14）

设[cn→∞]， [ncn→∞]，[μn，i→μi，0<μi<∞]，有：[ηn=n?μn-λncn→η，  -∞<η<+∞] （15）

[Kncn→k，  0

且假定：

[PSu0=0=PSvi0=1] （17）

[PDiscSvi?μie?DiscSvj?μje=?=1] （18）

[PDiscSvi?μie?DiscSu=?=1] （19）

则有：

[Qn，Ln?Q，L=      ?0，ki=1mSvi-Su-ηe，ψUki=1mSvi-Su-ηe] （20）

2.2  流失比例的探究

因为[Lt]表示的是[[0，t]]内共流失的顾客数，记[Πt]为[[0，t]]内的流失比例，则[Πt=Ltmax1，At]，且其相应刻画随机过程为[Πnt=nΠnntcn]

定理2：在定理1的条件下，若在[D0，∞，R，M1]上：

[Πn?Π] （21）

其中[Πt=Ltt]，[t≥0]，假定当[t>0]时，[Pt∈DiscL=0]，对于所有的[t>0]，当[n→∞]时：

[ncnΠnnt?Πt] （22）

且：

[Πnntμn-λn?Πtη] （23）

式中[η]是式（15）中的极限，若当[t→∞]时[Πt?π]，则有：

[ncnΠnnt?π] （24）

式中[π]是某一确定的流失比例。

3  模拟仿真

3.1  算法设计

为了方便排队系统的信息记录及仿真算法的研究，本文构建这样一个状态矩阵A为一个[8×s]矩阵，[s]为考虑的[0，t]到达的前[s]个顾客，矩阵的每一列存放着一名顾客的所有信息及此顾客到达时系统的状态，则以第[i]列为例，矩阵每一行所存放的具体信息如表1所示。

在算法中：[r]表示平均到达率;[μ]表示平均服务率;[k]为等待空间容量;[m]为服务台数;[loss]为流失比例。根据到达过程产生顾客的间隔到达时间，则可得到每个顾客的到达时刻，并初始化矩阵A的第一行，根据服务时间服从的分布产生顾客的服务时间，流失比例的计算应用第2节中的定义式。

表1 状态矩阵A

由于前[m]个顾客到达时均不需要排队，因此可初始化矩阵A的前[m]列。当第[ii>m]个顾客到达系统时，会遇到如三种情况：情况1为 顾客到达时有空闲的服务台，顾客不需要等待直接接受服务;情况2为顾客到达时无空闲服务台，顾客进入等待队列;情况3为顾客到达时等待空间已满，顾客被阻塞而流失。这样通过对顾客的到达进行分析，得到相应的数量指标，同时初始化矩阵A。

3.2  算例分析

现在给出算例分析，以[M/M/m/K]为例：考虑一[M/M/m/K]队列的模型序列，在第[n]个模型中：令刻画常数[cn=n]，顾客的平均到达率[r=m?1+1n]，各个服务台的平均服务率都相同为[u=1]，则服

务强度为[ρ=rm]，令等待空间容量[k=30]，[s=n]，即考虑在[0，t]内到达的前[n]个顾客。

3.2.1  对顾客基本信息的分析

对到达的前100个顾客进行分析（m=100）如图1所示。从图1中的（a）部分可得到当顾客的离开时刻与到达时刻相同时，则该顾客为被阻塞而流失的顾客;从（c）部分可得到当顾客的等待时长为0时，主要为两种情况：顾客到达时有空闲的服务台顾客直接接受服务;顾客到达等待空间已满，顾客因被阻塞而流失;而 （d）、（e）、（f）部分分别表示了顾客到达时系统的队长、流失顾客数及流失率。

图1 到达前100个顾客分析图

3.2.2  探讨流失比例[loss]与[m，n]的关系

模拟在[n]与[m]取不同的值的情况下的流失比例（横坐标均为时间，纵坐标均为流失比例），如图2所示。

在图2中，当[n]的取值相同服务台数[m]不同时，服务强度相同但平均到达率不同;当服务台数[m]相同[n]取不同的数值时，平均到达率不同从而服务强度不同。服务强度与流失比例对比，如表2所示。

由于到达时间间隔与服务时间均为产生的随机数，每次的模拟结果均不相同且有时相差很大，但是当[n=10  000]时，可观察到流失比例基本上趋近于一个确定值，当[n]取值更大时，通过多次的模拟计算，也可得到同样的结论，这与推论结论相符，所以建立的仿真算法是有效且可行的。

图2 n，m取值不同时的流失比例

4  结  语

本文给出[G/GI/m/K]队列在高负荷下队长过程、流失过程及流失比例的高负荷极限，并且以[M/M/m/K]为例，给出关于流失比例的模拟仿真。根据[K]的不同取值可被应用到不同的随即服务系统，当[K=m]时，可被应用到呼叫中心服务系统，当[K>m]且为具体某一个值时可被应用到随机服务系统（如银行系统）。通过对更新方法与随机数产生的方法，该仿真算法还可被应用到其他的队列系统，如[G/M/m/K]或[M/G/m/K]等队列系统，显然当[m=1]时为单服务台队列系统。

参考文献

[1] WHITT W. Fluid models for multi?server queues with abandonment [J]. Operations Research， 2006， 54（1）： 37?54.

[2] WHITT W. A diffusion approximation for the [G/GI/n/m] queue [J]. Operations Research， 2004， 52（6）： 922?941.

[3] HALFIN S， WHITT W. Heavy?traffic limits for queues with many exponential servers [J]. Operations Research， 1981， 29（3）： 567?588.

[4] WHITT W. Heavy?traffic approximations for service systems with blocking [J]. AT&T Bell Laboratories Technical Journal， 1984， 63（5）： 689?708.

[5] WHITT W. Heavy?traffic limits for loss proportions in single?server queues [J]. Queueing Systems， 2004， 46： 507?536.

[6] 霍明.并联多服务台多服务台排队系统的仿真建模研究[J].广东科技，2012（15）：198?200.

[7] 邓寿年，姜培华，何广.基于Matlab的多服务台排队系统的计算机模拟[J].安庆学院学报，2011，17（3）：61?63.

[8] WHITT W. Stochastic?process limits [M]. New York： Springer?Verlag， 2002.

[9] 陈实.多服务台混合制排队模型[M/G/s/k]的仿真研究[J].现代电子技术，2010，33（3）：142?149.

[10] BILLINGSLEY P. Convergence of probability measures [M]. 2nd ed. New York： Wiley， 1999.

图1 到达前100个顾客分析图

3.2.2  探讨流失比例[loss]与[m，n]的关系

模拟在[n]与[m]取不同的值的情况下的流失比例（横坐标均为时间，纵坐标均为流失比例），如图2所示。

在图2中，当[n]的取值相同服务台数[m]不同时，服务强度相同但平均到达率不同;当服务台数[m]相同[n]取不同的数值时，平均到达率不同从而服务强度不同。服务强度与流失比例对比，如表2所示。

由于到达时间间隔与服务时间均为产生的随机数，每次的模拟结果均不相同且有时相差很大，但是当[n=10  000]时，可观察到流失比例基本上趋近于一个确定值，当[n]取值更大时，通过多次的模拟计算，也可得到同样的结论，这与推论结论相符，所以建立的仿真算法是有效且可行的。

图2 n，m取值不同时的流失比例

4  结  语

本文给出[G/GI/m/K]队列在高负荷下队长过程、流失过程及流失比例的高负荷极限，并且以[M/M/m/K]为例，给出关于流失比例的模拟仿真。根据[K]的不同取值可被应用到不同的随即服务系统，当[K=m]时，可被应用到呼叫中心服务系统，当[K>m]且为具体某一个值时可被应用到随机服务系统（如银行系统）。通过对更新方法与随机数产生的方法，该仿真算法还可被应用到其他的队列系统，如[G/M/m/K]或[M/G/m/K]等队列系统，显然当[m=1]时为单服务台队列系统。

参考文献

[1] WHITT W. Fluid models for multi?server queues with abandonment [J]. Operations Research， 2006， 54（1）： 37?54.

[2] WHITT W. A diffusion approximation for the [G/GI/n/m] queue [J]. Operations Research， 2004， 52（6）： 922?941.

[3] HALFIN S， WHITT W. Heavy?traffic limits for queues with many exponential servers [J]. Operations Research， 1981， 29（3）： 567?588.

[4] WHITT W. Heavy?traffic approximations for service systems with blocking [J]. AT&T Bell Laboratories Technical Journal， 1984， 63（5）： 689?708.

[5] WHITT W. Heavy?traffic limits for loss proportions in single?server queues [J]. Queueing Systems， 2004， 46： 507?536.

[6] 霍明.并联多服务台多服务台排队系统的仿真建模研究[J].广东科技，2012（15）：198?200.

[7] 邓寿年，姜培华，何广.基于Matlab的多服务台排队系统的计算机模拟[J].安庆学院学报，2011，17（3）：61?63.

[8] WHITT W. Stochastic?process limits [M]. New York： Springer?Verlag， 2002.

[9] 陈实.多服务台混合制排队模型[M/G/s/k]的仿真研究[J].现代电子技术，2010，33（3）：142?149.

[10] BILLINGSLEY P. Convergence of probability measures [M]. 2nd ed. New York： Wiley， 1999.

图1 到达前100个顾客分析图

3.2.2  探讨流失比例[loss]与[m，n]的关系

模拟在[n]与[m]取不同的值的情况下的流失比例（横坐标均为时间，纵坐标均为流失比例），如图2所示。

在图2中，当[n]的取值相同服务台数[m]不同时，服务强度相同但平均到达率不同;当服务台数[m]相同[n]取不同的数值时，平均到达率不同从而服务强度不同。服务强度与流失比例对比，如表2所示。

由于到达时间间隔与服务时间均为产生的随机数，每次的模拟结果均不相同且有时相差很大，但是当[n=10  000]时，可观察到流失比例基本上趋近于一个确定值，当[n]取值更大时，通过多次的模拟计算，也可得到同样的结论，这与推论结论相符，所以建立的仿真算法是有效且可行的。

图2 n，m取值不同时的流失比例

4  结  语

本文给出[G/GI/m/K]队列在高负荷下队长过程、流失过程及流失比例的高负荷极限，并且以[M/M/m/K]为例，给出关于流失比例的模拟仿真。根据[K]的不同取值可被应用到不同的随即服务系统，当[K=m]时，可被应用到呼叫中心服务系统，当[K>m]且为具体某一个值时可被应用到随机服务系统（如银行系统）。通过对更新方法与随机数产生的方法，该仿真算法还可被应用到其他的队列系统，如[G/M/m/K]或[M/G/m/K]等队列系统，显然当[m=1]时为单服务台队列系统。

参考文献

[1] WHITT W. Fluid models for multi?server queues with abandonment [J]. Operations Research， 2006， 54（1）： 37?54.

[2] WHITT W. A diffusion approximation for the [G/GI/n/m] queue [J]. Operations Research， 2004， 52（6）： 922?941.

[3] HALFIN S， WHITT W. Heavy?traffic limits for queues with many exponential servers [J]. Operations Research， 1981， 29（3）： 567?588.

[4] WHITT W. Heavy?traffic approximations for service systems with blocking [J]. AT&T Bell Laboratories Technical Journal， 1984， 63（5）： 689?708.

[5] WHITT W. Heavy?traffic limits for loss proportions in single?server queues [J]. Queueing Systems， 2004， 46： 507?536.

[6] 霍明.并联多服务台多服务台排队系统的仿真建模研究[J].广东科技，2012（15）：198?200.

[7] 邓寿年，姜培华，何广.基于Matlab的多服务台排队系统的计算机模拟[J].安庆学院学报，2011，17（3）：61?63.

[8] WHITT W. Stochastic?process limits [M]. New York： Springer?Verlag， 2002.

[9] 陈实.多服务台混合制排队模型[M/G/s/k]的仿真研究[J].现代电子技术，2010，33（3）：142?149.

[10] BILLINGSLEY P. Convergence of probability measures [M]. 2nd ed. New York： Wiley， 1999.