带有负顾客和N-策略的Geo_Geo_1排队模型均衡策略分析.pdf

应用数学MATHEMATICA APPLICATA2024,37(2):289-302带有负顾客和N-策略的Geo/Geo/1排队模型均衡策略分析张恒,刘力维(南京理工大学数学与统计学院,江苏 南京 210094)摘要：本文提出带有负顾客、N-策略休假和待机时间的Geo/Geo/1迟到达排队模型,并研究了此模型下的稳态条件、不同信息水平下顾客的策略和系统吞吐量的优化问题.负顾客到达发生在服务台在线阶段,其到达会抵消一个正在被服务的正顾客,即清除队列头部的顾客(RCH).为此,系统设置了N-策略休假机制,即系统处于休假时,服务台不提供服务,此时负顾客也不会到达系统;直到顾客数目累积至N时,休假自动结束,服务台开始运行并按FCFS原则提供服务.系统一旦变空,会有一段待机时间,待机结束后,服务台关闭并进入休假.模型借助N-策略设置避免了频繁启动和关闭服务台造成的损耗,同时削弱了负顾客对系统产生的不良影响.分析得到了顾客在不同信息水平下的策略行为,同时给予系统管理者对于N-策略和信息展示水平的选择参考.最后通过数值模拟,验证了N-策略的保护作用和系统性能指标的敏感性.关键词：N-策略;负顾客;吞吐量;信息水平中图分类号：O226;F224.34AMS(2010)主题分类：90B22;60K25文献标识码：A文章编号：1001-9847(2024)02-0289-141.引言排队现象渗透在生活的方方面面,存在于所有服务系统.它既包含了如核酸检测、医院挂号等实体排队系统,同时也包括计算机数据处理、线上APP点餐等虚拟排队系统.实际生产环境中的外部干扰会导致产品报废,这类干扰可定义为排队论中的负顾客到达.并且,新顾客的到达与离开导致机器的频繁开启和关闭会造成能源浪费.基于上述现象,可考虑设置N-策略休假和待机时间来减少此类负面影响.带有N-策略休假的排队模型研究主要集中在系统的性能分析,N-策略作为一种控制方法来优化系统的各项性能指标、提升服务效率,而对此情形下顾客的策略行为则少有讨论.文1首次在M/M/1系统中提出了N-策略的概念.之后,文2总结了一系列带有假期的排队模型及常用的研究方法.文3将休假和可修模型结合,推广了带有N-策略的M/G/1排队系统的研究,使用全概率分解技术,导出了在任意时刻t瞬态队长分布的拉普拉斯变换的递推表达式及平稳队长的随机分解.而后随着排队系统应用的广泛化,N-策略休假的应用有了进一步拓展:文4中以系统启动的临界队长为决策变量,结合客户的策略行为讨论最佳运营策略,讨论了可见与不可见两种不同信息水平下顾客的纳什均衡策略,分析了带有N-策略和假期的排队收稿日期：2023-03-02基金项目：国家自然科学基金项目(61773014)作者简介：张恒,女,汉族,江苏人,研究方向：排队论.290应用数学2024系统.在此基础之上,文5讨论了不同信息水平下的最优控制策略.近期,王勋等人6将N-策略应用于排队系统流体模型的性能分析,N-策略应用的广泛性和有效性进一步体现.以上研究均为经典的连续时间排队模型,文7首次采用矩阵几何解方法讨论了更适用于计算机系统的Geo/Geo/1工作休假排队模型,休假排队模型的研究方法进一步扩充.文8研究了多重工作休假变体模型下不耐烦顾客的均衡策略,拓展了休假排队模型的研究视角.负顾客的定义由Gelenbe(1989)在神经网络建模中引入,Gelenbe等人9后将其扩展到排队系统.作为一类对服务台起制约作用、带走系统中的正顾客但自身并不接受服务的顾客,负顾客一直受到学者的关注,大量的研究丰富和发展了负顾客排队系统的理论体系.负顾客通常被认为是一种病毒、错误操作或系统的灾难等,其主要影响是在正常忙期下对正顾客产生不同抵消作用的同时也可能使服务台发生故障,进入维修期.例如:在计算机系统中,病毒的存在可能会影响系统的工作效率而不是导致系统完全崩溃,如黑客的入侵会引发计算机正在处理的信息的丢失但不会影响计算机性能Panda等10研究了带有工作假期和负顾客模型下正顾客的均衡行为.WANG等11分析了M/M/1可修排队模型中顾客在四种信息水平下的均衡策略以及N-策略对易受攻击系统的保护作用.文10-11基于成本-收益结构讨论了不同休假变体下顾客的均衡行为,与性能分析不同的是,求解目标是标记顾客的预期逗留时间,而非稳态下顾客的平均等待时间.文12研究了带有负顾客和多服务器的易腐库存系统,其中负顾客可看作是竞争对手的吹捧者,进一步突出了负顾客的实际应用意义.文13首次以博弈论视角出发研究Geo/Geo/1可修排队模型中顾客在可见和不可见情形下顾客的均衡策略.MA等人14分析了带有备用服务台和两种负顾客破坏方式(RCH和RCE:清除队列头部顾客和清除队列末尾顾客)的离散排队模型,刘再明等15还研究了顾客到达率不同且带有工作休假的离散时间排队系统.从应用上看,离散时间排队模型给实际工程操作提供了重要理论支撑,例如数字信号处理中的离散时间信号处理等.在文15的基础上,文16将N-策略引入,以数值计算为例确定了系统费用最小的最优控制策略N*,以稳态队长的求解结果作为系统容量设计的参考,体现了N-策略应用于服务系统的优越性.2021年,文17创新性地考虑了具有Bernoulli休假和负顾客到达的Geo/G/1早到达重试排队系统,利用马尔可夫链和补充变量法推导平衡方程组,得到了嵌入马尔可夫链的平稳分布和一系列指标.至此,带有负顾客、待机时间和N-策略的离散时间排队模型的稳态条件及此模型下顾客的均衡策略分析还未被研究过,本文在文11的基础上考虑了系统稳态条件,简化模型的同时丰富了离散时间排队模型下顾客的均衡策略研究,给系统信息展示程度的设置提供了参考.本文主要研究带有负顾客、待机时间和N-策略休假的Geo/Geo/1离散时间排队模型的稳态条件、顾客在不同信息水平下的均衡策略行为及N-策略对系统的控制优化作用.模型贴近实际生活,例如:计算机工作会遭遇木马、病毒入侵而导致信息丢失,且计算机通常均有待机设置,关机时信息均已备份储存.因此本文在模型创新的同时也兼具实际意义.2.模型描述考虑一个带有负顾客、N-策略休假和待机时间的Geo/Geo/1迟到达排队系统,正、负顾客的到达发生在时隙末端,且时间间隔分别服从参数为p和的几何分布(0 p 1,0 1).假期下到达的正顾客不会立即被服务,当系统顾客数目累积至N时,系统转为在线状态,服务台根据FCFS规则向正顾客提供服务,服务时间服从参数为的几何分布(0 1).负顾客只会在系统在线时到达.服务过程中若负顾客到达,他会抵消一个正在被服务的正顾客(RCH)但不会破坏服务台.当系统变空时,服务台不会立刻关闭,而是待机一段时间,待机时间服从参数为的几何分布(0 1),在待机时间内到达的正顾客会立即被服务,若没有正顾客到达,则待机结束后系统自动进入休假.我们假设模型中的正负顾客到达时间间隔、服务第 2 期张恒等：带有负顾客和N-策略的Geo/Geo/1排队模型均衡策略分析291时间、待机时间均相互独立,每位正顾客都是风险中立且希望自身利益最大化的.记每位正顾客离开系统时收益为R,正顾客成功被服务的概率为ps,获益为Rs:正顾客被负顾客抵消的概率为ps=1 ps,获得的补偿为Rc,E(W)为顾客的预期逗留时间,C为顾客单位时间的逗留成本,则顾客的预期净收益为U=R CE(W),其中R=psRs+psRc.本文考虑以下两种信息水平:1)完全可见情形:顾客到达系统时,已知队长和系统状态;2)几乎不可见情形:顾客到达系统时,已知系统状态,但队长未知.3.稳稳稳态态态条条条件件件基于以上假设,可构造离散时间Markov链(Ln,In),n N动态刻画系统在时刻t=n+下的状态.其中In表示系统状态,Ln表示系统的正顾客数(时隙(n,n+)内离开或被移除的顾客不计入),且Ln=0,服务台休假,1,服务台在线(待机或忙).此Markov链的状态空间为=(k,i)|i=0时,k=0,1,N 1;i=1时,k N.系统的转移概率矩阵为P=A00A0A10A1A0A2A1A0.A2A1A0A2A1C0A2BCA2BC.,其中A00=p0p1 p p ,A0=p00p ,A10=A2=000p(+),A1=p001 p(+)p ,B=0001 p(+)p ,C0=0p0p ,C=000p .引理3.1若r11 1,则矩阵方程R=R2A2+RB+C存在最小非负解:R=r11000,其中r11=p p(+),此时Markov链(Ln,In),n N正常返.证由A2、B、C的矩阵形式,设R=r11r120r22,292应用数学2024代入矩阵方程得:p(+)r2p(+)+p r+p =0,求解后有r11=pp(+),r12=r22=0(舍去平凡根r11=1),故R=r11000为方程R=R2A2+RB+C的最小非负解.另一方面,根据文18,拟生灭过程正常返的充要条件是率矩阵谱半径小于1,且矩阵方程(x0,x1,xN)B(R)=(x0,x1,xN)有正解,这里B(R)=A00A0A10A1A0A2A1A0.A2A1A0A2A1C0A2RA2+B.B(R)是一个正随机矩阵19,故可取B(R)的一个不变概率向量(x0,x1,xN)作为以B(R)为系数矩阵的方程组的一个正解.因此Markov链正常返当且仅当SP(R)1,即p p(+)1.此条件等价于p(1 )+.符合拟生灭过程正常返条件:生率灭率,基于此,可求解两种信息水平下的系统稳态.4.模模模型型型求求求解解解完全可见情形为便于表示,将此情形下的稳态概率记作pfo(k,i),基于模型描述,系统在完全可见情形的状态转移率如图4.1所示:图4.1完全可见情形状态转移图到达系统的正顾客基于队长(不含自身)和系统状态这两个信息,通过“成本-收益”函数计算预期净收益后决定加入或是止步.这里需保证系统可被激活,即假期到达的顾客均乐意加入,然后研究顾客在服务台在线时的止步阈值ne.当顾客在(n,n)内到达系统时,若Ln 0时,顾客乐意加入:当Ufo(k,i)=0时,顾客无所谓加入或放弃:当Ufo(k,i)0 时,顾客会放弃加入.即只要预期净收益非负,假期到达的顾客第 2 期张恒等：带有负顾客和N-策略的Geo/Geo/1排队模型均衡策略分析293都会选择加入,服务台能够被激活.假期加入的顾客需要遵循N策略休假的排队机制,因此相对于服务台在线状态下进入的标记顾客,还需要等待N k 1个新顾客到达.自然地有T(k,1)0,k=0,1,N 1.即队长不超过N 1时到达的正顾客预期净收益均为正,且系统可容纳至少N个顾客.因此止步阈值必然要满足ne N.下面给出止步阈值的计算过程,求解均在稳态条件=p p(+)1之下进行.定理4.1服务台休假、在线期间到达的正顾客的平均逗留时间分别为:T(k,0)=N k 1p+k+1 ,k=0,1,N 1,(4.1)T(k,1)=k+1 ,k=0,1,2,.(4.2)证服务台在线时,若标记顾客在(k,i)状态下到达并选择进入,则顾客队列位置改变前需等待一段时间,这段时间服从参数为1 的几何分布,这是因为单位时间内标记顾客前移一位的概率为1 .因此标记顾客的队列位置前移一位需要的等待时间为11 ,此后顾客的逗留时间为T(k 1,1).从而有T(k,1)=11 +T(k 1,1),k=1,2,(4.3)特别地,如果正顾客在系统处于(0,1)状态(待机)时到达并加入系统,那么他只可能以两种形式离开系统:成功获得完整服务或被负顾客抵消,因此他的平均逗留时间为T(0,1)=+1=+.事实上+=1 ,结合(4.3)式进行递推可得T(k,1)=k+1 ,k=1,2,类似地,对于休假状态下到达并加入系统的正顾客,他将会比相同队长情况下服务台在线期间到达的顾客多一部分等待时间,即等待队长达到N的时间,由Little公式可知,多余的平均等待时长为N k 1p.因此有T(k,0)=N k 1p+T(k,1),k=0,1,N 1,即有T(k,0)=N k 1p+k+1 ,k=0,1,N 1,得证.注4.1令上式中 0,T(k,0),T(k,1)的形式与带有N-策略休假的经典M/M/1排队系统中4假期和忙期到达的顾客的平均逗留时间一致.定理4.2在信息完全可见情形下,正顾客存在一个止步阈值:ne=Rs+RcC+,其中x 表示不超过x的最大整数.证由定理4.1知,标记顾客的预期逗留时间关于k严格递增.因此存在唯一阈值ne N满足不等式组:Ufo(ne(1)1,1)=R CT(ne 1,1)0,Ufo(ne(1),1)=R CT(ne(1),1)0.294应用数学2024通过求解方程Ufo(k,1)=0 可得零点k0=Rs+RcC.结合上述不等式组自然有ne=k0+1,证毕.为保证服务器能够被激活,则要考虑在休假时进入的正顾客在最长预期逗留时间下净收益非负,这样才能保证顾客数累计至N个,因此下述引理考虑了假期下到达顾客的预期逗留时间最大值将在何处取得.引理4.2 若系统处于休假,则系统为空时到达顾客的预期逗留时间最长,也即maxkT(k,0)=T(0,0).证根据定理4.1,有T(k,0)=N k 1p+k+1 ,k=0,1,N 1,上式关于k求导可得T(k,0)=11 1p.令T(k,0)=0,可得零点p0=1 (0,1).由稳态条件p1 ,可知T(k,0)0,T(k,0)关于k单调递减,因此maxkT(k,0)=T(0,0).定理4.3在完全可见情形下,定理4.2中得到的均衡止步阈值ne在0 C(N 1p+1 ),整理后得Rs+RcC (N 1)(1 )p.即k0 N 1,故ne=k0+1 N.引理4.3在完全可见情形下,当正顾客全部遵循定理4.2中的止步阈值策略时,系统的稳态概率如下:pfo(0,1)=Npp+1 ne(1)+11 +(N+ne(1)+1 ne(1)N+11 )L1 1,(4.4)pfo(k,0)=pppfo(0,1),k=0,1,2,N 1,(4.5)pfo(k,1)=(k+1 k1 L)pfo(0,1),k=0,1,N,(4.6)pfo(k,1)=(1 1 N1 L)kpfo(0,1),k=N+1,N+2,ne(1),(4.7)其中=p p(+),L=+.证根据状态转移图(图4.1),可列出平衡方程如下:ppfo(0,0)=ppfo(0,1),(4.8)第 2 期张恒等：带有负顾客和N-策略的Geo/Geo/1排队模型均衡策略分析295ppfo(k,0)=ppfo(k 1,0),k=0,1,2,N 1,(4.9)(p +p)pfo(0,1)=p(+)pfo(1,1),(4.10)p +p(+)pfo(k,1)=p(+)pfo(k+1,1)+p pfo(k 1,1),(4.11)k=1,N 1,N+1,ne(1)1,(4.12)p +p(+)pfo(N,1)=ppfo(N 1,0)+p pfo(N 1,1)+p(+)pfo(N+1,1),(4.13)p(+)pfo(ne(1),1)=p pfo(ne(1)1,1),(4.14)由(4.8)可得pfo(0,0)=pppfo(0,1).(4.15)由(4.9)和(4.14)及顾客到达率非负性,可推得pfo(k,0)=pfo(0,0)=pppfo(0,1),k=0,1,N 1,(4.16)记L=+,由(4.10)可得pfo(1,1)=p +pp(+)pfo(0,1)=(+L)pfo(0,1),(4.17)令(4.11)中k=1可得pfo(2,1)=(2+L+L)pfo(0,1)=2+(+1)Lpfo(0,1),(4.18)令(4.11)中k=2,结合(4.14)和(4.15)可得pfo(3,1)=(2+L+L)pfo(0,1)=2+(+1)L,如此递推下去有pfo(k,1)=(k+k1i=0iL)pfo(0,1),k=1,2,N 1,(4.19)令(4.11)中k=N 1,有p +p(+)pfo(N 1,1)=p(+)pfo(N,1)+pfo(N 2,1),结合(4.18)可推得pfo(N,1)=N+(N1i=0i)Lpfo(0,1),从而(4.18)可进一步扩充为pfo(k,1)=(k+k1i=0iL)pfo(0,1),k=1,2,N,(4.20)将已有结果代入(4.12)式可得pfo(N+1,1)=N+1+(Ni=1i)Lpfo(0,1),(4.21)因(4.11)式对应的差分方程为p(+)x2 p +p(+)x+p =0,(4.22)其特征根为x1=,x2=1.则根据文20中齐次线性差分方程解的理论有pfo(k,1)=c1k+c21k,k=N+1,ne(1)1,ne(1),296应用数学2024上式与(4.20)联立得c1=(1 1 N1 L)pfo(0,1),c2=0.故有pfo(k,1)=k(1 1 N1 L)pfo(0,1),k=N+1,ne(1)1,ne(1).(4.23)至此,通过观察(4.15)、(4.20)和(4.22)形式可知,可见情形下系统的所有稳态概率均可由pfo(0,1)表示,结合归一化条件:N1k=0pfo(k,0)+ne(1)k=0pfo(k,1)=1,有pfo(0,1)=Npp+1 ne(1)+11 +(N+ne(1)+1 ne(1)N+11 )L1 1,(4.24)其中=pp(+),L=+证毕.推论4.1针对完全可见情形下的稳态概率,可得出稳态条件下服务台正常工作时系统的均衡吞吐量:THfoe=ne(1)k=1pfo(k,1)=1 ne(1)+11 +L1 (N+ne(1)+1 ne(1)N+11 )1pfo(0,1).(4.25)几乎不可见情形为便于表示,将此情形下稳态概率记作pau(k,i).此情形下到达系统的顾客已知系统状态但不知道队长,因此需要根据系统状态采用混合策略,假期和在线期间的加入概率分别记为q0,q1,则实际到达率应为:p=p0=pq0,服务台休假,p1=pq1,服务台在线(待机或忙).此时,系统的稳态条件仍为生率灭率,并且转移概率矩阵与情形只存在到达率上的差别.故此时的稳态条件为p1 p1(+)1,并且系统状态转移图如下:图4.2几乎不可见情形状态转移图基于此,我们可以求解几乎不可见情形下的稳态概率.引理4.4几乎不可见情形下的稳态概率如下:pau(0,1)=(Np1p0+1+NL1 1)1,(4.26)pau(k,0)=p1p0pau(0,1),k=0,1,N 1,(4.27)第 2 期张恒等：带有负顾客和N-策略的Geo/Geo/1排队模型均衡策略分析297pau(k,1)=(k1+1 k11 L)pau(0,1),k=1,2,N,(4.28)pau(k,1)=(k11 N11 L)k1pau(0,1),k=N+1,N+2,(4.29)其中1=p1 p1(+),L=+.证根据图4.2,几乎不可见情形下的稳态概率可由以下平衡方程解出:p0pau(0,0)=p1pau(0,1),(4.30)p0pau(k,0)=p0pau(k 1,0),k=1,2,(4.31)(p1 +p1)pau(0,1)=p1(+)pau(1,1),(4.32)p1 +p1(+)pau(k,1)=p1(+)pau(k+1,1)+p1 pau(k 1,1),k=1,2,(4.33)p1 +p1(+)pau(N,1)=p1pau(N 1,0)+p1 pau(N 1,1)+p1(+)pau(N+1,1).(4.34)类似地用引理4.3的解法,由(4.29)和(4.30)式可得pau(k,0)=p1p0pau(0,1).(4.35)记1=p1 p1(+),由(4.31)和(4.32)式可得pau(1,1)=(1+L)pau(0,1),pau(2,1)=21+(1+1)Lpau(0,1),最终推得pau(k,1)=(k1+1 k11 L)pau(0,1),k=1,2,N,(4.36)pau(k,1)=k1(1 1 N11 1L)pfo(0,1),k=N+1,N+2,(4.37)由归一化条件N1k=0pau(k,0)+k=0pau(k,1)=1,结合(4.31)-(4.33)知pau(0,1)(Np1p0+1+NL1 1)=1.则pau(0,1)=(Np1p0+1+NL1 1)1.推论4.2针对几乎不可见情形下的稳态概率,可得出稳态条件下服务台正常工作时系统的均衡吞吐量:THaue=k=1pfo(k,1)=1 1(1+LN)pau(0,1).(4.38)定理4.4几乎不可见情形在系统稳定条件下,11时,假期到达系统的正顾客的均衡加入概率为:qe0=0,R CN 12+N 1+22(1 )0,0,1,R CN 12+N 1+22(1 )=0.298应用数学2024服务台在线期间到达系统的正顾客的均衡加入概率为:qe1=0,R C2NL+(N+1)L2(1 )0,q1,R C2NL+(N+1)L2(1 )0,(4.39)其中p1=pq1=1(+)1(+)+,1=1 CR(1+NL)(1 )C+NL(+N+12).证在几乎不可见情形下,顾客进入系统时仅被告知系统状态而不知道队列长度,因此需要通过计算条件概率来求解预期逗留时间.首先记顾客到达时系统处于状态i的概率为p(In=i),i=0,1.那么根据引理4.4结论可得:p(In=0)=N1k=0pau(k,0)=Np1p0(Np1p0+1+NL1 )1=Np1p0pau(0,1),p(In=1)=N1k=0pau(k,1)=1+NL1 1(Np1p0+1+NL1 )1=1+NL1 1pau(0,1).因此p(k|i=0)=pau(k,0)p(In=0)=pau(k,0)N1k=0pau(k,0)=1N,k=0,1,N 1,p(k|i=1)=pau(k,1)p(In=1)=pau(k,1)k=0pau(k,1)=1 11+NL,k=0,k1(1 1)+(1 k1)L1+NL,k=1,2,N,k1(1 1)+k1(N1 1)L1+NL,k=N+1,N+2,.将服务台休假和在线期间到达顾客的平均逗留时间分别记为E(W|In=0),E(W|In=1).结合(4.1)、(4.2)式有E(W|In=0)=N1k=0pau(k|i=0)T(k,0)=N 12p0+N 1+21 ,(4.40)E(W|In=1)=k=0pau(k|i=1)T(k,1)=1(1+NL)(1 )11 1+NL(+N+12).(4.41)根据成本收益结构公式来计算均衡加入概率,需要求解方程Uaui(qi)=R CE(W|In=i)=0,i=0,1.(4.42)记Uau0(q0)=R CE(W|In=0)=0,(4.43)Uau1(q1)=R CE(W|In=1)=0.(4.44)容易得到dE(W|In=0)dq0=N 12p200,故Uau0(q0)关于q0严格递增,为分析假期到达顾客的均衡加入策略,需要考虑净收益在p0 0和p0=1下的取值:又因p0 0+时,T(k,0)+,此时净收益必然为负,故Uau0(q0=0)0,说明当其他顾客选择放弃,标记顾客选择加入时收益为负,故此时qe0=1 不是均衡解.考虑以下情形:第 2 期张恒等：带有负顾客和N-策略的Geo/Geo/1排队模型均衡策略分析2991)Uau0(q0=1)0,即R CN 12+N 1+22(1 )0,即RCN 12+N 1+22(1 )0,又因p0 0+时收益为负,且Uau0(q0)关于q0严格递增,因此存在零点q0(0,1),使得Uau0(q0)=0,此时q0=qe0.综上有qe0=0,R CN 12+N 1+22(1 )0,0,1,R CN 12+N 1+22(1 )=0.类似地,求解服务台在线时顾客的均衡加入率需讨论Uau1的单调性,又因1关于p1单调递增,所以讨论Uau1(1)关于1的单调性即可.易知E(W|In=1)关于1严格递增,且1 1时,有E(W|In=1),收益为负,从而Uau1(1)关于1递减且方程(4.42)关于1有且仅有一个根1:故服务台在线期间到达的顾客会面临以下情形:1)Uau1(1=0)0,即R C1(1+NL)(1 )1+NL(+N+12)0,此时无论顾客以何种概率加入都无法获得正收益,因此顾客的最佳决策是放弃加入,其均衡策略为qe1=0.2)Uau1(1=0)0,即R C1(1+NL)(1 )1+NL(+N+12)0,由介值性定理可知1(0,1),s.t.Uau1(1(p1)=0,此时,当pe1=p1=1(+)1(+)+,其中1是方程R C1(1+NL)(1 )1+NL(+N+12)=0的根,对其求解可得1=1 CR(1+NL)(1 )C+NL(+N+12),综上有qe1=0,R C2NL+(N+1)L2(1 )0,q1,R C2NL+(N+1)L2(1 )0.(4.45)注4.2在带有N-策略休假的经典M/M/1排队模型中(见文3),假期加入系统的顾客平均逗留时间是T0=N 12+N+12,令(4.38)中 0,即系统不会被负顾客入侵时,类似地,有E(W|In=0)=N 12p0+N+12成立.注4.3因为Uau1(p1)关于p1递减.一方面,当顾客到达率为p1且p1pe1时,若标记顾客选择进入系统,那么他的预期净收益将为负值.故此时他的最优策略是止步(qe1=0);另一方面,当p1pe1时,若标记顾客选择进入系统,那么他的预期净收益将为正.故此时他的最优策略是加300应用数学2024入(qe1=1).以上分析说明标记顾客的加入概率是其他顾客加入率单调非增函数.即其他顾客加入概率越高,标记顾客的加入意愿越低,属于拥挤厌恶情形(ATC).5.数数数值值值模模模拟拟拟根据推论4.1及推论4.2得到针对两种信息水平的系统均衡吞吐量表达式,分析其对系统主要参数的敏感性,并从中寻找最优的N-策略.取Rs=15,Rc=5,C=1,p0=0.6,p1=0.6,=0.8,=0.6.可以通过限制取值来满足稳态数值条件.首先,比较在不同负顾客到达率下,N-策略对吞吐量的影响:图5.1 不同情形下N-策略对系统吞吐量的影响(Rs=15,Rc=5,C=1,p0=0.6,p1=0.6,=0.8,=0.6)图5.2不同情形下的系统吞吐量增量(Rs=15,Rc=5,C=1,p0=0.6,p1=0.6,=0.8,=0.6)容易发现,在相同的N-策略设置下,随着负顾客到达率增大,吞吐量会逐渐减少,这是由于服务台在线期间负顾客的到达会造成正顾客的流失,这一趋势符合客观认知.并且,若系统设置为“付费可见”,即仅向缴纳信息费的顾客展示队长和系统状态信息时,相当于降低顾客预期收益R,此时吞吐量也会下降.因此,通过图5.1对比,向顾客隐藏队长更有利于优化吞吐量.此外,在负顾客入侵率一定时,一方面,观察N=1,2时的图像递增趋势,不难发现,设置N-策略休假可以显著提升单位时间内的系统吞吐量;另一方面当N超过一定数值时,吞吐量的递增趋势越发平缓,这是因为,阈值N的提高在抵御负顾客的入侵、减少正顾客流失的同时,也持续延长了假期到达系统的正顾客的平均逗留时间,造成了部分正顾客的流失;此外,第 2 期张恒等：带有负顾客和N-策略的Geo/Geo/1排队模型均衡策略分析301当N逼近止步阈值时,吞吐量会降低.完全可见情形因止步阈值的限制,并非N值越高,吞吐量越大,而是存在一个最佳阈值N*,使得吞吐量达到最大值;而在几乎可见情形下,均衡吞吐量则一直随着N的提升而递增,只是递增速度越来越慢.这一点符合直观事实,N的增加会使顾客不断增加等待时间,系统拥堵,吞吐量增速慢.因此N设置过高时对系统优化也是不利的.在相同数值条件假设下,比较可知,几乎不可见情形下系统吞吐量明显高于完全可见情形下的吞吐量;这给服务商提供了经营策略的参考,即此模型假设下向顾客隐藏队长信息会更有利于优化系统吞吐量.进一步,比较不同情形下的系统吞吐量增量,图5.2刻画了系统在不同信息水平和N-策略设置下,单位时间内系统吞吐量增量关于负顾客到达率的变化趋势.这里的吞吐增量指的是带有N-策略设置和无N-策略设置(N=1)下系统吞吐量的差值.一方面,在相同的负顾客到达率下,当N较小时,门限N的提升对系统的优化效果十分明显,固定负顾客到达率下,N越高,单位时间内系统吞吐量增量越大,但提升速度趋于缓慢,说明吞吐量在N数值较小时的敏感度更强.另一方面,固定N的取值,随着负顾客到达率的提升,单位时间内系统吞吐增量也随之提升,进一步说明负顾入侵越频繁时,N-策略的保护作用越明显.比较可知,在完全可见情形下N-策略的保护效果优于几乎不可见情形.因此若系统信息设置为完全可见,则设置N-策略休假来保护系统是必要的.6.结结结论论论本文考虑了带有负顾客和N-策略的Geo/Geo/1迟到达排队系统,研究了不同信息水平下顾客均衡策略和优化问题,论文针对完全可见情形和几乎不可见情形分别获得了顾客的均衡止步策略和均衡进入策略,并进一步求出了系统的稳态概率分布,通过数值算例考察了系统参数对系统单位时间吞吐量的影响,给顾客决策和系统方案设计提供了参考数据.参参参考考考文文文献献献：1 YADIN M,NAOR P.Queueing systems with a removable service stationJ.Journal of the OperationalResearch Society,1963,14(4):393-405.2 PANTA A P,GHIMIRE R P,PANTHI D,et al.A review of vacation queueing models in differentframeworkJ.Ann.Pure Appl.Math,2021,24:99-121.3 刘晓燕.N-策略M/G/1排队系统的推广研究D.成都:电子科技大学,2009.4 GUO P,HASSIN R.Strategic behavior and social optimization in Markovian vacation queuesJ.Operations Research,2011,59(4):986-997.5 GUO P,LI Q.Strategic behavior and social optimization in partially-observable Markovian vacationqueuesJ.Operations Research Letters,2013,41(3):277-284.6 王勋,徐秀丽.带N-策略的双阶段休假M/M/1排队系统驱动的流体模型性能分析J/OL.运筹学学报,20222023-03-02.http:/ TIAN N,MA Z,LIU M.The discrete time Geom/Geom/1 queue with multiple working vacationsJ.Applied Mathematical Modelling,2008,32(12):2941-2953.8 PANDA G,GOSWAMI V,BANIK A D.Equilibrium behaviour and social optimization in Markovianqueues with impatient customers and variant of working vacationsJ.RAIRO-Operations Research,2017,51(3):685-707.9 GELENBE E,GLYNN P,SIGMAN K.Queues with negative arrivalsJ.Journal of Applied Proba-bility,1991,28(1):245-250.10 PANDA G,GOSWAMI V.Equilibrium joining strategies of positive customers in a Markovian queuewith negative arrivals and working vacationsJ.Methodology and Computing in Applied Probability,2022,24(3):1439-1466.302应用数学202411 ZHANG L,WANG J.Strategic shield against external shocks in a Markovian queue with vulnerableserverJ.Journal of Industrial and Management Optimization,2023,19(5):483-3508.12 YANG T,WANG J,ZHANG F.Equilibrium balking strategies in the Geo/Geo/1 queues with serverbreakdowns and repairsJ.Quality Technology and Quantitative Management,2014,11(3):231-243.13 YADAVALLI V S S,SIVAKUMAR B,ARIVARIGNAN G,et al.A multi-server perishable inventorysystem with negative customerJ.Computers&Industrial Engineering,2011,61(2):254-273.14 MA Z,GUO Y,WANG P,et al.The Geo/Geo/1+1 queueing system with negative customersJ.Mathematical Problems in Engineering,2013:1-8.15 刘再明,于森林.一个不同到达率及负顾客的离散工作休假排队J.山东大学学报(理学版),2015,50(6):1-6.16 潘取玉,唐应辉,兰绍军.带负顾客和N-策略的Geo1,2/Geo/1(MWV)排队系统分析及最优控制策略NJ.运筹学学报,2017,21(3):65-76.17 薛红,唐应辉.具有Bernoulli休假和负顾客到达的Geo/G/1早到达重试排队系统J.数学的实践与认识,2021,51(12):111-119.18 田乃硕,岳德权.拟生灭过程与矩阵几何解M.北京:科学出版社,2002.19 NETUS M.Matrix-geometric Solutions in Stochastic ModelsM.Baltimore:Johns Hopkins Univer-sity Press,1981:80-120.20 ELAYDI S.An Introduction to Difference EquationsM.New York:Springer,2005.Analysis of Geo/Geo/1 Queueing Model EquilibriumStrategy with Negative Customer and N-PolicyZHANG Heng,LIU Liwei(College of Mathematics and Statistics,Nanjing University of Science and Technology,Nanjing 210094,China)Abstract:In this paper,Geo/Geo/1 late arrival queuing model with negative customer,N-policyvacation and standby time is proposed,and the steady-state condition,customer policy and throughputoptimization problem under this model are studied.The arrival of a negative customer occurs du