论文研究--策略工作休假.pdf,  考虑N-策略M/M/1排队，休假期间服务员并未停止工作而是以较低的速率为顾客服务.系统的决策主体是顾客，基于“收益-成本”结构，利用马尔可夫过程理论，采取均值分析的方法，以顾客追求利益最大化为出发点，分析了全可见和几乎可见两种情况下的顾客行为.通过求解平衡方程，得到几乎可见情况下系统的稳态概率，进而求得几乎可见状态下顾客的期望逗留时间.构建均衡社会收益函
1850 系统工程理论与实践 第36卷 这一祭件保证了在休假期顾客加入系统收益非负.顾客会在休假期加入系统,系统可以转化到正常服务状态 否则,系统一旦开始休假,将永远留在休假期. 基于上述假设,分别记策略集为S,效用函数为F.令F(a;b)为标定顾客采取策略a,而其他顾客选择 策略b时,顾客的收益或所得.若对νs∈S,均有F(sε,S)≥F(s,S),则称sε为一个(对称纳什)均衡策略. 事实上,每位顾客的策略都是对其他人策略的最优反应(纳什均衡).当所有顾客选择均衡策略时,没有任何 单个顾客有积极性去改变这种均衡,因为无论做出任何改变,都不会使自己的收益变大 系统运作的状态转移图如下所示 (0,0)←(1,1)(2,1) (N-1.1) (M,1(N+1,1)-→ 1 (1,0)2(2,0) 图1系统运作状态转移图 3全可见状态下顾客行为分析 本部分研究全可见排队模型中的相关顾客行为.假设顾客在t时刻米到系统后,不仅知道系统中的顾客 数N(t),还知道系统当前所处的状态r(t) 系统的状态转移图如下图所示 (0 1 图2全可见情况下的状态转移图 令ne表示顾客止步门限,即顾客在t时刻来到系统,者系统中的顾客数N(t)大于等于me时,顾客接受 服务后净收益为负,顾客选择离开.ne满足 >0.R 故 Rul 下面分情况分析顾客的期望逗留时间: 1)若顾客米到系统时:系统状态为(m1,1),顾客的期望逗留时间为 +1 EWi(uu)I 2)若顾客来到系统时,系统状态为(mo,0), i)若m0≥N-1.此顾客必然以正常服务率接受服务,其在系统中的期望逗留时间为: EWo(no) 十— i)若m0<N-1,若此顾客在接受服务前,系统中的顾客数到达N,服务员就会转换到正常工作状态 因此,此顾客有可能以休假服务率p接受服务,也有可能以正常服务率1接受服务.顾客在系统中最长的 逗留时间为+,即顾客以休假服务率p0接受服务的等待时间;最短的逗留时间为+m,即只有顾客来 到时系统中的第一个顾客以休假服务率p接受服务,而在其之后的所有顾客都以正常服务率p1接受服务. 下面定理给出顾客在(70,0)(m0<N-1)时来到并加入系统后,以正常服务率1接受服务的概凇P0,01, 顾客以休假服务率10接受服务的概率为1-Pno,01 定理1若顾客在(m0,0)来到并加入系统,其以正常服务率接受服务的概率为 no Pn,01=)P,o1, 第7期 刘维奇,等:N-策略工作休假M/M/1排队系统中的顾客行为研究 1851 其中,B,01表示机构服务完k(0<k≤m)个顾客后转换到正常服务状态的概率.且 e-(7o+1-k) ∑Pm〈S0(k) T=N-(70+1-k) Pm(S0(k)表示在时间S(k)内来到顾客数为m的概率,S0(k)表示机构以休假服务率服务k个顾客所需 的时间.且 Pm(So(k))=C An+ 证明先来求S0(k)的分布.S0(k)表示机构以休假服务率10服务k个顾客的时间,故S0(k)是k个参 数为10且独立的指数分布的和.用矩母函数容易证得S0(k)服从参数为(k,10)的 Gamma分布,其概率密 度为 oe02(/( h-1 (k t>0. 个标定顾客在系统中有70个顾客时加入,若服务员服务完k(<k≤m0)个顾客后,系统中的顾客数 至少为N-(0+1-k),服务员转换到正常服务状态下面来求在S0(k)内来到m个顾客的概率Pn(S0(k) Pm(So(k)= PIN(So(k))=ml PN(S(k)=m15(k)=t均0°(n-d PIN(t=m) e -1 dt k-1)! 入ot k-1 m!(k-1 Cl /0 +k Ao 0+10 图3是Pm(S0(k)的图像 0.35 0.15 k 0.05 图3Pm(S0(k)图线 图3描述了Pm(S0(k)的概率走势,取xA-0.7.从图中可以看出随着k值的增大,也就是服务顾 客数增多.在服务期内没有顾客来到的概率越来越小.当k=1时,即服务员服务一个顾客期问系统中来到 的m个顾客的概率随m的增大而减小.而当k>1时,系统中来到m个顾客的概率先增后减,即达到峰值 后下降.当k=1时,系统中没有顾客来到的桃率最大,故不存在其他图线中先增长的一段 若S(k)内米到并加入系统的顾客数大于等于N-(0+1-k),服务员转换到正常服务状态故服务 员服务完k个顾客后转换到正常状态的概率Pk.01为 Pk.01=PIN(So(k))2N-(n+1-k))=2 PIN(So(k)=m)=2 Pn(So(k), N-(no+1-b m=N-(70+1-k) 1852 系统工程理论与实践 第36卷 因此.当顾客在状态(no,0)来到并加入系统,其以正常服务率接受服务的概率P0,01为 证毕 定理2顾客在状态(m0,0)(o<N-1)时来到其期望逗留时间E[W0(mo)为: k 710+1-k P1,以概率Po ET0(7o)={a=1、:0 70+ 以概率1-Po,o1 在N较小的时候,不考虑休假期间的均衡队长,而在N较大的时候,就应该考虑到均衡队长对系统的 影响.令L为休假时的均衡队长,若N>L成立时,从长期米看,系统一旦开始休假服务,就不能转化到正 常服务状态.因此,为了使系统正常运作,服务系统必须满足休假状态的均衡队长大于等于转换门限N 引理1系统以休假服务率o服务k个顾客的时间S(k)内来到顾客数的期望为: E[N(S0(k)]==k. 证明令T=S;-S-1为服务员服务第讠个顾客的时间,T服从参数为10的指数分布,则在服务k个 顾客的时间内,来到系统的顾客数的期望为 +∞ EN(S)-∑AN以)->/EN()2=1-d ∑ Aoti uoe kodi 证毕 在普通的排队系统中,顾客为了避免等待时间过长净收益为负,一般采取避免拥挤策略.而在N-策略工 作休假排队系统中,在休假期来到系统的顾客会采取跟随拥挤策略,因为休假期间所有顾客的加λ,会使系 统更快地转换为正常工作状态,从而缩短系统中所有顾客的等待时间,增加顾客净收益. 4几乎可见排队中顾客行为分析 本韶分讨论几乎可见排队模型中相关的顾客行为.顾客来到系统时,只知道系统中的顾客数N(),不知 道服务员的状态I(t) 令me表示顾客止步门限,由上部分的分析可知,me=1」.系统的状态转移图如下所示 人 (0,0)←(1 (2,1) (1,0)←(2,0 图4几乎可见模型中的状态转移图 定理3在服务规则为FCFS的几乎可见N-策略M/M/1工作休假排队系统中,顾客来到系统时只知 道系统中的顾客数N(t),系统的稳态概率为 Pao(k, 0 Pa(1,1),k=1,2 (1 5) Pa(k,11- Pao(1,1),k=1,2, p1 Pa(N+k,1)=21(1-mN Pao(1,1),k=0,1,2 e 其中, (N+1) N+1 Pao(1,1) (8) 0 10 第7期 刘维奇,等:N-策略工作休假M/M/1排队系统中的顾客行为研究 1853 证明根据状态转移图可以写出以下平衡方程: p1P(1,1)+p0P(1,0)=AP (9) (A+p41)P(1,1)=11P(2,1) (0+入P(k,0)=AP(k-1,0)+10P(k+1,0),k=1,2,…,N-2 (11) 入P(N-2,0)=(40+入P(N-1,0 AP(N-1,0)+AP(N-1,1)+1P(N+1,1)=(入+1)P(N.1) (13) AP(k-1.1)+1P(k+1,1)=(X+1)P(k,1),k=2,3,…,N-1 入+p1)P(N+k.1)=入P(N+k-1,1)+11P(N+k+1,1),k=1,2,……,me-N (15) 令p1=A,p=.下面用差分方程求解平衡方程 式(11)对应的差分方程为 (10+入0)xn+Ao= (16) 此特征方程的特解为:rk=C1p8+C2,即 k,0)=C1p6+C2,k=1,2,…,N (17)与(12)联立,解得: 18 将式(9),(17),(18)联立,解得 P(1,1) (19) 故有 P(k,0 p(1-p0)0 P(1,1),k=0,1 (20) 用同样的方法解得 P(k P(1,1),k=1,2,…,N-1 (21) n(1 P(N+k,1) P(1,1),k=1,2, 根据标准概率归一化条件,有: 1=∑P(k.0)+∑P(k,1)+∑P(N+k,1 =0 k=1 P(1,1)+∑nP(1,1)+∑ P k=0 (1-p0) 11-(N+1)o+N N+1 N+1 (N+100+NoN+ po p(1-p0)o P(1,1)+ P⊥PO 1 P(1,1) 故 P(1,1 +1)+Np0+1p1,N-N ne-N+1 24) 证毕 下面分情况讨论顾客的期望逗留时间. 1854 系统工程理论与实践 第36卷 1)若顾客来到系统时,看到系统中的顾客数n≥N-1,此顾客必然以正常服务率p1接受服务,其期望 逗留时间EW1(m)为 m+1 顾客来到时,系统已经转换到正常服务状态 EWi(n) (25) +一,顾客来到时,系统将要转换到正常工作状态 当系统中的顾客总数为N时,系统状态是一种“混合”状态:可以处于正常工作状态,也可以处于休假 状态,此时的休假状态在服务员服务完当前接受服务的顾客后马上结束 2)若顾客来到系统时,系统中的顺客数m<N-1,此时系统有可能处于休假状态,也有可能处于正常 工作状态.由前面的结论可知 P(0n) Pao(n, 0) Pao(n, O) Pao(, 1) (72 Pao(n, 0)+ Pao(n, 1) Pao(n, 0)+Pao(n 1) 此情况下顾客的期望等待时间为: EW-(n)= EWo(n)lp(on)+ eWi(n)P(ln) k n+1-k n+1 +1 (,01)+—(1-P(n,01)P(0m)+ 10 系统中顾客的平均队长L为 N-1 ∑A(P(k.0)+P(k,1)+∑(N+P(N+,1) Pn,)+∑(N+) 1 Pao(1,1) 1-p1 p0)+ po P0)0 1+(N-1 (27) Pa(1,1) (1-p1) N+1 ne -N+1 N Pan(1,1)(N + p1 2 1+(N-1 Po Po P0)0 +1 Pao(1,1) e 1-P 系统中顾客数达到最大时的稳态的概率P。为 e Pa(1,1) P 根据 Little公式,有L=X(1-Pn。)EW(mn),EW(m)表示顾客来到系统后的期望逗留时间,其表达式 为 EWn)- Pin2N-1EWi(n+ Pin<N-1elW-(n] 210人(P(N-1,0)+ ∑P(N+k,1)+-∑ P(k,1)+ 1 上=N-1 (28) ∑(P(k,0)+P(k,1)EW(l) 由 PASTA性质,单位时间的均衡社会收益为:SW=(R-CEW(m))(1-Pn)=F(1-P。)一CL 5数值模拟 上韶分研究了几乎可见排队模型的均衡状态以及顾客来到系统后的期望逗留时间,得到了系统稳态概率 以及单位时间的均衡社会收益.本部分将通过一系列数值模拟,分析N,R以及入对单位时间均衡社会收益 的影响 第7期 刘维奇,等:N-策略工作休假M/M/1排队系统中的顾客行为研究 1855 图5中,在N相同时,平均队长L随着来到率λ的增大而增大,均衡社会收益SW随着来到率入先增 大后减小:在λ相同时,平均队长L随着系统启动门限N的增大而增大,均衡社会收益SW随着N的增大 而减小.这与实际情况是相符的,在N-策略工作休假排队模型中,若系统由休假状态转换到正常服务状态 的门限值N确定,顾客的到达率λ越大,单位时间内到达的顾客数就越多,在服务率给定时,平均队长就越 大,系统中的顾客总数越容易达到转换门限N,系统越容易转化到正常服务状态,顾客在系统中的期望逗留 时间就会越短,故而均衡社会收益就越大;当λ増加到一定值后,顾客的均衡收益达到最大,若入继续增大, 系统出现拥堵,顾客旳等待时问增加,收益降低,均衡社会收益下降.若顾客到达率λ确定,系统的转换门限 N越小,系统越容易转换到正常工作状态,系统中等待的顾客数越少,平均队长越小;顾客的期望逗留时间越 短,均衡社会收益越大 N=6 =5 图5参数入对L,SW的影响({40=1.5,41=2,C=1.5,R=20) 3.51 图6参数N对L,SW的影响(0=1.5,u41=2,入=1.2,C=1.5,R=20) 图6表明,平均队长L随N的增大而增大,SW随着N的增大而减小.囚为随着N的增大,系统由休 假状态转化到正常工作状态变得困难,系统中等待的顾客数增多,故平均队长会增大,顾客在系统中的期望 逗留时问增加,进而使均衡社会收益下降. 2.013 0125 2.0115 2.011 米米米米来米米米关米※米米米米 2095l 图7参数R对L,S的影响(p0=1.5,11=2,入=1.2,C=1.5,N=5) 1856 系统工程理论与实践 第36卷 图7表明.平均队长L随着R的增大而减小,均衡社会收益随R增大而增大.容易理解,当顾客接受服 务后的收益都增大后,在顾客来到率一定的前提下,每个顾客接受服务后的收益也会相应变大,均衡社会收 益作为单位时间内米到系统顾客的收益的和,必然是会增大的 6结论与展望 本文基于M/M/1排队系统中的N-策略工作休假模型,从顾客利益出发,研究了全可见和几乎可见两 种状态下的顾客行为.通过对全可见排队模型的分析,得到了顾客在各个状态来到并且加入系统的期望等待 时间通过求解平衡方程,得到几乎可见情况下的稳态概率,进而求出顾客在系统中的期望逗留时间,并给出 了单位时间的均衡社会收益.最后通过数值模拟,研究了各个参数对系统平均队长和均衡社会收益的影响 文章拓展∫排队理论的研究视角,对服务行业中顾客如何选择服务机构以达到效益最大化有指导作用.由于 篇幅的限制,本文只讨论了全叮见和几乎可见两种状态下的顾客行为,接下来的研究将继续讨论几乎不可见 和全不可见状态下顾客行为 参考文献 1 Naor P. The regulation of queue size by levying tolls[J. Econometrica, 1969, 37(1): 15-24 2 Edelson N M, Hilderbrand D K. Congestion tolls for poisson queuing processes[J]. Econometrica, 1975, 43(1) 8192 3 Hassin R, Haviv M. To queue or lot lo queue: Equilibriun behavior in queueing sysleInsM. BOSLOll, Kluwer Academic publishers 2003 1 Yadin M, Naor P. Queueing systems with a removable service stationJ]. Operation Research Quarterly, 1963 14(4):393-405 5 Kella O. The threshold policy in the M/G/1 queue with server vacations[J]. Naval Research Logistics, 1989 36(1):11123 6唐应辉延迟N-策略M/C/1排队系统队长约瞬态和稳态分布叮.系统工程理论与实践,2007,27(1):130134 Tang Y H. The transient and equilibrium distributions of the queue-length for M/ G/l queue with delayed N-policy[J]. Systems Engineering- Theory Practice, 2007, 27(11 ): 130-134 ∏7唐应辉,蒲会,余玅妙.带启动时间的N策略M/G/1排队系统的队长同.系统工程理论与实践,2011,31(1):131-137 Tang Y H, Pu H, Yu MM. Queue size of M/G/l queueing system with N-policy and set-up times J Systems Engineering- Theory Practice, 2011, 31(1): 131-137 岗8」魏瑛源,唐应辉,顾建雄.延迟N-策略σeσ/C/Ⅰ排队系统旳队长分布及数值运算刂J·系统工程理论与实践,2011 31(11):2151-2160 Wei YY, Tang Y H, GuJX. Queue length distribution and numerical calculation for Geo/G/1 queueing system with delayed N-policy[J]. Systems Engineering-Theory &e Practice, 2011, 31(11): 2151-2160 ⑨唐应辉朱亚丽吴文青.修理设备可更换的N-策略MG/1可修排队系统分析J·系统工程理论与实践,2014,34(3) 746-755 Tang Y H, Zhu Y L, Wu Q. Analysis of M/G/1 repairable queueing system with N-policy and a replaceable repair facilityJ. Systems Engineering- Theory Practice, 2011, 31(3):716-755 10唐应辉,吴文青,刘云颇,等基亍多重休假的min(N,V)策咯M/G/1排队系统的队长分布同.系统工程理论与实践, 2014,34(6):1533-1546 Tang YH, WuwQ, liu Y P, et al. Queue length distribution of M/G/1 queueing system with min(N, V)-policy based on multiple server vacations[J. Systems Engineering-Theory Practice, 2014, 34(6: 1533-1546 11 Guo P, Hassin R Strategic behavior and social optimization in Markovian vacation queues[J. Operations Re search,2Ol1.59:986997 12 Guo P, Hassin R. Strategic behavior and social optimization in Markovian vacation queues: The case of hetero- geneous customers[J. European Journal of Operational Reseach, 2012. 222: 278-286 [13 Guo P, Li Q. Strategic behavior and social optimization in partially-observable Markovian vacation queues Operations Research Letters, 2013, 41: 15-24 14杨顺利,囗乃硕.N-策略工作休假M/M/1排队.运筹与管理,2007,16(4):50-55 Yang S L, Tian N S. The M/M/1 queue with working vacation and N-policy[J. Operations Research and Management Science, 2007, 16(4 ) : 50-55 15]罗海军,朱翼隽.带冇负顾客的N-策略工作休假MM/Ⅰ排队J运筹与管理,2010,19(1):100105 Luo H J, Zhu Y J. The M/M/1 working vacation queue with negalive custOmers anld N-policyJ]. Operalions Research and Management Science, 2010, 19(1):100-105