具有多重工作休假的GI/Geo/1/∞离散时间排队模型的稳定性研究

程慧慧, 王文娟

(华北水利水电大学 数学与统计学院,河南 郑州 450046)

0 引言

随着社会的进步,排队论在交通、物流、通信、网络等领域的重要性日趋明显。为了满足人们的实际需要,带有休假的离散时间排队模型逐渐得到研究学者的重视。到目前为止,经典休假排队理论已经得到非常深入的研究。在2001和2002年,ZHANG等[1]和TIAN等[2]分别研究了带有多重休假政策的Geo/G/1(Geometric/General/1)和GI/Geo/1(General Independent/Geometric/1)模型。在2002年,SERVI等[3]提出了工作休假策略,此休假与经典休假理论的不同之处是处于休假时期的服务器不会完全停止工作,而是以更低的服务速率为顾客提供服务。这个工作休假策略曾应用于研究通信系统的波分复用技术。在2007年,LI等[4]以及LI和TIAN[5]分别研究了基于多重工作休假和假期中止的离散时间无限缓冲GI/Geo/1排队系统。在2009年,余玅妙等[6]研究了具有多重工作休假的有限缓冲GI/Geo/1/N离散时间排队模型,与具有工作休假的GI/Geo/1离散时间排队模型相关的详细内容可参考田乃硕[7]等人所写的书。

HUNTER[8]使用嵌入Markov链的方法研究GI/Geo/1排队模型,并由此得到了顾客到达前夕的概率分布。随后CHAUDHRY[9]等人在此基础上使用补充变量法和求根法得到顾客到达前夕系统容量的概率母函数。2019年,BARBHUIYA和GUPTA[10-11]研究了无限缓冲的GIX/GeoY/1离散时间排队模型。

综合上述讨论,接下来要研究的是具有多重工作休假的无限缓冲GI/Geo/1离散时间排队模型的稳定性,该模型的假设条件主要是:顾客单个到达单个服务且遵循先到先服务原则,服务时间服从几何分布。研究该模型时主要用到两个方法:一是使用嵌入Markov链法得到其遍历的充要条件，从而建立平衡方程;二是利用补充变量法构造Markov链,从而建立平衡方程,再利用非齐次差分方程进行求解。研究此模型的目的主要是得到系统稳定时顾客到达前夕和任意时刻的队长分布母函数形式,使结果易于计算。该模型的研究在分组交换和网络开关方面的应用起着非常重要的作用,比如密集波分复用技术在通信系统上的应用。

文章主要部分由以下4个小节构成:第1小节对模型进行综合描述,第2小节主要是构造Markov链并得到该Markov链遍历的充要条件,第3小节主要是求解系统稳定时任意时刻和顾客到达前夕的队长分布母函数形式,第4小节对全文进行总结。

1 模型描述

建立离散时间轴时,时间轴被分为离散的点0,1,…,m,…,相邻两点之间的长度相等。本文研究的是晚到延迟系统,即到达发生在(m-,m),离开发生在(m,m+)。假定工作休假的开始与结束发生在m-处。

模型的详细介绍如下:

1)设到达时间间隔为T,它的概率分布函数、概率母函数和均值函数分别为

2)单个服务器服务顾客遵循先到先服务的规则为：批量服务时间为S,且服从参数为μ的几何分布,S的概率分布函数为

3)与经典休假不同的是,服务器在工作休假期间并未完全停止工作,而是以较低的服务速率η(η<μ)为顾客服务,工作休假期间顾客的服务时间SV服从参数为η的几何分布,即

4)当系统变空时,即正规忙期结束后服务器会立即进入随机长度为V的工作休假期,V服从参数为γ的几何分布,它的概率分布函数为

当某次工作休假结束时,若系统非空,则立即停止休假返回系统,并将服务速率从η提高至μ,即开始它的正规忙期,此时正在接受低速率服务的顾客重新开始接受服务;否则,服务器将进行另一次独立同分布的工作休假。

2 Markov链的遍历性

Ω={(0,0)}∪{(k,i):k≥1,i=0,1},

记Qn的转移概率为

记fi为一个到达间隔内以速率μ刚好有i个顾客完成服务的概率,ki为到达间隔小于一个工作休假期,且在此到达间隔内以速率η刚好有i个顾客完成服务的概率,hi为一个到达间隔大于工作休假期,且在此到达间隔内刚好有i个顾客完成服务的概率。由此可得,

故Qn的转移概率矩阵为

其中

对于嵌入Markov链Qn的遍历性结论如下。

3 系统稳定时顾客到达前夕和任意时刻的队长分布

该模型把下一批次的剩余到达时间作为补充变量,并利用补充变量法构造Markov链。记N(m-)为m-时刻处系统中的顾客数,U(m-)为m-时刻处顾客的剩余到达时间,

易知Yn={N(m-),U(m-),H(m-)}构成一个离散时间Markov链。

定义{N(m-),U(m-),H(m-)}的联合概率,

另记

3.1 建立平衡方程及两个重要等式

考虑到系统在m-和(m+1)-两个时间点处的状态转移情况,令m→∞时,经过概率分析建立一组差分方程

π0,0(u-1)=π0,0(u)+ηπ1,0(u)+μπ1,1(u),

(1)

(2)

(3)

(4)

(5)

接下来的主要目标是找到系统稳定时的队长分布πn,0,n≥0,以及πn,1,n≥1。由于从(1)式～(5)式我们很难得到队长分布,因此需要对其进行Z变换。变换后的方程组为

(6)

(7)

(8)

(9)

(10)

将(6)式～(10)式相加得

(11)

由贝叶斯公式及(11)式可得两个重要等式

(12)

(13)

因为3.2节和3.4节的需要,把(8)和(10)式相加,可得

(14)

3.2 非齐次差分方程的建立

(15)

(16)

3.3 系统稳定时服务器处于工作休假期的队长分布

求解系统稳定时服务器处于工作休假期的队长分布时需用到引理1和引理2。

因为ρ<1且η<μ,所以1-aη<0。又因为δ充分小,所以在单位圆|d|=1-δ的条件下有|g(d)|<|f(d)|。由Rouche定理可得f(d)和f(d)+g(d)都有1个零点在单位圆内。引理得证。

(17)

因为

(18)

在单位圆|s|=1内有1个根(由引理1可得),所以记这个根分别为α1。

由此可得(17)式的通解为

(19)

其中α1为(17)式对应的特征方程的根,c1为待定的任意常数。

把(19)式代入(15)式可得

(20)

则由(19)式可得非齐次线性差分方程的通解形式为

(21)

其中

为求解(20)式的通解形式,需如下引理2。

要确保(21)式收敛,必须取e1=0,故(20)式的通解为

(22)

假设(22)式适用于n=1,则当n=1时,把n=1代入(7)式并使用(19)式可得

(23)

对(19)式求和并加上(23)式可得

(24)

3.4 系统稳定时服务器处于正规忙期的队长分布

由(18)式可得方程(17)存在一个特解为

(25)

把(25)式代入方程(15)可得其特解为

(26)

(27)

(28)

(29)

其中α2为(28)式对应的特征方程的根。

把(29)式代入(27)式可得(27)式的特解形式为

(30)

假设(30)式对于n=1时也成立，再对(29)式求和可得

(31)

3.5 系统稳定时顾客到达前夕和任意时刻的队长分布

把(24)式和(31)式代入(11)式可得

(32)

利用(32)式可解得c1。由此可得πn,0(0),n≥0和πn,1(0),n≥1的表达式以及

(33)

(34)

故利用(12)式、(13)式、(33)式、(34)式可得顾客到达前夕和任意时刻队长分布的母函数形式,即

综上可得如下定理2。

定理2当ρ<1时,系统稳定时顾客到达前夕和任意时刻的队长分布的母函数形式为

4 总结

在本文中,研究的主要内容是具有多重工作休假的离散时间排队模型的稳定性问题。在多重工作休假期间,服务器会以不同的速率进行工作,进而利用嵌入Markov链法和补充变量法得到系统稳定时顾客到达前夕与任意时刻队长分布的母函数形式。