具有插队行为的M_M_c_m c排队系统等待时间分析.pdf

DOI:10.159601.issn.1007-6093.2023.03.008Operations Research TransactionsVol.27No.3Sep.,20232023年9 月运筹学学报第2 7 卷第3 期具有插队行为的M/MC排队系统等待时间分析吴文青1,2,t柯淇淋3唐应辉3陈林4摘要本文研究具有插队行为和容量有限的多服务台排队系统中顾客的等待时间分布函数。将进入系统的顾客按照插队与否分为常规顾客和插队顾客，常规顾客进入系统后在等待队尾排队等待服务，插队顾客进入系统后总是尽可能地靠近队首插队接受服务。利用负指数分布和位相型分布的性质推导了处于等待队列位置n的顾客、常规顾客、插队顾客的等待时间分布函数的矩阵表达式，并在此基础上给出了等待时间分布函数随时间的变化情况。关键词M/M/c/m+c排队系统，插队行为，等待时间分布函数，位相型分布中图分类号0 2 2 6,0 2 13.22010数学分类号6 0 K25，6 0 G 10Analysis of waiting time of customers in anM/M/c/m+c queueing system withcustomer interjections*WU Wenqingl,2,tKE Qilin3TANG Yinghui3CHEN Lin4Abstract This paper studies waiting time distributions of customers in a multi-server queueing system with customer interjections and finite buffer.The customers whoenter the system are divided into regular customers and interjection customers accordingto whether they interject the queue or not.After entering the system,the regular cus-tomers queue up at the end of the waiting line and wait for service,while the interjectioncustomers queue up as close as possible to the head of the waiting line to receive service.By using the properties of negative exponential distribution and phase type distribution,the matrix expressions of waiting time distribution of customers in waiting queue positionn,regular customers and interjection customers are derived.Further,the plots of waitingtime distributions with time t are given.Keywords M/M/c/m+c queueing system,customer interjection,the function ofthe waiting time distribution,phase type distribution收稿日期：2 0 2 0-12-11*基金项目：国家自然科学基金（No.72001181)，可视化计算与虚拟现实四川省重点实验室基金（No.SCVCVR2020.01VS)1.中国民用航空飞行学院理学院，四川德阳6 18 30 7;School of Science,CivilAviationFlightUniversityof China,Deyang 618307,Sichuan,China2.西南科技大学数理学院，四川绵阳6 2 10 10;School ofMathematicsandPhysics,SouthwestUniversityof Science and Technology,Mianyang 621010,Sichuan,China3.四川师范大学数学科学学院，四川成都6 10 0 6 8;Schoolof Mathematical Sciences，Si c h u a n No r m a lUniversity,Chengdu 610068,Sichuan,China4重庆交通大学数学与统计学院，重庆40 0 0 6 7;College of Mathematics and Statistics，Ch o n g q i n gJiaotong University,Chongqing 400067,China+通信作者E-mail:11027卷吴文青，柯淇淋，唐应辉，陈林Chinese Library Classification O226,O213.22010 Mathematics Subject Classification 60K25,60G10在排队系统的理论研究中，通常都假定顾客按照先到先服务的原则。但在现实生活中，会存在部分顾客急于寻求服务而选择插队，特别是在一些服务容量有限的场所，例如医院专家门诊、车站购票以及限制了每日游客量的景区等。这些顾客的插队行为不仅会影响整个排队系统的秩序以及增加队列中某些顾客的等待时间，甚至会影响到系统的工作效率和服务质量。因此，研究具有插队行为的排队系统中顾客的等待时间很有必要。2010年，Chavoushi1首先讨论了具有插队行为的M/M/1排队系统中顾客的等待时间。作者将到达的顾客分为常规顾客和插队顾客，其中常规顾客按照进入系统的先后次序依次等待服务，插队顾客则进入系统后总是尽可能地靠近队首插队等待服务。利用随机比较方法、拉普拉斯变换工具讨论了不同类型的顾客在队列中的等待时间的期望和方差。进一步，作者给出了不同参数下相应指标的取值情况。随后，He和Chavoushi2利用矩阵分析方法、随机比较方法、拉普拉斯变换等研究了具有插队行为的M/M/1和MMAP/PH/1排队系统中顾客的稳态等待时间。受到上述工作的启发，余3在博士论文第五章讨论了插队行为下M/M/C排队系统等待时间的拉普拉斯变换表达式，并给出了均值的表达式以及相应的数值结果。吴等人4进一步从顾客的角度出发将止步策略引入到多服务台排队系统中，并分析相应参数的变化对顾客等待时间的影响。最近，吴等人5,6 将止步、有限容量等策略引入到M/M/1排队系统中讨论顾客的等待时间。梳理上述关于插队的排队系统，可以知道文献1-4都是讨论系统容量无限的排队系统，文献5,6 讨论的是有限容量的排队系统，并且在研究中都使用了拉普拉斯变换来推导顾客等待时间的期望或者方差。由于拉普拉斯逆变换的复杂性，上述文献都没有给出顾客等待时间分布函数的数学表达式。因此，在本文中我们将主要解决顾客等待时间分布函数的表达式。本文考虑了具有插队行为和容量有限的多服务台排队系统中顾客的等待时间分布函数。充分利用负指数分布、位相型分布给出了系统中处于等待队列位置n的顾客，任意一个常规顾客和任意一个插队顾客的等待时间分布函数的表达式以及相应的数值结果。通过分析排队系统中各情况下顾客的等待时间分布函数随时间的变化情况，可以更好地研究插队行为对顾客造成的影响。与文献1-6 不同之处体现在如下两个方面：一是本文研究的是插队行为下多服务台有限容量的排队系统中顾客的等待时间分布函数，这在以前是没有讨论过的。二是在整个的求解过程中，巧妙地多次借助吸收时间的马尔可夫过程理论推导不同类型顾客的等待时间分布函数，并给出了其矩阵表达式。1模型描述本文讨论的具有插队行为和系统容量有限的多服务台排队系统的模型描述如下：1）顾客到达服从参数为入(入 0)的泊松流，即顾客相继到达时间间隔X服从负指数分布 F(t)=P(Xt)=1-e-t,t0。顾客到达时若遇到空闲的服务台则立即接受服务,且服务时间Y服从参数为(0)的负指数分布 G(t)=PYt)=1-e-t,t0。2）若顾客到达时遇到c个服务台全忙，且在队列中等待顾客的人数不为零时，可能会激发该到达顾客的插队动机，即顾客将以一定概率0(0 1)决定插队，并称此类顾客为插队顾客。将没有插队动机的顾客称为常规顾客，其进入系统后自觉加入等待队列1113期具有插队行为的M/M/排队系统等待时间分析队尾排队等待服务。3）插队顾客决定插队时，其插队位置取决于等待队列中顾客数和顾客的位置。若等待队列中的顾客数为n，并假设位置i(1in）上的顾客拒绝顾客插队的概率为ri，则插队顾客能成功在位置i(1in)插队的概率为（1-ra)rj。若等待队列中的n 位-1j=1顾客都拒绝该顾客插队，则插队顾客只能处于位置n+1上，此时概率为ri。在本文j=1讨论中，假定顾客插队所需时间忽略不计。4）系统容量为m+c，若到达顾客看到有m位顾客在排队等待中（其中有c位顾客正在接受服务），意味着此时系统容量已满，则到达顾客由于没有位置而自动离开系统，即此排队系统可记为具有插队行为的M/M/c/m+C。5）上述涉及到的随机变量均相互独立。下面给出一些用到的定义。定义17 概率分布H(）称为（0,+oo)上具有不可约表示（,T）的s阶位相型分布（简记为PH分布)，当且仅当它是一个状态空间为 1,2,，s,s+1)的马氏过程的吸收时间分布，其中1,2,，s 为过程的滑过状态，s+1为过程的吸收状态。记该过程的状态转移速率矩阵为下面的分块形式，TTOQ=00过程的初始状态概率向量为（,s+1)，这里是一个s维行向量，s+1表示初始时刻过程处于吸收状态的概率为s+1。转移速率矩阵中T=-Tesx1。定义2 8 具有状态空间 1,2,，s,s+1)的马尔可夫过程Q以初始分布(,s+1)出发直到吸收于状态s+1为止的时间有分布函数H(a)=1-exp(Ta)esx1 定义39)若H(）和W()是两个相互独立的连续PH分布，分别有s阶PH表示(,T)和阶PH表示(,L),则卷积H*W有s+阶PH表示(,I),其中TTu+1TO=(,Qs+1),s+u+1=s+1u+1,I=0LLO2插队行为下顾客的等待时间分析虽然插队行为对系统的队长没有影响，但是队列中顾客的等待时间将受到插队行为的影响。在本节中，首先给出无插队行为下经典的M/M/c/m+c排队系统中的有关结果。其次，讨论插队行为下处于等待队列位置n的顾客的等待时间分布函数，任意一个常规顾客的等待时间分布函数和任意一个插队顾客的等待时间分布函数的表达式。11227卷吴文青，柯淇淋，唐应辉，陈林2.1经典的M/M/c/m+c排队系统中的有关结果在排队系统的研究中，记pn（n=0,1,m+c)为平稳条件下任意时刻队长为n 的概率，qn(n=0,1,m+c-1）为进入系统的顾客看到有 n个顾客的概率。根据文献10,11,有如下的相关结果。（）nPm=元Po,0nc-1,1nPnPo,cnm+c,cn-c.c!2()（nm+c1Po+cn-c.c!n=0n=cnPoqn=,0nc-1,1一Pm+c1Poqn,cnm+c-l。cn-c.c!1-Pm+c2.2插队行为下处于等待队列位置n的顾客的等待时间分布函数处于等待队列位置n(n=1,2,，m）的顾客的等待时间长短与其位置的变化密切相关，而这种位置变化与插队顾客的剩余到达时间和正在接受服务的顾客的剩余时间有关。因此，对处于位置n的顾客的队列序号变化做如下讨论。情形1n(n=1,2,1),即顾客所处位置并非排队系统中等待队列的末尾位置，可分为下面两种a)nn+1：当前接受服务的c个顾客的剩余服务时间大于下一个插队顾客的剩余到达时间。b）n n 一1：当前全忙的c个服务台服务完成一个顾客的剩余时间小于下一个插队顾客的剩余到达时间。情形2 n=m，即顾客所处位置为等待队列的末尾这表明系统中的顾客数已经为m+c(c位顾客正在接受服务，m位顾客处于等待服务状态)，此时新到的顾客由于容量的限制不得不直接离开系统。因此，位置m上的顾客的队列序号变化只能是向前移动一位，即mm一1。令Ti为在等待队列前n个位置插队成功的顾客的剩余到达时间，T为c个服务台全忙时服务完一个顾客的剩余服务时间，min(T1,T2）为处于位置n顾客的位置序号改变的时间，于是有如下表达式：-入0P(Ti T2=(4)1-rincu+入0=13）处于位置n顾客的位置序号改变时间的概率为入0min T1,T2)t=1-PTi t)P(T t=1-(5)接下来，充分利用吸收时间的马尔可夫过程理论讨论位置n顾客的等待时间分布函数。令Yn表示当前处于等待队列中位置n(n=1,2，m）的顾客其位置序号首次由n变到 n-1 的时间。关于情形1:n(n=1,2,m-1)时在此种情形下，可能由于新到的插队顾客插队成功而使得位置n的顾客朝位置n+1,n十2,，m移动。但不管怎样，经过一段时间的排队等待后，位置n的顾客总是可以到达位置n一1的。为了清楚地描述顾客的状态转移，下面给出其位置的转移概率表达式以及相应的状态转移图，见图1。1（t）=P【t内c个顾客的服务未完成，到达一插队顾客且插队成功Pn,n+1(t)=Pt 内c个顾客的服务未完成,到达=P(T2 t,T i t)-入0(1-,rk)t=e-cAt1-ek=1=入01-rkt +o(t)k=1=入nt +o(t),n =1,2,.,m -1。类似地，Pn,n-1(t)=Pt 内c个全忙服务台服务完一个顾客,插队顾客的剩余到达时间大于t！=P(T2 t,T i t)=e-nAt(1-e-cAt)=ct +o(t)。直n-11427卷吴文青，柯淇淋，唐应辉，陈林入nn+12一1n-1nn+1m-1mcucucu图1位置n顾客的状态转移图将位置n-1视为吸收状态,位置n,n+1,m视为滑过状态，则Yn(n=1,2,，1)服从m一n+1维的位相型分布,且有(-c-入n入n0000cu-c-入n+1入n+10000cu-c-入n+2000Sn=000-c-入m-2入m-20000cu-c-入m-1 入m-10000cucu00So1x(m-n+1)000(m-n+1)x1则由定义2，得到其分布函数的矩阵表达式为P(Yn t)=1-(n)1x(m=n+1)exp(Sn)(m-n+1)x(m-n+1)t)e(m-n+1)1,(6)以及等待时间的期望为EYn=-(n)1x(m-n+1)(m-n+1)x(m-n+1)e(m-n+1)x1(7)关于情形2:n=m时此时位置m上的顾客由于系统容量的原因位置序号只能变到m1，其变化时间即为c个正在接受服务的顾客中某一个服务完毕的时间，于是有PYmt=1-e-ct,t0.进一步，将位置顾客的位置变化时间用位相型分布来表示，则由定义1可知，位m为滑过状态，位置m1为吸收状态，则有Sm=-c,S%=c,m=1。由定义2，得到其分布函数的矩阵表达式为PYmt)=1-mexp(Smt)e1x1,(8)1153期具有插队行为的M/M/排队系统等待时间分析以及等待时间的期望为11EYm=-mSmle1x1(9)-cu接下来，再分析顾客从位置n一直排队到队首并最终接受服务的时间。事实上，这段时间也是一个随机变量，且等待时间Wn就是Yi(i=1,2,n)时间之和，即Wn=Yn+Yn-1+.+Y2+Yi。由定义3可知，等待时间Wn也服从位相型分布，其中位置1,2,，m都是滑过状态，接收服务的状态为吸收状态。于是得到Wn服从（mi+1）维的位相型分布，有=1不可约表示（8,)，且有SnSoBn-100000Sn-1S%-1Bn-200000Sn-2000A=：7000S3S9200000S2S8100000S1000(m0.0一1x00Ax1n=m+(m-1)+.+(m-n+1)=(m-i+1)。21则由定义2，得到其分布函数的矩阵表达式为Wn(t)=PWn t)=1-dixe x p(A x tx1,n=1,2,.：,m,(10)以及等待时间的期望为nEW,=ZEY=12(;)1x(m-i+1(S-1)n(m-i+1)x(m-i+1)e(m-i+1)x1,n=1,2,.,m-1,=1(11)cu-2(3:)1x(mi+1)(S-1)(m-i+1)x(m-i+1)e(m-i+1)x1,n=m。=1顾(t)11627卷吴文青，柯淇淋，唐应辉，陈林注1当=1时，顾客的插队概率为1，此时到达顾客看到系统中有顾客排队等待均选择插队，进一步有ri=0，则表示队列中的排队顾客接受顾客插队，此时有入n=入；ri=1，则表示队列中的排队顾客不接受顾客插队，此时有入n=0。在此种情形下位置n顾客的等待时间有-cu00000cu-cu00000-cu000Sn=000-cu00000cu-cu00000cu00S1x(m-n+1)000(m-n+1)1其分布函数的矩阵表达式为PYn t)=1-(n)1x(m-n+1)exp(Sn)(m-n+1)x(m-n+1)te(m-n+1)x1,以及等待时间的期望为1EYn=-(n)1x(m-n+1)(m-n+1)x(m-n+1)e(m-n+1)x1=000其中(Sn)-1=-。此值恰好是个全忙服务台服务完一个顾cu0011111客所需的平均时间。当=0时，到达顾客无插队行为，此情形等同于=1,ri=1。2.3插队行为下任意一个常规顾客的等待时间分布函数记常规顾客的等待时间分布函数为Wim(t)=PWiM)t),t0。在讨论Wim)的表达式之前，定义两个新变量。P,（i=0,1,，m+c)：顾客到达系统时看到有i位1173期具有插队行为的M/M/排队系统等待时间分析客的稳态概率；q;（i=0,1，m+c-1)：到达且进入系统的顾客看到有i位顾客的稳态概率。首先，由文献1 可知 p=pj,j=0,1,+c。接下来计算 q;(i=0,1,.,m+c-1)的表达式。qi=PN-=j到达顾客能够进入PN-=j,到达顾客能够进入P【到达顾客能够进入】P(N-=jP到达顾客能够进入|N-=i)P到达顾客能够进入PiX1Pi,j=0,1,.,m+c-1,(12)1一Pm+c1-pm+c这里N一表示到达顾客看到的顾客数目。由于常规顾客到达系统时，其自觉加入等待队列队尾排队等待服务。因此，当常规顾客进入系统看到系统中有k个顾客时，如果kc此时没有排队等待服务的顾客，该常规顾客可直接接受服务，其等待时间显然为0。如果kc此时常规顾客不能立即接受服务，需要等待一段时间，且常规顾客在等待队列中的位置为k一c+1。因此有W(mj(t)=PW(m t)=PW(n=0+P0W(M t)c-1m+c-1P(0WMt/N=h)4kqk+k=0k=cc-1m+c-1qk+qkP(Wk-c+1 t)k=0k=cc-1m+c-1qk+qkWk-c+1(t),(13)k=0k=c以及等待时间的期望为m+c-1EW(m=qkE Wk-c+1。(14)k=c2.4插队行为下任意一个插队顾客的等待时间分布函数记插队顾客的等待时间分布函数为Wm(t)=PWm)t),t0。插队顾客到达时系统有两种情况：一是到达时看到的顾客数为n(n=0,1,，c 1)，此时插队顾客将直接接受服务，无需等待；二是到达时看到有顾客数n(n=C,c+1,.，m+c-1)，则此时在队列中排队的只有nc 位顾客，于是此新到顾客成功插队于位置(i=1,2,，n c)11827卷吴文青，柯淇淋，唐应辉，陈林i1的概率为（1-ra）r，前n-c位顾客都拒绝其插队的概率为n一c，于是有3=13=1Wu(t)=PWm t)=PWm=0)+P0Wim t)c-1qk+P(Wit)qck=0m+c-1U-1k-cPW,t)+P(Wk-c+1 t)一qkj=1(j=1k=c+1c-1m-c+1i-1qk+qc Wi(t)+qk1-ri)lri.W;(t)=1k=0k=c+1m-c+1k-cqkWk-c+1(t),(15)j=1k=c+1其中PWit)qc表示此时看到有c位顾客,没有办法插队。插队顾客的等待时间期望值为m-c+1/k-cZ(1-ri)rl)1E Wim=QeEWi+qkEWij=1k=c+1（=1m-c+1/k-cqkEWk-c+1。(16)(j=1k=c+13数值例子本节将结合具体的数值算例来说明上述所得表达式的正确性，以及三种类型顾客等待时间分布函数随时间的变化情况。我们考虑如下一个具有顾客插队行为的M/M/c/m+c排队系统，其中顾客到达率入=0.55，服务台的服务率=0.95，到达顾客中是插队顾客的概率Q=0.3,拒绝率函数ri=e-1/i12,服务台的数量c=3，系统总的容量m+c=18。编写数值计算程序，得到三种类型顾客等待时间分布函数取值，其结果见表1和图2 4。Wn(t)=P(W,t)10.9-n=10.8一n=20.7n=30.6-n=40.5n=50.40.30.210.1一0123456图2任意位置n顾客的等待时间分布函数随时间的变化情况Wim(t)=P(WiMt)10.9950.990.9850.980.9750123456图3常规顾客的等待时间分布函数随时间的变化情况1193期具有插队行为的M/M/c/mc排队系统等待时间分析表1顾客等待时间分布函数的数值计算结果位置n的顾客t常规顾客插队顾客n=1n=2n=3n=4n=50.00.0000000.0000000.0000000.0000000.0000000.9775690.97991610.50.7506000.4083630.1680990.0548870.0147600.9927040.9948031.00.9334350.7609990.5251290.3061810.1524970.9975230.9986131.50.9811620.9130340.7781510.5943350.4035570.9991330.9996072.00.9944040.9694940.9065130.7951160.6437680.9996900.9998832.50.9982710.9894220.9627770.9056860.8108260.9998880.9999643.00.9994490.9963360.9856530.9591270.9075340.9999590.9999883.50.9998200.9987260.9945750.9829880.9574020.9999850.9999964.00.9999400.9995540.9979710.9931130.9812020.9999940.9999994.50.9999800.9998430.9992460.9972650.9919640.9999981.0000005.00.9999930.9999450.9997210.9989280.9966460.9999991.000 0005.50.9999980.9999800.9998970.9995840.9986251.000 0001.000 0006.00.9999990.9999930.9999620.9998400.9994441.0000001.000000均值0.3642060.7284141.0926221.4568291.8210370.0224310.009127Win(t)=P(Wimt)10.9950.990.9850.980.975上0123456图4插队顾客的等待时间分布函数随时间的变化情况从表1和图2 4中可看出随着时间增大，相应等待时间分布函数的取值趋近于1，符合分布函数的一般性质，这说明我们给出的表达式是正确的。从表1和图2 可看出，不同位置上的顾客其等待时间是不同的，位置越靠后的顾客其等待时间越长，因此小于某一时刻的概率就越小。从表1、图3和图4可以明显看出常规顾客和插队顾客的等待时间也是有明显区别的。计算小于某一时刻的概率时，常规顾客的概率明显要比插队顾客的概率小，这说明插队顾客的等待时间比常规顾客的等待时间要短。这也说明插队行为的确会扰乱系统的秩序，使得某些人获利，某些人失利。4结论本文考虑了具有插队行为的M/M/c/m+有限容量排队系统中顾客等待时间分布函数。利用负指数分布和位相型分布，给出了处于等待队列位置n的顾客、任意一个常规顾客和任意一个插队顾客的等待时间分布函数的矩阵表达式，并在此基础上给出了相关指标的数值计算结果。12027卷吴文青，柯淇淋，唐应辉，陈林在本文中，充分利用吸收时间的马尔可夫过程理论对不同类型顾客的位置变化进行了刻画，并得到了相应的矩阵表达式。相比于已经发表文献采用的拉普拉斯变换等，该方法推导简单、所得结果简洁、易于编程实现。在今后的研究中，可将这一思想方法应用在更为复杂的具有插队行为的排队系统中。参考文献1 Chavoushi A A.Analysis of an M/M/1 queue with customer interjection D.Nova Scotia:Dalhousie University,2010.2 He Q M,Chavoushi A A.Analysis of queueing systems with customer interjections J.QueueingSystems,2013,73(1):79-104.3余妙妙基于位相型过程的复杂随机系统研究D。成都：四川师范大学，2 0 12.4吴文青，何刚，唐应辉，等。具有插队和止步行为的M/M/C排队系统J.运筹学学报，2 0 18,2 2(4):127-134.5张元元，吴文青，唐应辉。具有插队和止步行为的M/M/1/m+1排队系统等待时间分析J.应用数学,2 0 19,32(3):495-50 2.6 Wu W Q,Zhang Y Y.Analysis of a Markovian queue with customer interjection and finitebuffer J.Opsearch,2020,57(2):301-319.7 Neuts M F.Matria-Geometric Solutions in Stochastic Models M.Baltimore:The Johns Hop-kins University Press,1981.8田乃硕.休假随机服务系统M.北京：北京大学出版社，2 0 0 1.9】田乃硕，岳德权.拟生灭过程与矩阵几何解M.北京：科学出版社，2 0 0 2.10】唐应辉，唐小我排队论-基础与分析技术M.北京：科学出版社，2 0 0 6.11唐加山排队论及其应用M.北京：科学出版社，2 0 16.