APP下载

带休假延迟和启动时间的M/M/1多重休假排队系统分析

2015-07-01

关键词:服务台指数分布等待时间

张 杰

(阜阳师范学院 数学与统计学院,安徽 阜阳 236037)

带休假延迟和启动时间的M/M/1多重休假排队系统分析

张 杰

(阜阳师范学院 数学与统计学院,安徽 阜阳 236037)

考虑了带休假延迟和启动时间的M/M/1多重休假排队系统,运用QBD过程和矩阵几何解等工具,给出过程稳态队长的具体形式,在此基础上, 推导出稳态条件下队长和平稳等待时间的随机分解结构以及系统的附加队长分布和附加延迟LST的具体形式. 并进一步得到系统处在各种状态的概率和稳态指标的均值。

M/M/1休假排队;休假延迟;启动时间;QBD过程;矩阵几何解;随机分解

近年来,休假排队成为应用概率中的一个研究热点,取得了有价值的结果[1-3]。带启动时间的排队系统,在复杂通信网络、计算机系统等诸多领域有着广泛的应用,不同启动机制及休假策略的连续时间排队,得到了较为深入的研究[4-8]。休假延迟策略由Leung[9]提出并受到广泛关注[10,11]。随后,根据不同的应用背景,各种控制策略的M/M/1排队得到了研究[12-14]。颜娜等[15]考虑了更一般的情形,即GI/M/1排队模型。类似地,魏瑛源等[16]考虑了离散时间带启动和延迟排队系统的队长分布。特别的,[12-16]中模型均可看作抢占优先权排队[17]情形。王建军[18]和李沛等[19]分别使用M/G/1型排队系统结构矩阵解析法,讨论顾客服务完离去后系统的稳态指标。

本文主要考虑在一个M/M/1排队系统中,引入带有休假延迟和启动时间的多重休假策略,利用QBD过程和由Netus发展的矩阵几何解[20]方法,详细分析了系统在稳态条件下的队长分布及其处在各种状态的概率,推导出稳态指标的随机分解结果,并进一步得到附加队长分布与附加延迟LST的具体形式和均值。

1 模型描述

考虑经典M/M/1排队系统,即顾客到达时间间隔序列{τn,n≥1}独立同分布F(t)=1-e-λt,t≥0;每个顾客的服务时间分布独立,同参数为μ的负指数分布。系统一旦没有顾客,服务台首先开始1个随机长度为D的休假延迟期,延迟时间服从参数为β的指数分布;休假延迟期如果有新的顾客达到,则服务台立刻开始服务,直到系统又空出而再次进入休假延迟期;休假延迟期结束时若无顾客,服务台开始休假;当一个休假期结束时,如果系统中无顾客,则服务台开始另一次独立同分布的休假,否则需要经历一个启动过程,这一时间A服从参数为α的负指数分布,启动期结束后一个忙期正式开始;假定休假时间V服从参数为θ的指数分布。

假设到达间隔、休假延迟时间以及休假状态与启动时间之间均相互独立。

设Q(t)表示系统在时刻t时的顾客数,

由模型假设易知{Q(t),J(t)}是具有状态空间Ω={(0,0),(0,1)}∪{(k,j)|k≥1,j=0,1,2}的Markov过程,其中(0,1)表示处于服务台休假延迟期,(k,0)(k≥0)表示服务台在休假状态且有k个顾客,(k,1)(k≥1)表示处于服务台启动期且系统中有k个顾客,(k,2)(k≥1)表示系统处于忙期且有k个顾客。

其中

R2B+RA+C=0

(1)

的最小非负解R,其中R称为率阵。

引理2 QBD过程{Q(t),J(t)}是正常返的当且仅当ρ<1。

证明 由矩阵几何解[20]可知,QBD过程{Q(t),J(t)}是正常返的当且仅当R的谱半径SP(R)<1,并且线性方程组(x0,x1,x2,x3,x4)B[R]=0有正解。由于

2 稳态队长分布

当ρ<1时,设(Q,J)表示QBD过程{Q(t),J(t)}的稳态极限。令

定理1 若ρ<1,则(Q,J)的稳态概率分布由(2)式给出

证明 由矩阵几何解方法,有(πk0,πk1,πk2)=(π10,π11,π12)Rk-1,k≥1,且

(π00,π01,π10,π11,π12)满足(π00,π01,π10,π11,π12)B[R]=0。将B[R]代入,得到方程组

最后,使用正规化条件可以确定常数因子K。

由(2)式可知,系统稳态时服务台分别处于休假期、休假延迟期、启动期和忙期的概率分布为

定理2 记Q表示此系统的稳态队长,则当ρ<1 时,Q可被分解为2个独立的随机变量之和:Q=Q0+Qd,其中Q0为无休假M/M/1经典排队模型中相应的稳态队长,服从参数为1-ρ的几何分布;Qd是带休假延迟和启动时间的M/M/1排队系统的附加队长,服从修正的几何分布

P{Qd=k}=

可以证明δ1+δ2+rδ3+β′δ4=(K*)-1,因此,Qd(z)是一个PGF。把Qd(z)展成z的幂级数,得到附加顾客数Qd的分布。

3 平稳等待时间

记稳态时系统中顾客的等待时间为W,可以得到以下随机分解结果:

定理3 假设采用FCFS规则进行服务,在平稳状态下,当ρ<1 时,带有休假延迟和启动时间的M/M/1排队系统顾客的平稳等待时间W可分解成2个相互独立的随机变量之和:W=W0+Wd,其中W0是标准M/M/1系统中顾客的等待时间,服从参数为μ(1-ρ)的指数分布;附加延迟Wd与W0相互独立,其LST为

并服从修正的指数分布。其中

证明 由稳态时系统中顾客数Q的PGF与等待时间W的LST之间的经典关系[21],

由定理2,系统中顾客数Q的PGF为

推论2 平稳状态时平均附加延迟为

系统平稳状态时等待时间的均值为

4 小结

本文对带有延迟休假期和启动时间的多重休假M/M/1排队系统进行了分析,推导出稳态条件下的队长和等待时间分布的母函数及其随机分解结构,并给出附加队长和附加延迟分布等系统排队指标。这一模型为通信网络等系统的优化设计提供了理论基础,具有一定的应用价值。另外,如何对模型进行完善使研究更具实用性,这些结果是否可以推广到离散时间情形,是值得进一步研究的问题。

[1] Doshi B T. Queueing systems with vacations — A survey[J]. Queueing Systems, 1986, 1(1): 29-66.

[2] Takagi H. Vacation and priority systems[M]. 1st. Amsterdam: North-Holland, 1991: 107-119.

[3]Tian Naishuo, Zhang Gz. Vacation queueing models-theory and applications[M]. New York: Springer Verlag, 2006: 1-56.

[4] 田乃硕.PH-启动时间的 GI/M/1排队[J].数学的实践与认识,1993(4):1-7.

[5] 蒲 会,唐应辉.带启动-关闭期的多重休假M/G/1排队系统的队长分布[J].数学的实践与认识,2011,41(10):120-128.

[6] 刘名武,马永开.启动延迟N-策略批到达多重休假排队[J].数学的实践与认识,2011,41(13):137-143.

[7] 朱翼隽,刘海燕,王逢佳.带启动时间、N策略和负顾客的M/M/1工作休假排队[J].江苏大学学报 (自然科学版),2012,33(5):616-620.

[8] 唐应辉,李沁洪,余玅妙.休假结束立即启动的M/G/1单重休假排队系统分析[J].应用数学,2014,27(2):447-456.[9] Leung, Kin K. On the Additional Delay in an M/G/1 Queue with Generalzed Vacations and Exhaustive Service[J]. Operations.Research,1992,40: 5272-5283.

[10]岳德权,赵 玮.具有延误休假的GI/M/1排队系统[J].运筹学杂志,1994,13(1):33-38.

[11]Deng Y L, Braun W J, Zhao Y Q. M/M/1 queueing system with delayed controlled vacation[J]. 0R Transactions, 1999, 3(4): 17-30.

[12]徐秀丽,高 红,田乃硕.对带启动时间和可变服务率的M/M/1休假排队的分析[J].应用数学学报,2008,31(4):692-699.

[13]胡 彬,朱翼隽,周宗好.负顾客、带启动期和备用服务员的M/M/1休假排队系统[J].系统工程理论与实践,2012,32(2):349-354.

[14]徐祖润,朱翼隽,罗海军.带关闭期和启动期及负顾客的工作休假排队[J].江苏大学学报(自然科学版),2012,33(2):244-248.

[15]颜 娜,吴云江.带有启动时间和单重工作休假的GI/M/1排队系统分析[J].工程数学学报,2014,31(4):529-538.

[16]魏瑛源,唐应辉.带启动时间的延迟N-策略Geo/G/1排队系统的队长分布及容量的优化设计[J].高校应用数学学报A辑,2013,28(4):391-405.

[17]张宏波,史定华.M/M/1抢占优先权排队平稳指标的尾部分析[J].系统科学与数学,2014,34(1):1-9.

[18]王建军,杨德礼.带启动-关闭期的多重休假M/G/1排队[J].燕山大学学报,2005,29(1):8-12.

[19]李 沛,徐秀丽,曹学云,等.带启动一关闭期和N策略的多重休假M/G/1排队[J].数学的实践与认识,2011,41(13):145-149.

[20]Netus M. Matrix-Geometric solutions in stochastic models[M]. Baltimore: the johns hopkins university press, 1981: 80-120.

[21]Keilson J, Servi L D. A distributional form of Little's Law[J]. Operations Research Letters, 1988, 7(5): 223-227.

Analysis of multiple vacation M/M/1 queue with delayed vacation and setup time

ZHANG Jie

(SchoolofMathematicsandStatistics,FuyangNormalUniversity,FuyangAnhui236037,China)

This paper considers an M/M/1 queue system with multiple vacation,delayed vacation and setup time. By applying quasi-birth-death (QBD) process and matrix-geometric solution method, the analytic expression of the stationary queue length and stochastic decomposition structures of the stationary queue length and waiting time are given. Meanwhile, it is demonstrated that the additional queue length and the expression of the laplace-stieltjes transformation of additional delay. Moreover, expectation of stationary indices, the steady state probabilities that the system in vacation delay, vacation period, setup time and busy period are calculated respectively.

M/M/1 queue with vacation;delayed vacation;setup time;quasi birth and death process;matrix-geometric solution;stochastic decomposition

2015-01-16

国家特色专业(TS11496);安徽省高校自然科学研究项目(KJ2014ZD21);阜阳师范学院优秀重点学科(2010XK6-03);阜阳师范学院质量工程项目(2014JXTD01)资助。

张 杰(1981-)女,硕士,讲师,研究方向:随机运筹学。

O226

A

1004-4329(2015)03-021-04

10.14096/j.cnki.cn34-1069/n/1004-4329(2015)03-021-04

猜你喜欢

服务台指数分布等待时间
给学生适宜的等待时间
——国外课堂互动等待时间研究的现状与启示
服务台企 互促共赢 民族村走出特色振兴路
收费站的服务台
具有两个备用服务台的异步限制休假排队
指数分布抽样基本定理及在指数分布参数统计推断中的应用
意大利:反腐败没有等待时间
二元Weinman型指数分布随机变量之和、差、积、商及比率的分布
顾客等待心理的十条原则
顾客等待心理的十条原则
传承雷锋精神的“美丽”服务台