Geo_T-IPH_1排队平稳队长分布的精确解.pdf

本文讨论离散时间 Geo/T-IPH/1 排队,其中 T-IPH 表示可数状态吸收生灭链吸收时间的分布.首先对排队系统建立无限位相拟生灭过程(QBD)模型,然后通过算子几何解方法,得到了过程联合平稳分布的解.在此基础上,进一步得到了所研究排队系统平稳队长分布的精确解.最后,还通过数值例子说明了分析方法的有效性.关键词:Geo/T-IPH/1 排队;QBD 过程;无限位相;平稳队长中图分类号:O226英文引用格式:ZHENG Q Z,FENG P H,ZHANG H B.Explicit solution for stationary queuelength distribution of Geo/T-IPH/1 queueJ.Chinese J Appl Probab Statist,2023,39(4):506516.(in Chinese)1引言离散时间 PH 分布1是有限状态吸收 Markov 链的吸收时间的分布,它在随机模型的分析中有着重要的应用,例如可以参见文献 1,2 等.Shi 等3把离散时间 PH 分布推广到了无限位相的情形,并称之为 IPH 分布,它是可数状态吸收 Markov 链吸收时间的分布,该分布在排队模型中的应用可以参见文献 4,5 等.本文考虑一种特殊的 IPH 分布,即在其表示(,T)中,=(1,0,0,),而T=bacbacba.其中 a,b,c (0,1),a+b+c=1 且 c a.以下称其为 T-IPH 分布,因而 T-IPH 分布是可数状态吸收生灭链吸收时间的分布.众所周知,离散 PH 分布的母函数是有理函数6,而文献 7 指出,T-IPH 分布的母函数是无理函数从而是不 PH 分布.这表明,IPH 分布类严格河南省高等学校重点科研项目(批准号:22B110002)资助.通讯作者,E-mail:zhanghb-.本文 2021 年 10 月 18 日收到,2022 年 1 月 20 日收到修改稿.第 4 期郑群珍,等:Geo/T-IPH/1 排队平稳队长分布的精确解507大于 PH 分布类.所以 T-IPH 分布具有一定的理论意义.同时由定义,经典的 Geo/Geo/1排队忙期分布服从 T-IPH 分布7,从而该分布也具有一定的应用价值.现在考虑离散时间 Geo/T-IPH/1 排队,它是经典的 Geo/PH/1 排队的推广.在文献8 中已对 Geo/T-IPH/1 排队的平稳指标进行了研究,得到了平稳队长与平稳逗留时间分布的概率母函数.在本文中,我们继续研究该排队模型,通过与文献 8 中稍不同的方法建立拟生灭(QBD)过程模型,得到了平稳队长分布的解析解,这是对文献 8 中结果的改进与补充.本文以下各节内容安排如下:第 2 节给出了 Geo/T-IPH/1 排队的描述以及 QBD 过程模型;随后,第 3 节对建立的 QBD 过程求解,得到了联合平稳分布以及排队系统的平稳队长的解.第 4 节给出了一个数值计算的例子,以说明本文分析方法的有效性.最后,第 5 节是本文的小结部分.2模型描述在 Geo/T-IPH/1 排队中,假设顾客的到达发生在时隙 t=n+,n=1,2,.在每一个时隙 n+,以概率 p (0,1)发生一个到达,以概率 1 p,没有发生到达,且不同时隙上的到达是相互独立的.因此相继的到达间隔 A 独立同分布,且共同的分布是几何分布.另外,假设服务的开始和结束发生在时隙 t=n,n=1,2,.服务时间 B 相互独立同分布,且服从表示为(,T)的 T-IPH 分布.进一步假设 A 与 B 相互独立,服务顺序是先到先服务,且一个在时隙 t=n+到达的顾客,在时刻 t=n 如果系统空闲则可直接进入系统接受服务,即本文考虑的是早到系统9.令 Ln表示 t=n 时系统中的顾客数,根据早到规则,一个在时隙 t=n完成服务的顾客不再计入 Ln.令 Jn表示时刻 t=n 时的服务位相.由此可建立二维离散时间 Markov链(Ln,Jn),n 0(注意,文献 8 中考虑的是(Jn,Ln),n 0),其状态空间为E=0 (m,k):m=1,2,k=0,1,.状态转移图如图 1 所示.当状态按字典规则排列时,由图 1 可得过程(Ln,Jn),n 0 的转移概率矩阵为P=B0A0C0BACBACBA.,508应用概率统计第 39 卷图 1QBD 过程(Ln,Jn),n 0 的状态转移图其中B0=(p),A0=(p,0,0,),C0=(pc,0,0,)T,B=pb+pcpapcpbpapcpbpa.,A=pbpapcpbpapcpbpa.,C=pc00.这里规定 p,1 p.因此所建立模型是一个离散时间 QBD 过程10.由文献 7 可知,本文所示 T-IPH 分布的均值为 1/(c a),从而所考虑排队系统稳定的条件为 =p/(c a)0 的平稳分布.首先是初始分量,由文献 8 可知 0=1 ,而 1通过求解方程组(3)可得.有下述结论:引理 1向量 1=(10,11,)的分量由下式给出:1k=ppc(1 )rk,k=0,1,(4)其中r,12pc1 pb(1 pb)2 4p2ac(0,1)是一个常数.证明:首先由方程组(3)左边系数矩阵是随机矩阵易得率阵 R 第一列 r1为r1=(pcpc,ppc,ppc,)T,(5)其中 c=1 c.代入方程(3),由其分量形式可得 10=0p/(pc)=(1 )p/(pc)以及p0+(p+pb)10+(p+pc)11+pk=11k=0,(6)pa1k(1 pb)1,k+1+pc1,k+2=0,k=0,1,.(7)方程(7)是一个二阶齐次线性差分方程,易求得其通解为1k=c1rk+c2sk,k=0,1,510应用概率统计第 39 卷其中r=1 pb(1 pb)2 4p2ac2pc,s=1 pb+(1 pb)2 4p2ac2pc是方程的两个特征根而 c1,c2是待定常数.通过简单的代数运算容易验证 0 r 1.所以由 1e 0.(9)对固定的 m,这是一个二阶线性非齐次差分方程.因此,由式(4)出发,对 m 用数学归纳法即得定理结论.?对式(8)中的待定系数 fm1,l,m=0,1,l=0,1,m 1,其中第一个下标表示其属于分量 m,第二个下标表示一共有 m 个.以下讨论如何确定这些系数的值,目的是对任意的 m 1,找到分量 m与 m+1中两组待定常数的递推关系式,而初始值由式(4)知为 f00=1.这时有以下两个引理:引理 3对 m=1,2,系数 fm0满足以下关系:fm0=m1l=0Slfm1,l,(10)第 4 期郑群珍,等:Geo/T-IPH/1 排队平稳队长分布的精确解511其中S0=11 r c,Sl=1(1 r)l+1l1k=0E(l,k)rk+1,l 1.(11)而 E(l,k)是 Euler 多项式,表达式如下:E(l,k)=ki=0(1)i(l+1i)(k i+1)l,k=0,1,l 1.证明:固定 m 1,由算子几何解(1)以及式(5)可得m+1,0=pcpcm0+ppck=1mk,把式(8)代入上式,解出 fm0可得fm0=cfm1,0+k=1m1l=0(fm1,lkl)rk=cfm1,0+m1l=0(fm1,lk=1klrk).显然,对任意非负整数 l,无穷级数k=1klrk收敛,因而可定义S0=c+k=1rk=11 r c,Sl=k=1klrk,l 1,由此即得式(10).最后,式(11)由 Euler 多项式的定义可得11.?引理 4对非负整数 m=0,1,定义 fm=(fm0,fm1,fmm),对正整数m=1,2,定义 gm=(fm1,fm2,fmm),对正整数 i=1,2,定义i=1i(pcr2i+pb 1),i=1i(cr2i+b).(12)则有gm=fm1Tm,(13)这里Tm=pc1t112A12t2t113.Am3m2tm2Am4m2tm3t11m 1Am2m1tm1Am3m1tm2A1m1t2t11m512应用概率统计第 39 卷是一个 m 阶下三角方阵,其中 =(1 pb)2 4p2ac,而 t1,t2,tm由递推关系tk=k(k 1)!+1ki=11i!tkii+1,k=1,2,(14)及初始条件 t0=a/r+b+cr 确定.证明:因为 m+1,k和 mk满足差分方程(9),所以把式(8)代入方程(9)并化简,可得两组待定常数满足如下等式:paml=0fmlkl(1 pb)ml=0fml(k+1)lr+pcml=0fml(k+2)lr2=pacm1l=0fm1,lkl pbcm1l=0fm1,l(k+1)lr+pc2m1l=0fm1,l(k+2)lr2.在上式两边先关于 k 求 j 1 阶导数,然后令 k=0,通过化简可得ml=jfmlAj1lr(pcr2lj+1+pb 1)=pc(j 1)!(a+br+cr2)fm1,j1 pcm1l=jfm1,lAj1lr(b+cr2lj+1),其中 j=1,2,m,而 Akm表示排列数.由此解出 fmj并且恒等式 1 pb 2pcr=化简,可得fmj=1ml=j+1(lj)lj+1fml+pcjfm1,j1+m1l=j(lj)lj+1fm1,l,其中 ,a/r+b+cr,i和 i由式(12)确定.最后,显然上式的矩阵形式为 gm=gmUm+fm1Vm,这里 Um,Vm分别是如下所示的 m 阶下三角方阵:Um=10(21)20(31)3(32)20.(m 11)m1(m 12)m2(m 1m 2)20(m1)m(m2)m1(mm 2)3(mm 1)20,第 4 期郑群珍,等:Geo/T-IPH/1 排队平稳队长分布的精确解513Vm=pc(11)12(21)2(22)13.(m 21)m2(m 22)m3(m 2m 2)1m 1(m 11)m1(m 12)m2(m 1m 2)2(m 1m 1)1m.因矩阵 Im Um非奇异,所以为了完成引理的证明,只须证明 Vm(Im Um)1=Tm,即Tm Vm=TnUm,而由分量形式,上式成立当且仅当Aij1i1tij(i 1j)ij=1il=jAil1i1til(lj)lj+1对 i=2,3,和 j=1,2,i 成立,这里规定 1=0,A1k=(k+1)1,k=0,1,.显然,上式又等价于(i 1)!j!tij(i 1)!j!(i j 1)!ij=(i 1)!j!1il=j1(l j)!tillj+1 tij=ij(i j 1)!+1il=j1(l j)!tillj+1 tk=k(k 1)!+1k+jl=j1(l j)!tkl+jlj+1 tk=k(k 1)!+1ki=01i!tkii+1,k=0,1,2,.因此,由 1=0 及式(14)即可得引理结论.?现在,由引理 3 和引理 4,即可得联合平稳分布(8)中待定系数所满足的递推关系,有如下定理:定理 5令 Sm=(S0,S1,Sm1)T.则系数 fm满足以下递推关系:fm=fm1Sm,Tm,m=0,1,(15)其中初始值为 f0=f00=1.最后,在所得结论的基础上,可得本文所研究排队系统的平稳队长分布,这也是本文的主要结论,有以下定理:514应用概率统计第 39 卷定理 6在排队系统 Geo/T-IPH/1 平稳队长分布 p=(p0,p1,)中,p0=1 ,其余分量由下式确定:pm=(1 )(fm0+cfm1,0)(ppc)m,m=1,2,.(16)证明:平稳队长分布 p 是 QBD 过程(Ln,Jn),n 0 对水平的边缘分布,从而p0=1 ,且对 m 1,有pm=PLn=m=m=k=0mk,再把式(8)代入,可得pm=k=0(1 )(ppc)m(m1l=0fm1,lkl)rk=(1 )(ppc)mfm1,0(S0+c)+m1l=1fm1,lSl=(1 )(ppc)m(cfm1,0+m1l=0fm1,lSl).再由式(15),上述最后一式中求和的值为 fm0,从而完成定理证明.?4数值算例在上一节中,我们得到 QBD 过程联合平稳分布以及 Geo/T-IPH/1 排队平稳队长分布的解,分别如式(8)和(16)所示,其中系数 fnk 由一系列递推公式给出.本小节,为了说明我们分析方法的有效性,考虑一个具体的数值计算例子.显然问题的关健是计算系数 F=(fml).给定 m=0,1,M,l=0,1,m1,则可通过以下各步完成:(i)由式(11)计算 Sm.或者由 Sm的定义,通过计算 SmrSm,容易验证 Sm也满足以下递推关系:S0=c+11 r,Sm=r1 rm1k=0(nk)Sk+rc1 r,m 1;(ii)由式(10)计算 fm0,其中初值为 f00=1;(iii)由式(14)计算 tk,其中初值为 t0=a/r+b+cr;(iv)由式(13)计算 fmk,而该式的分量形式为fmk=pc(fm1,k1k+m1i=kAikitik+1fm1,i),m 1,1 6 k 6 m.第 4 期郑群珍,等:Geo/T-IPH/1 排队平稳队长分布的精确解515有了系数 F 的数值结果,再由式(8)和(16)就可以得到联合平稳分布和平稳队长分布的数值结果.下面是一个具体的例子.设参数取值为 p=0.3,a=0.1,c=0.5,所以=0.75.这时联合平稳分布和平稳队长分布的部分数值结果如表 1 和表 2 所示.表 1联合平稳分布的部分数值结果 nk,n 6 6 6 5,k 6 6 6 4nkk=0k=1k=2k=3k=4n=12.143 1012.192 1022.243 1032.295 1042.348 105n=21.128 1012.603 1024.146 1035.758 1047.443 105n=37.476 1021.917 1024.120 1037.427 1041.191 104n=45.276 1021.392 1023.339 1037.105 1041.349 104n=53.816 1021.017 1022.563 1035.966 1041.270 104表 2平稳队长分布的前 10 个数值结果 pn,n 6 6 6 9n01234pn2.500 1012.387 1011.436 1019.894 1027.090 102n56789pn5.164 1023.793 1022.798 1022.070 1021.534 1025小结本文通过 QBD 过程和算子几何解方法,讨论了离散时间排队 Geo/T-IPH/1 排队平稳队长分布律的计算问题.得到了 QBD 过程的联合平稳分布和排队系统平稳队长分布,分别由式(8)和式(16)给出,其中的系数由递推关系(15)给出.从这些结果出发,可以得到联合分布以及平稳队长分布的数值解.从平稳队长分布出发,可进一步讨论等待时间、忙期等其它指标,这是值得进一步研究的问题.另外,在文中考虑的 T-IPH 分布的表示中,比较特殊,若 具有一般形式 =(1,2,),这时分布的性质,以及相应的排队模型的研究,也是值得进一步考虑的问题.参考文献1 NEUTS M F.Matrix-Geometric Solutions in Stochastic Models:An Algorithmic ApproachM.Bal-timore:Johns Hopkins University Press,1981.2 BREUER L,BAUM D.An Introduction to Queueing Theory and Matrix-Analytic MethodsM.Dor-drecht:Springer,2005.516应用概率统计第 39 卷3 SHI D H,GUO J L,LIU L M.SPH-distributions and the rectangle-iterative algorithmC/CHAKRAVARTHY S R,ALFA A S.(eds)Matrix-Analytic Methods in Stochastic Models.Boca Ra-ton:CRC Press,1997:207224.4 ALFA A S.Discrete time queues and matrix-analytic methods(with discussion)J.TOP,2002,10(2):147210.5 ALFA A S.Queueing Theory for Telecommunications:Discrete Time Modelling of a Single NodeSystemM.New York:Springer,2010.6 OCINNEIDE C A.Characterization of phase-type distributionsJ.Commun Statist Stochastic Mod-els,1990,6(1):157.7 张宏波,侯振挺.T-IPH 分布的若干性质及其在排队论中的应用J.应用概率统计,2015,31(2):193198.8 ZHANG H B,HOU Z T,SHI D H.Analysis of stationary queue length distribution for Geo/T-IPH/1queueJ.J Oper Res Soc China,2013,1(3):415424.9 HUNTER J J.Mathematical Techniques of Applied Probability,Vol.2,Discrete Time Models:Tech-niques and ApplicationsM.New York:Academic Press,1983.10 LI Q L.Constructive Computation in Stochastic Models with Applications:The RG-Factorization-sM.Beijing:Tsinghua University Press;Heidelberg:Springer,2010.11 HIRZEBRUCH F.Eulerian polynomialsJ.M unster J Math,2008,1(1):914.Explicit Solution for Stationary Queue Length Distribution ofGeo/T-IPH/1 QueueZHENG QunzhenFENG PinghuaZHANG Hongbo(School of Statistics and Mathematics,Henan Finance University,Zhengzhou,450046,China)Abstract:In this paper we study a discrete-time Geo/T-IPH/1 queue model,where T-IPH denotes thediscrete-time phase type distribution defined on a birth and death process with countably many states.The queue model can be described by a quasi-birth-and-death(QBD)process with countably many phases.Using operator-geometric solution method,we first give the expression of the joint stationary distribution.Then we obtain the explicit stationary queue length distribution of the queue we considered.Finally,anumerical example is also presented to illustrate the computational procedure.Keywords:Geo/T-IPH/1 queue;QBD process;infinite phases;stationary queue length2020 Mathematics Subject Classification:60K25;90B22