＊ 一般重試時(shí)間、伯努利單重休假的離散Geom/G/1重試排隊(duì)系統(tǒng)

朱翼雋,胡昌亮

(江蘇大學(xué) 理學(xué)院,江蘇 鎮(zhèn)江 212013)

＊一般重試時(shí)間、伯努利單重休假的離散Geom/G/1重試排隊(duì)系統(tǒng)

朱翼雋,胡昌亮

(江蘇大學(xué) 理學(xué)院,江蘇 鎮(zhèn)江 212013)

考慮一個(gè)帶有一般重試時(shí)間、伯努利單重休假的離散Geom/G/1重試排隊(duì)系統(tǒng).服務(wù)臺(tái)前無(wú)等待位置,新到達(dá)的顧客若發(fā)現(xiàn)服務(wù)臺(tái)忙或處于休假,則進(jìn)入重試區(qū)域等待重試;若發(fā)現(xiàn)服務(wù)臺(tái)空閑(不管有無(wú)顧客重試),就立即接受服務(wù).顧客在完成服務(wù)之后,若重試區(qū)域中有顧客存在,則服務(wù)臺(tái)以概率θ(0≤θ≤1)進(jìn)行一次單重休假,以概率ˉθ(=1-θ)重新等待顧客的到來(lái);若重試區(qū)域中無(wú)顧客,則服務(wù)臺(tái)也重新等待顧客的到來(lái).利用馬爾可夫鏈法,得到了本模型各個(gè)狀態(tài)的穩(wěn)態(tài)分布,并給出了系統(tǒng)顧客數(shù)的隨機(jī)分解結(jié)果及關(guān)于其的一個(gè)應(yīng)用.還給出了一個(gè)遞推公式去計(jì)算重試區(qū)域顧客數(shù)的分布.最后用數(shù)值例子說(shuō)明了一些參數(shù)對(duì)系統(tǒng)性能的影響.

離散重試排隊(duì);伯努利單重休假;隨機(jī)分解;穩(wěn)態(tài)分布

0 引言

由于離散排隊(duì)在通信系統(tǒng)以及其他相關(guān)領(lǐng)域的應(yīng)用,各種有關(guān)離散排隊(duì)的研究得到了極大的重視.許多計(jì)算機(jī)和通信系統(tǒng)的信號(hào)傳遞問(wèn)題都是發(fā)生在有固定間隔的時(shí)間段內(nèi),所以離散排隊(duì)較之連續(xù)排隊(duì)能更好的符合實(shí)際,并且近些年來(lái)出現(xiàn)了許多有關(guān)離散排隊(duì)在應(yīng)用方面的文章[1-3].

所謂重試排隊(duì),即顧客到達(dá)系統(tǒng)時(shí),如果發(fā)現(xiàn)服務(wù)臺(tái)忙,并且服務(wù)臺(tái)沒(méi)有等待位置,顧客就會(huì)進(jìn)入重試區(qū)域等待再次重試.重試排隊(duì)已經(jīng)廣泛的應(yīng)用于電話交換系統(tǒng)、電信系統(tǒng)和計(jì)算機(jī)通訊系統(tǒng)等領(lǐng)域[4-6].在過(guò)去,重試排隊(duì)的研究主要集中在連續(xù)時(shí)間上,但是自從 Yang和Li[7]首次將重試排隊(duì)的有關(guān)問(wèn)題推廣到離散時(shí)間上,一些離散重試排隊(duì)的研究陸續(xù)出現(xiàn)[8-11],但相比于比較成熟的連續(xù)重試排隊(duì)的研究,這方面的研究還不夠充分,需要進(jìn)一步的完善.

在日常生活中,顧客在完成一次服務(wù)后,即使重試區(qū)域還有顧客存在,服務(wù)臺(tái)也有可能進(jìn)行休假.帶有休假的連續(xù)重試排隊(duì)的研究比較多[12-14],但有關(guān)具有休假的離散重試排隊(duì)的文章很少.在實(shí)際生活中,服務(wù)員完成一次服務(wù)之后,可以根據(jù)重試區(qū)域顧客的多少,決定是繼續(xù)為顧客服務(wù)還是選擇進(jìn)行一次單重休假,此即伯努利單重休假規(guī)則.本文在離散重試排隊(duì)的基礎(chǔ)上,加入一般重試時(shí)間及伯努利單重休假規(guī)則,得到了一些重要的穩(wěn)態(tài)結(jié)果及數(shù)值分析結(jié)果.

1 模型描述

考慮一個(gè)離散Geom/G/1重試排隊(duì)早到達(dá)系統(tǒng),顧客的到達(dá)過(guò)程依據(jù)概率為p的Bernoulli過(guò)程.服務(wù)臺(tái)前無(wú)等待位置,若顧客到達(dá)服務(wù)臺(tái)時(shí),發(fā)現(xiàn)服務(wù)臺(tái)忙或者處于假期,就會(huì)進(jìn)入重試區(qū)域等待再次重試;如果服務(wù)臺(tái)處于空閑狀態(tài),則立即接受服務(wù)(不管此時(shí)重試區(qū)域隊(duì)首顧客是否正在重試).服務(wù)臺(tái)完成一次服務(wù)后,如果重試區(qū)域還有顧客存在,則服務(wù)臺(tái)以概率θ(0≤θ≤1)進(jìn)行一次單重休假,休假結(jié)束之后,重新等待為顧客服務(wù),以概率ˉθ重新等待顧客的到來(lái);如果重試區(qū)域沒(méi)有顧客,則服務(wù)臺(tái)重新等待顧客的到來(lái)并為其服務(wù).

2 馬氏鏈及穩(wěn)態(tài)分布

在時(shí)刻m+處,系統(tǒng)狀態(tài)可由過(guò)程Xm=(Cm,ξm,Nm)來(lái)描繪.此處Cm表示服務(wù)臺(tái)的狀態(tài)(0,1,2分別表示服務(wù)臺(tái)處于空閑,服務(wù),休假狀態(tài)),Nm表示重試區(qū)域的顧客數(shù),當(dāng)Cm=0時(shí),ξm表示剩余的重試時(shí)間;當(dāng)Cm=1時(shí),ξm表示剩余的服務(wù)時(shí)間;當(dāng)Cm=2時(shí),ξm表示剩余的休假時(shí)間.則其狀態(tài)空間為:

本文將研究馬氏鏈{Xm,m∈N}的平穩(wěn)分布,即

為了使研究能夠繼續(xù),給出下面兩個(gè)引理:

引理1 對(duì)于0≤x≤1,不等式A(x)≤x,S(x)≤x,V(x)≤x成立.

證明 由概率母函數(shù)A(x),S(x),V(x)的凸性可知,對(duì)于0≤x≤1,三不等式成立.

3 隨機(jī)分解

隨機(jī)分解原理是由Fuhrmann和Cooper[16]第一次引入排隊(duì)系統(tǒng)的,起初隨機(jī)分解原理在排隊(duì)系統(tǒng)中的作用是分析各種休假策略對(duì)經(jīng)典排隊(duì)模型的影響,但隨著研究的深入,它也可以用于比較復(fù)雜的離散重試排隊(duì)系統(tǒng)中.

4 穩(wěn)態(tài)概率計(jì)算

令ψk=P{N=k},則ψk表示重試區(qū)域顧客數(shù)為k個(gè)的概率.下面將會(huì)給出一個(gè)遞推公式,用此計(jì)算本模型中重試區(qū)域顧客數(shù)分布的概率.

由定理4可以知道,若知道ψ(z)的各階導(dǎo)數(shù),重試區(qū)域顧客數(shù)的概率分布就可求得.

5 數(shù)值分析

在此部分,將會(huì)用數(shù)值例子來(lái)研究一些參數(shù)對(duì)系統(tǒng)性能的影響.假設(shè)p=0.1,并且重試時(shí)間,服務(wù)時(shí)間,休假時(shí)間分別服從參數(shù)為r,q1,q2的幾何分布,則有分布

sj=q1(1-q1)j-1,vj=q2(1-q2)j-1,ai=ri(1-r),j≥1,i≥0,且0＜q1,q2＜1,0≤r＜1.

同時(shí),約定q1=q2=0.5.下面討論,對(duì)于不同的θ,系統(tǒng)非空的概率、重試區(qū)域平均顧客數(shù)分別與參數(shù)r的影響.

圖1描繪了參數(shù)r與系統(tǒng)非空的概率之間的關(guān)系.由圖1可以看出,對(duì)于不同參數(shù)θ,系統(tǒng)非空的概率是隨著θ增大而增大的;圖2描繪了參數(shù)r與重試區(qū)域平均顧客數(shù)之間的關(guān)系,可以看出,E(N)也是隨著θ增大而增大的.同時(shí)可以知道,r值越大,對(duì)1-π0,0,E(N)的影響也就越大.

圖1 系統(tǒng)非空的概率與 r的關(guān)系Fig.1 Relation between the parameter r and the probability of non-empty system

圖2 重試區(qū)域平均顧客數(shù)與 r的關(guān)系Fig.2 Relation between the parameter r and the customers in obit site

最后,利用定理4給出的遞推公式計(jì)算重試區(qū)域顧客數(shù)的概率分布.表1和表2(P49)分別闡明了在θ=0.3,0.6,r=0,0.3,0.6,0.9的情況下,重試區(qū)域顧客的概率分布情況.根據(jù)表中的結(jié)果,可以做出結(jié)論:隨著θ的增大,重試區(qū)域中無(wú)顧客的概率是下降的,而重試區(qū)域中有非零顧客的概率是增大的;固定θ,可以看出,隨著r的增大,重試區(qū)域中無(wú)顧客的概率也是下降的,而重試區(qū)域中有非零顧客的概率同樣也是增大的.

表1 重試區(qū)域顧客數(shù)的概率分布(θ=0.3)Table 1 Probability distribution of queue length(θ=0.3)

表2 重試區(qū)域顧客數(shù)的概率分布(θ=0.6)Table 2 Probability distribution of queue length(θ=0.6)

6 小結(jié)

在這篇文章中,我們考慮了一個(gè)帶有伯努利休假、一般重試時(shí)間的離散Geom/G/1重試排隊(duì)系統(tǒng),研究了它的穩(wěn)態(tài)分布、隨機(jī)分解及數(shù)值運(yùn)算的結(jié)果,具有一定的現(xiàn)實(shí)意義.重試區(qū)域中的顧客除非接受服務(wù)后離開(kāi),否則就會(huì)一直等到接受服務(wù).今后的研究可以將重點(diǎn)集中在帶有不耐煩顧客之上,在此基礎(chǔ)上,重試區(qū)域中的顧客就會(huì)根據(jù)具體的情況決定是繼續(xù)等待重試,接受服務(wù),還是選擇離開(kāi).

[1] Bruneel H,Kim B G.Discrete-Time Models for Communication Systems Including A TM[M].Boston:Kluwe Academic Publishers,1933.

[2] Takagi H.Queueing Analysis:A foundation of Performance Evaluation,in:Discrete-time Systems[M].vol3,North Holland,Amsterdan,1993.

[3] Woodward M E.Communication and Computer Networks:Modelling with Discrete-time Queues[M].IEEE Computer Soc press,Los Alamitors,CA,1994.

[4] Artalejo J R.A Classified bibliography of Research on Retrial Queues:Progress in 1990-1999[J].Top,1999,7(2):187-211.

[5] Artalejo J R.A Classified Bibliography on Retrial Queues[J].Mathm atical and Computer Modelling,1999,30:1-6.

[6] Falin G I,Templeton J G G.Retrial Queues[M].Chapman&Hall,London,1997.

[7] Yang T,Li H.On the Steady-state Queue Size Distribution of the Discrete-time Geo/G/1 Queue with Repeated Customers[J].Queueing Systems,1995,21:199-215.

[8] Atencia I,Mo reno P.Discrete-time Geo[X]/G/1 Retrial Queue with Bernoulli Feedback[J].Com puters and Operations research,2004,31:359-381.

[9] Atencia I,Moreno P.A Discrete-time Geo/G/1 Retrial Queue with General Retrial Times[J].Queueing Systems,2004,48:5-21.

[10] 王金亭,趙青.兩種失效模式下離散時(shí)間重試排隊(duì)之研究[J].應(yīng)用數(shù)學(xué)學(xué)報(bào),2008,31(5):901-909.

[11] 陳佩樹(shù),朱翼雋,陳燕.有一般重試時(shí)間的 GeoX/G/1重試排隊(duì)系統(tǒng)[J].江蘇大學(xué)學(xué)報(bào):自然科學(xué)版,2008,29(2):181-184.

[12] 陳佩樹(shù),朱翼雋,徐潔.有Bernoulli休假和可選服務(wù)的M/G/1重試反饋排隊(duì)模型[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2008,38(11):92-102.

[13] 武惠玲,方春鋒.有休假閥值M和顧客丟失的M/G/1重試休假排隊(duì)系統(tǒng)[J].華南師范大學(xué)學(xué)報(bào):自然科學(xué)版,2006(2):43-49.

[14] Aissani A.An MX/G/1 Energetic Retrial Queue with Vacations and it’s Control[J].Electronic Notes in Theoretical Com puter Science,2009,253(3):33-44.

[15] 孫微,田乃碩.帶有準(zhǔn)入規(guī)則的伯努利單重休假 Geomξ/G/1排隊(duì)模型[J].燕山大學(xué)學(xué)報(bào),2008,32(6):539-543.

[16] Fuhrmann SW,Cooper RB.Stochastic Decomposition in The M/G/1 Queue with Generalied Vocations[J].Ope-rational Research,1985,32:1119-1129.

[17] Artalejo J R,Falin G I.Stochastic Decomposition for Retrial Queues[J].Top,1994,2:329-342.

A Discrete-Time Geom/G/1 Retrial Queue with General Retrial Times and a Single Vacation Under Bernoulli Schedule

ZHU Yi-jun,HU Chang-liang
(Faculty of Science,Jiangsu University,Zhenjiang212013,China)

We consider a discrete-timeGeom/G/1 retrial queue with general retrial times,a single vacation under Bernoulli schedule.There is no waiting position in the server,and a new arriving customer finds the server busy or at vacation,he w ill join the orbit to retry getting the service,or he will accept service at once(No matter there is a retrial customer).After the service,the server either goes for a vacation with probality θ(0≤θ≤1)or may continue to wait the customer with probalityˉθ,if there is a customer in the orbit at least;Ortherwise,the server may wait the customer too.Applying for Markov chain,w e derive the various steady state distributions of this system,and give a stochastic decomposition law of the system size and a application about it.A recursive form ular is also built up to facilitate the orbit site distribution.Finally,some numercial examples show the influence of the parameters on the system performance.

discrete-time retrial queues;a single vacation under Bernoulli schedule;stochastic decomposition;steady state distribution

O226

A

0253-2395(2011)01-0042-09＊

2010-03-20;

2010-07-16

國(guó)家自然科學(xué)基金(70571030;10571076)

朱翼雋(1945-),男,安徽歙縣人,教授,博士生導(dǎo)師,主要從事排隊(duì)論和隨機(jī)網(wǎng)絡(luò)方面的研究.