带有两类故障和延迟维修的M_G_1重试排队_陈芹.pdf

第40卷第2期2023年06月Vol.40，No 2Jun.2023阜阳师范大学学报（自然科学版）Journal of Fuyang Normal University（Natural Science）带有两类故障和延迟维修的 M/G/1 重试排队陈芹，高珊*(阜阳师范大学 数学与统计学院，安徽 阜阳 236037)摘要：研究带两类故障和延迟维修的 M/G/1 重试排队模型。针对系统平稳性及其平稳分布的问题，首先采用嵌入马尔科夫链和补充变量法得到稳态条件和平稳概率分布，然后用概率母函数研究系统队长分布，最后通过数值算例分析参数对系统性能指标的影响。关键词：延迟维修；补充变量法；嵌入马尔科夫链；M/G/1 排队；重试排队中图分类号：O226文献标识码：A文章编号：2096-9341（2023）02-0007-06DOI:10.14096/34-1069/n/2096-9341（2023）02-0007-06M/G/1 retrial queue with two-type breakdowns and delayed repairsCHEN Qin,GAO Shan（School of mathematics and statistics,Fuyang Normal University,Fuyang Anhui 236037,China）Abstract:The M/G/1 retrial queue model with two types of breakdowns and delayed repairs is studied.For the problem ofsystems stability and stationary distribution of the system,the stationary condition and stationary probability distribution are ob-tained using embedded Markov chain and supplementary variable method firstly.Then the probability generating function isused to study the system queue length distribution.Finally,numerical examples are given to illustrate the impact of system pa-rameters on the system performance measures.Keywords:delayed repairs;supplementary variable method;embedded Markov chain;M/G/1 queue;retrial queue由于重试排队模型在呼叫中心、计算机通信和供应链管理等领域的应用，重试排队得到了广泛的关注。重试排队系统的特点是当顾客到达发现服务台空闲会立即接受服务，否则他们将离开服务区，进入重试组并在一段时间后继续请求服务直到成功。Falin1研究重试排队模型给出了相关概述，文献2-7推广了重试排队模型。目前在重试排队模型基础上加入服务器故障成为研究热点，其中服务器故障主要包含主动故障、被动故障。Kulkarni 等人8研究了带有服务器故障的重试排队模型。此后文献9-15，17-20继续研究了此类排队模型。Choudhury16提出了被动故障发生时，服务器不能及时获得维修而导致维修延迟的重试排队模型。本文在前人研究的基础上，对 M/G/1 重试排队模型同时考虑被动故障和主动故障，且主动故障可以由内部因素和外部因素引起。该模型中的故障类型具体如下：（1）被动故障：服务器在闲期发生的故障。（2）主动故障：服务器在工作过程中发生的故收稿日期：2022-07-02基金项目：安徽省自然科学基金项目（2108085MA08，1908085MF192）；安徽省高校自然科学研究项目（KJ2020A0530）；阜阳师范大学自然科学研究项目（2020FSKJ14）资助。作者简介：陈 芹(1992-)，女，硕士，讲师，主要研究方向：可靠性理论，排队论等。通讯作者：高 珊(1975-)，女，博士，教授，研究方向：排队论，Email:sgao_。陈芹，高珊：带有两类故障和延迟维修的 M/G/1 重试排队第40卷阜阳师范大学学报（自然科学版）8障，有以下两种类型：因内部因素引发的故障（服务器寿命有限）；由外部因素引发的故障（病毒入侵，外部冲击，操作失误）。1模型介绍对于 M/G/1 的重试排队系统，假设如下：（1）顾客到达的时间间隔服从参数为 的指数分布。服务时间 B 服从一般分布，其概率分布函数为B(x)B(0)=0，密度函数b(x),Laplace 变换为B?(s)，存在有限的 1，2 阶矩分别为1,2。如果到达的顾客发现服务器空闲将立即接受服务；当发现服务器正忙于其他顾客或处于维修状态时，该顾客将进入重试组中按照先进先出的原则不断进行重试，直到重试成功。（2）服务器在忙期，可能会发生主动故障，主动故障的发生时间服从参数为的指数分布。其中由内部因素引发的故障的概率 p，由外部因素引起故障的概率为 1-p，记为p。当服务器因内部因素引起的故障中断时，正在接受服务的顾客在服务器前等待服务器修复完成后继续接受其剩余的服务。内部因素引起的故障维修时间R1服从一般分布，分布函数为R1(x)，密度函数为r1(x)，存在有限的 1，2 阶矩分别为v1,v2；当服务器因外部因素引起的故障中断时，正在接受服务的顾客离开系统，同时服务器开始维修，维修时间R2服从一般分布，分布函数为R2(x)，密度函数为r2(x)，存在有限的 1，2 阶矩分别为1,2。（3）当服务器空闲时，可能会发生被动故障，被动故障的发生时间服从参数为 的指数分布。然而，由于在空闲时间缺乏对服务器的监管，当被动故障发生时，服务器无法立即得到修复，直到顾客从外部或重试组（重试组如果有顾客的话）到达服务器时服务器才启动维修，而触发服务器启动维修的顾客在服务台前等待服务器维修结束后立即开始接受服务。被动故障维修时间G服从一般分布，概率分布函数为G(x)，密度函数为g(x)，存在有限的 1，2 阶矩1,2。（4）当服务器空闲时，只有重试组队首的顾客允许重试，重试时间服从参数为的指数分布。（5）以上所有随机过程假设都是相互独立的。对于分布函数F(x)，记F(x)=1-F(x)表示F(x)的尾部分布，F?(s)=0e-sxdF(x)为F(x)的 Laplace-Stieltjes 变换，F?*(s)=0e-sxF(x)dx为F(x)的 Laplace变 换。设(x)=b(x)-B(x),(x)=g(x)-G(x),v1(x)=r1(x)-R1(x),v2(x)=r2(x)-R2(x),分别为服务时间，被动故障维修时间，主动故障中由内部因素引起的故障维修时间，由外部因素引起的故障维修时间的条件完成率。该排队模型可用于计算机网络模型中。当没有信息需要传输时，工作人员会做其他工作，这时服务器出现被动故障无法立即发现并维修，只有新的信号到达才能发现服务器故障并维修。在信息传输过程中服务器可能会中病毒使得正在传输的信息被移除；正常传输过程中因服务器寿命有限也会发生故障，这两种故障都会立即得到维修，但是维修时间有所不同。2稳态条件设SB表示顾客开始接受服务到服务完成或由外部因素引起的故障维修完成的时间间隔，分布函数为SB(x)，Laplace 变换为S?B(x)，则有SB(t)=P(SBt)=0tk=0R(k)1(t-u)e-u(u)kk!pkdB(u)+0tk=1R(k-1)1*R2(t-u)e-uk(k-1)!uk-1-ppk-1-B(u)du,S?B(s)=0e-stdSB(t)=B?(s)+-pR?2(s)1-B?(s)(s),ESB=-(S?B(s)|s=0=1-B?(-p)(1+1+pv1-p)=*1,ESB2=(S?B(s)|s=0=2(1-B?(-p)+21(1+pv1)(B?(-p)-p+1-B?(-p)-p+1-B?(-p)pv2+2B?(-p)(1+pv1)2-p+2(1-B?(-p)(1+pv1)2(-p)2，其中(s)=s+(1-pR?1(s)，设ak表示被动故障维修期间进入重试组 k 个顾客的概率，hk为广义服务期间进入重试组 k 个顾客的概率。则ak=0(t)kk!e-tdG(t),第2期陈芹，高珊：带有两类故障和延迟维修的M/G/1重试排队9hk=0(t)kk!e-tdSB(t),A(z)=k=0zkak,H(z)=k=0zkhk,(z)=(1-z),A(z)=G?(z),H(z)=B?(z)+-pR?2(z)1-B?(z)(z)，A(1)=dA(z)dz|z=1=1=1,A(1)=d2A(z)dz2|z=1=22=2,H(1)=dH(z)dz|z=1=*1=,H(1)=d2H(z)dz2|z=1=2*2=*.设ck为被动故障维修与广义服务期间有 k 个顾客进入重试组的概率。ck=k=0aihk-i，k0，C(z)=k=0zkck=A(z)H(z).令Tk(T0=0)为第 k 个广义服务结束时刻，Nk=N(Tk)为时刻Tk时的重试组中的顾客数，则Nk,k0为嵌入 Markov 链，其状态空间为自然数集。定理 1Nk,k0是具有遍历性的 Markov链的充要条件为+10,j=i-1;+hj-i+1+hj-i+(+cj-i+1+cj-i)i0,ji-1；0其他情况。平均漂移为i=ENk+1-Nk|Nk=i=|+1i=0;+1-+i0.由 Foster s 准则，得到系统处于稳态的充分条件是+1+。用反证法证明其必要性。假设+1+，即i0时，i0，由一步转移概率可知i=j0.对所有i0都有i0，所以Nk,k0不具有遍历性，必要性得证。3系统稳态概率分析本节用补充变量法研究系统稳态概率分布。设系统在任意时刻的状态空间可由X(t),t0=N(t),J(t),1(t),2(t),4(t),5(t),t0表 示,其 中N(t)表示重试组中的顾客数，J(t)表示服务器的状态：J(t)=|0 闲时;1 忙时;2 内部因素引起的主动故障维修;3 延迟维修;4 被动故障维修;5外部因素引起的主动故障维修。当J(t)=1，1(t)是已逝服务时间；当J(t)=2，2(t)是内部因素引起的主动故障的已逝维修时间；当J(t)=4，4(t)表示被动故障的已逝维修时间；当J(t)=5，5(t)表示外部引起的主动故障已逝维修时间。因为到达时间间隔服从指数分布，由 Burke s定理，当+1+时，X(t)的稳态概率存在且是正的。假设+1+，且N,J,1,2,4,5是 Markov 过 程N(t),J(t),1(t),2(t),4(t),5(t),t0的极限过程。定义Pn,j=PN=n,J=j=limtPn,j(t),n0,j=0,3;Pn,j(x)dx=PN=n,J=j,xjx+dx=limtPn,j(t,x)dx,n0,j=1,4,5;Pn,2(x,y)dxdy=PN=n,J=2,x1x+dx,y20;xPn,2(x,y)=-(+1(y)Pn,2(x,y)+Pn-1,2(x,y);P0,3=P0,0;(+)Pn,3=Pn,0,n1;ddxPn,4(x)=-(+(x)Pn,4(x)+Pn-1,4(x),n0,x0;ddxPn,5(x)=-(+2(x)Pn,5(x)+Pn-1,5(x),n0,x0.这里P-1,1(x)=P-1,2(x,y)=P-1,4(x)=P-1,5(x)=0边界条件为|Pn,1(0)=Pn,0+Pn+1,0+0Pn,4(x)(x)dx,n0;Pn,2(x,0)=pPn,1(x);Pn,4(0)=Pn,3+Pn+1,3;Pn,5(0)=p 0Pn,1(x)dx.将上述等式左右同时乘以zn，并对 n 从 0 到进行求和，求解方程，定理得证。由定理 2 易得定理 3。定理 3（1）服务器忙时的重试组顾客数的边际概率生成函数为P1(z)=N1(z)D(z)1-B?(z)(z)P0,0;（2）由内部因素引起的主动故障维修期间的重试组顾客数的边际概率生成函数为P2(z)=p1-R?1(z)(z)P1(z);（3）被动故障维修期间的重试组顾客数的边际概率生成函数为P4(z)=N2(z)D(z)1-G?(z)(z)P0,0;（4）由外部因素引起的主动故障维修期间的重试组顾客数的边际概率生成函数为P5(z)=p 1-R?2(z)(z)P1(z).由正规化方程n=0(Pn,0+Pn,3)+n=00(Pn,1(x)+Pn,4(x)+Pn,5(x)dx+n=000Pn,2(x,y)dxdy=1和上述定理可得以下推论。推论 1在稳态条件下，服务器各状态概率分别如下：（1）服务器处于闲时的概率P0=P0(1)=(+)(1-)+)(+)1+(+)(+);（2）服务器处于忙时的概率P1=P1(1)=1-B?(p)p;（3）服务器处于由内部因素引起的主动故障维修期间的概率P2=P2(1)=p1P1;（4）服务器处于延迟维修的概率P3=P3(1)=(+)(1-)-1)(+)1+(+)(+);（5）服务器处于被动故障维修期间的概率P4=P4(1)=1(+)(1-)+)(+)1+(+)(+);（6）服务器处于由外部因素引起的主动故障维修期间的概率P5=P5(1)=p 1P1.设(z)=EzN为重试组中等待的顾客数概率生成函数，NS为平稳状态下任意时刻顾客数，并且概率生成函数为(z)=EzNS，则(z)=j=05Pj(z),(z)=P0(z)+zP1(z)+zP2(z)+P3(z)+zP4(z)+P5(z)。由定理 3 易得下述推论。推论 2重试组中等待的顾客数概率生成函数为(z)=N(z)D(z)P0,0这里N(z)=(z+)(C(z)-H(z)+(+)(+)(z-1),P0,0=D(1)N(1).定理 4设LO,LS是平均重试组顾客数和平均系统顾客数，则LO=EN=ddz(z)|z=1=N(1)2N(1)-D(1)2D(1),LS=ENS=ddz(z)|z=1=LO+P1+P2+P4.这里N(1)=(+)1+(+)(+),N(1)=21+(+)(2+21),D(1)=(+)-(+)(+)+1),D(1)=-(+)(2+(+)*)-21(+(+)3.23.02.82.62.42.22.01.812345678910=0.1=0.2=0.3=0.4(a)LS3.02.82.62.42.22.01.812345678910=0.1=0.2=0.3=0.4(b)LO1.60.850.800.750.700.650.600.5512345678910=0.1=0.2=0.3=0.4(c)A0.300.280.260.240.220.1812345678910=0.1=0.2=0.3=0.4(d)Wf0.160.20图 1(a)(b)(c)(d)分别为取 0.1,0.2,0.3,0.4 时，对LS，LO，A，Wf数值大小的影响4数值分析假设=0.5，服务时间BExp(1)，均值为11，Laplace 变换为B?(s)=1s+1。被动故障维修时间GExp(2)，均值为1=12，Laplace 变换为G?(s)=2s+2，由内部因素引起的主动故障维修时间R1Exp(3)，均 值 为1=13，Laplace 变 换 为R?1(s)=3s+3，由外部因素引起的主动故障维修时间R2Exp(4)，均值为1=14，Laplace 变换为R?2(s)=4s+4，在平稳的条件+1+下，令各参=1,1=5,2=4,3=3,4=2,p=0.7。设 系 统 处 于 稳 态 下 服 务 器 可 用 率 为 A,则A=P0+P1，服务器故障率为Wf，则Wf=P0+P1。由图 1 可以看出重试率从 1 变到 10 的过第2期陈芹，高珊：带有两类故障和延迟维修的M/G/1重试排队11且概率生成函数为(z)=EzNS，则(z)=j=05Pj(z),(z)=P0(z)+zP1(z)+zP2(z)+P3(z)+zP4(z)+P5(z)。由定理 3 易得下述推论。推论 2重试组中等待的顾客数概率生成函数为(z)=N(z)D(z)P0,0这里N(z)=(z+)(C(z)-H(z)+(+)(+)(z-1),P0,0=D(1)N(1).定理 4设LO,LS是平均重试组顾客数和平均系统顾客数，则LO=EN=ddz(z)|z=1=N(1)2N(1)-D(1)2D(1),LS=ENS=ddz(z)|z=1=LO+P1+P2+P4.这里N(1)=(+)1+(+)(+),N(1)=21+(+)(2+21),D(1)=(+)-(+)(+)+1),D(1)=-(+)(2+(+)*)-21(+(+)3.23.02.82.62.42.22.01.812345678910=0.1=0.2=0.3=0.4(a)LS3.02.82.62.42.22.01.812345678910=0.1=0.2=0.3=0.4(b)LO1.60.850.800.750.700.650.600.5512345678910=0.1=0.2=0.3=0.4(c)A0.300.280.260.240.220.1812345678910=0.1=0.2=0.3=0.4(d)Wf0.160.20图 1(a)(b)(c)(d)分别为取 0.1,0.2,0.3,0.4 时，对LS，LO，A，Wf数值大小的影响4数值分析假设=0.5，服务时间BExp(1)，均值为11，Laplace 变换为B?(s)=1s+1。被动故障维修时间GExp(2)，均值为1=12，Laplace 变换为G?(s)=2s+2，由内部因素引起的主动故障维修时间R1Exp(3)，均 值 为1=13，Laplace 变 换 为R?1(s)=3s+3，由外部因素引起的主动故障维修时间R2Exp(4)，均值为1=14，Laplace 变换为R?2(s)=4s+4，在平稳的条件+1+下，令各参=1,1=5,2=4,3=3,4=2,p=0.7。设 系 统 处 于 稳 态 下 服 务 器 可 用 率 为 A,则A=P0+P1，服务器故障率为Wf，则Wf=P0+P1。由图 1 可以看出重试率从 1 变到 10 的过第40卷阜阳师范大学学报（自然科学版）12程中，系统平均顾客数LS与重试组中平均顾客数LO，服务器可用率A和服务器故障率Wf逐渐递减。当被动故障发生率从 0.1 增加到 0.4 的过程中，系统平均顾客数LS，重试组中的平均顾客数LO和服务器故障率Wf逐渐增加。服务器可用率A逐渐减小。故降低故障率可以提高服务效率，符合预期要求。5小结本文分析了带有两类故障延迟维修的 M/G/1排队服务模型。首先获得系统处于稳态的条件，然后分析计算得出系统稳态的各项指标如系统平均顾客数与重试组中的平均顾客数，最后通过数值举例来说明参数对系统指标的影响。参考文献：1FALIN G.A survey of retrial queues J.QueueingSystems,1990,7(2):127-167.2FALIN G.TEMPLETON J G C.Retrial Queues M.London:Chapman and Hall,1997.3ARTALEJO J R.A classified bibliography of researchon retrial queues:progress in 1990-1999 J.Top,1999,7(2):187-211.4ARTALEJO J R.Accessible bibliography on retrialqueues:Progress in 2000-2009 J.Mathematical andComputer Modelling,2010,51(9):1071-1081.5GAO S,ZHANG J.Strategic joining and pricing poli-cies in a retrial queue with orbital search and its appli-cation to call centers J.IEEE Access,2019,7:129317-129326.6ZHANG Y.Optimal pricing analysis of computer net-works based on a queueing system with retrial mecha-nism J.IEEEAccess,2020,8:137490-137500.7ZIREM D,BOUALEM M,ADEL-AISSANOU K,etal.Analysis of a single server batch arrival unreliablequeue with balking and general retrial time J.QualityTechnology and Quantitative Management,2019,16(6):672-695.8KULKARNI V G,CHOI B D.Retrial queues withserver subject to breakdowns and Repairs J.Queue-ing Systems,1990,7(2):191-208.9FALIN G.An retrial queue with an unreliable serverand general repair times J.Performance Evaluation,2010,67(7):569-582.10WANG J T.Reliability analysis M/G/1 queues withgeneral retrial times and server Breakdowns J.Prog-ress in Natural Science-Materials International,2006,16(5):464-473.11GMEZ-CORRAL A.Stochastic analysis of a singleserver retrial queue with general retrial times J.Na-val Research Logistics,1999,46(5):561-581.12KRISHNA KUMARB,RUKMANIR,THANI-KACHALAM A,et al.Performance analysis of retrialqueue with server subject to two types of breakdownsand repairs J.Operations Research,2018,18(2):521-559.13LV S L,ZHU L M.Single Server Repairable QueueingSystem With Variable Service Rate and Failure RateJ.IEEEAccess,2021,9:1233-1239.14WANG J T,LIU B.Equilibrium joining strategies inthe Mn/G/1 queue with server breakdowns and repairsJ.Operations Research,2020,20(4):2163-2187.15GAO S,WANG J T.Reliability and availability analy-sis of a retrial system with mixed standbys and an unre-liable repair facilityJ.Reliability Engineering andSystem Safety,2021,205:107240.16CHOUDHURY G,TADJ L.An M/G/1 queue with twophases of service subject to the server breakdown anddelayed repair J.Applied Mathematical Modelling,2009,33(6):2699-2709.17CHOUDHURY G,KE J C.An unreliable retrial queuewith delaying repair and general retrial times underBernoulli vacation schedule J.Applied Mathematicsand Computation,2014,230:436-450.18GAO S,ZHANG J,WANG X C.Analysis of a retrialqueue with two-type breakdowns and delayed repairsJ.IEEEAccess,2020,8:172428-172442.19KE J C,HUANG K B,KUO C C.Reliability-basedmeasures for a batch-arrival queue with an unreliableserver and delayed repair under randomised vacationsJ.International Journal of Industrial and Systems En-gineering,2017,27(4):500-525.20MALIK G,UPADHYAYA S,SHARMA R.ParticleSwarm Optimization and Maximum Entropy Resultsfor MX/G/1 Retrial G-Queue with Delayed Repair J.International Journal of Mathematical,Engineeringand Management Sciences,2021,6(2):541-563.