Min(N,D)-策略下M/G/1排隊(duì)系統(tǒng)的離去過(guò)程?

魏瑛源, 唐應(yīng)輝, 顧建雄, 余玅妙

(1-河西學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅張掖 734000;2-四川師范大學(xué)數(shù)學(xué)與軟件科學(xué)學(xué)院，成都 610066;3-河西學(xué)院物理與機(jī)電工程學(xué)院，甘肅張掖 734000;4-四川理工學(xué)院理學(xué)院，四川自貢 643000)

1 引言

在排隊(duì)網(wǎng)絡(luò)中，一個(gè)排隊(duì)系統(tǒng)的輸出即為下游排隊(duì)系統(tǒng)的輸入，直接影響下游排隊(duì)系統(tǒng)的各項(xiàng)指標(biāo)，而且在一段已知時(shí)間內(nèi)離去顧客的平均數(shù)也反映了系統(tǒng)的工作效率．因此，離去過(guò)程是排隊(duì)系統(tǒng)理論研究的一個(gè)重要指標(biāo)，也是決策優(yōu)化的理論依據(jù)．

近年來(lái)，一些策略休假的排隊(duì)系統(tǒng)得到了較好的研究，經(jīng)典的有T-策略休假[1-3]，D-策略休假[4-6]和N-策略休假[7-10]．T-策略休假是指服務(wù)員休假時(shí)間為事先設(shè)定的定長(zhǎng)時(shí)間T(后來(lái)有文獻(xiàn)推廣到隨機(jī)時(shí)間V的休假策略)，D-策略休假是指當(dāng)系統(tǒng)中等待服務(wù)的顧客所需總的服務(wù)時(shí)間不小于事先設(shè)定的時(shí)間量D時(shí)，服務(wù)員就立即終止休假為顧客服務(wù)，而N-策略是指系統(tǒng)中有N個(gè)顧客時(shí)服務(wù)員就立即終止休假．這三個(gè)單一策略的休假是從不同側(cè)面來(lái)刻畫(huà)的休假機(jī)制，他們各自有不同的優(yōu)勢(shì)和缺陷．例如，僅依靠系統(tǒng)中有N個(gè)顧客就重新開(kāi)始服務(wù)或結(jié)束休假，系統(tǒng)會(huì)變得比較警惕，在某些情形下是不必要的，正如在緩沖區(qū)中的大量顧客未必會(huì)成為服務(wù)員大工作量的標(biāo)志，因?yàn)樵S多顧客所需的服務(wù)時(shí)間也許較短．然而，N-策略沒(méi)有考慮這一點(diǎn)．另一方面，僅僅因?yàn)橐纬梢粋€(gè)適當(dāng)?shù)睦鄯e工作量，過(guò)多的顧客數(shù)又會(huì)使得緩沖區(qū)存貨過(guò)多，這就成為了D-策略的盲區(qū)．這兩種策略哪一個(gè)更合適依賴(lài)于系統(tǒng)的構(gòu)造和費(fèi)用因素．如果所有因素都需要被考慮，又是什么策略？另外，從管理角度而言，當(dāng)生產(chǎn)制造環(huán)境發(fā)生改變并且系統(tǒng)擁有者想轉(zhuǎn)換成另一種控制策略時(shí)，在大多數(shù)情況下，拋棄現(xiàn)有的硬件系統(tǒng)是不可能的．在這種情況下，一些多閥值聯(lián)合策略的排隊(duì)模型被提出并得到了研究，例如Min(N,V)-策略M/G/1排隊(duì)[11-13]和Min(N,D)-策略M/G/1排隊(duì)[14-16]．多閥值聯(lián)合策略為系統(tǒng)的優(yōu)化提供了更大的靈活性，是一種可供選擇的好方案．例如，在本文討論的Min(N,D)-策略M/G/1排隊(duì)系統(tǒng)中，僅僅通過(guò)使N→∞或者D→∞，系統(tǒng)就能從一種策略轉(zhuǎn)換為另一種策略，而且Min(N,D)-策略的另一個(gè)益處是：從長(zhǎng)期運(yùn)行操作費(fèi)用角度而言，Min(N,D)-策略至少能超越單一的N-策略或者單一的D-策略，因?yàn)镸in(N,D)-策略在同一時(shí)間利用工作量和顧客數(shù)兩個(gè)信息．

Lee等[14]分析基于Min(N,D)-策略的MAP/G/1排隊(duì)，討論隊(duì)長(zhǎng)和等待時(shí)間，并給出數(shù)值實(shí)例．Lee和Seo[15]研究Min(N,D)-策略下的M/G/1排隊(duì)模型，在假定系統(tǒng)已處于平穩(wěn)狀態(tài)并且服務(wù)時(shí)間具有概率密度函數(shù)的條件下(這一假定條件較苛刻)，得到穩(wěn)態(tài)隊(duì)長(zhǎng)分布的概率母函數(shù)，并給出線性費(fèi)用函數(shù)下的最優(yōu)成本控制．其進(jìn)一步的研究可見(jiàn)文獻(xiàn)[16]，在假定服務(wù)時(shí)間服從一般分布下(不假定系統(tǒng)一開(kāi)始處于平穩(wěn)狀態(tài))，得到系統(tǒng)的瞬態(tài)隊(duì)長(zhǎng)分布和穩(wěn)態(tài)隊(duì)長(zhǎng)分布的遞推表達(dá)式，并對(duì)系統(tǒng)中有j個(gè)顧客的穩(wěn)態(tài)概率進(jìn)行數(shù)值計(jì)算．但是到目前為止，還沒(méi)有文獻(xiàn)對(duì)Min(N,D)-策略下M/G/1排隊(duì)系統(tǒng)的離去過(guò)程進(jìn)行研究．鑒于此，本文考慮此排隊(duì)系統(tǒng)，運(yùn)用全概率分解，更新過(guò)程理論和Laplace-Stieltjes變換，從任意初始狀態(tài)i(i=0,1,2,···)出發(fā)(不假定系統(tǒng)一開(kāi)始處于平穩(wěn)狀態(tài))，討論在(0,t]內(nèi)離去顧客的平均數(shù)以及其漸近展開(kāi)，揭示了系統(tǒng)的離去過(guò)程所具有的隨機(jī)分解特性：(0,t]內(nèi)離去顧客的平均數(shù)被分解為兩部分，一部分是服務(wù)員忙的概率Ai(t)，另一部分是忙期中的服務(wù)平均更新次數(shù)，從而簡(jiǎn)化了對(duì)離去過(guò)程的研究．

2 模型描述

考慮一個(gè)基于Min(N,D)-策略的M/G/1排隊(duì)系統(tǒng)，我們約定：

1) 顧客到達(dá)過(guò)程是參數(shù)為λ的Poisson流，即相繼到達(dá)的間隔時(shí)間序列{τi,i=1,2,···}相互獨(dú)立且服從相同的負(fù)指數(shù)分布F(t)=1?e?λt,t≥0．顧客的服務(wù)時(shí)間序列{χk,k=1,2,···}相互獨(dú)立且服從相同的任意分布G(t)，且平均服務(wù)時(shí)間為μ<∞)．服從FCFS服務(wù)規(guī)則；

2) 服務(wù)員采取Min(N,D)-策略是指，每當(dāng)系統(tǒng)變空時(shí)，服務(wù)員開(kāi)始處于閑期(空閑但在崗)，直到系統(tǒng)中累積到達(dá)了N(N≥1)個(gè)顧客，或者到達(dá)系統(tǒng)等待服務(wù)的顧客所需服務(wù)時(shí)間總量不小于D(D>0)，無(wú)論哪一個(gè)先發(fā)生，處于閑期的服務(wù)員將重新開(kāi)始服務(wù)顧客，直到系統(tǒng)再次變空，其中N是預(yù)先給定的正整數(shù)，D是預(yù)先給定的正實(shí)數(shù)；

3) 到達(dá)的間隔時(shí)間和顧客的服務(wù)時(shí)間是相互獨(dú)立的；

4) 系統(tǒng)在t=0時(shí)刻的顧客數(shù)為N(0)=i(i=0,1,2,···)，且當(dāng)N(0)=0時(shí)，即在t=0時(shí)刻，如果系統(tǒng)是空的，則服務(wù)員留在系統(tǒng)中等待顧客的到達(dá)，且到達(dá)的第一個(gè)顧客立即被服務(wù)，而當(dāng)N(0)=i,i=1,2,···時(shí)，服務(wù)員按照FCFS規(guī)則為顧客服務(wù)，即只有在服務(wù)員繁忙一段時(shí)間后才實(shí)行Min(N,D)-策略(這種假設(shè)更符合實(shí)際情況，但平穩(wěn)結(jié)果與此假設(shè)無(wú)關(guān))．

注1N(t)表示系統(tǒng)在時(shí)刻t的隊(duì)長(zhǎng)，即時(shí)刻t系統(tǒng)中的顧客數(shù)；表示系統(tǒng)的交通強(qiáng)度；

分別表示相應(yīng)G(t)的Laplace變換(簡(jiǎn)稱(chēng)L變換)和Laplace-Stieltjes變換(簡(jiǎn)稱(chēng)LS變換)；?(s)表示復(fù)變數(shù)s的實(shí)部；G(k)(t)表示相應(yīng)G(t)的k(k≥1)重Laplace-Stieltjes卷積，即

且

3 預(yù)備知識(shí)

系統(tǒng)閑期為從系統(tǒng)剛變空的時(shí)刻起，直到其后第一個(gè)顧客到達(dá)的時(shí)刻為止這一段時(shí)間．如果用表示第j個(gè)系統(tǒng)閑期長(zhǎng)度，則由到達(dá)過(guò)程為參數(shù)λ的Poisson過(guò)程，易知系統(tǒng)閑期的分布為

系統(tǒng)忙期為從第一個(gè)顧客到達(dá)空閑系統(tǒng)的時(shí)刻起，直到系統(tǒng)再次變空為止的這一段時(shí)間．服務(wù)員閑期為從系統(tǒng)剛變空的時(shí)刻起，直到服務(wù)員開(kāi)始為顧客服務(wù)為止的這一段時(shí)間．服務(wù)員忙期為從服務(wù)員開(kāi)始為顧客服務(wù)的時(shí)刻起，直到系統(tǒng)再次變空為止的這一段時(shí)間．令b表示由一個(gè)顧客開(kāi)始的服務(wù)員忙期長(zhǎng)度，

則：

引理1[17]對(duì)?(s)>0，有b(s)是方程z=g(s+λ?λz)在|z|<1內(nèi)的唯一根，且

其中ω(0<ω<1)是方程z=g(λ?λz)在(0,1)內(nèi)的根．

又令表示由i個(gè)顧客開(kāi)始的服務(wù)員忙期長(zhǎng)度，因?yàn)榈竭_(dá)過(guò)程是Poisson過(guò)程，所以有

引理2[18]設(shè)M(t)表示以G(t)為分布函數(shù)的更新過(guò)程{χk,k=1,2,···}的更新函數(shù)，χk表示第k個(gè)顧客所需的服務(wù)時(shí)間，期望為記

進(jìn)一步，若分布函數(shù)G(t)是非格的，則

4 離去過(guò)程分析

令ξ(t)=1表示在時(shí)刻t系統(tǒng)處于服務(wù)員忙期，Ai(t)=P{ξ(t)=1|N(0)=i}，即Ai(t)表示在初始狀態(tài)N(0)=i下，時(shí)刻t服務(wù)員忙的概率，其Laplace變換為

定理1[17]當(dāng)N=1時(shí)，對(duì)?(s)>0，有

而且平穩(wěn)結(jié)果

證明 當(dāng)N=1時(shí)，本文研究的排隊(duì)系統(tǒng)成為經(jīng)典M/G/1排隊(duì)系統(tǒng)，證明過(guò)程見(jiàn)文獻(xiàn)[17]．

定理2當(dāng)N≥2且D>0時(shí)，對(duì)?(s)>0，有

而且平穩(wěn)結(jié)果

其中

當(dāng)j

證明 令

且S0=l0=0．由于顧客的到達(dá)過(guò)程是同參數(shù)的齊次Poisson流，因此，服務(wù)員忙期的開(kāi)始時(shí)刻與結(jié)束時(shí)刻均為更新點(diǎn)，注意到顧客的離去只發(fā)生在服務(wù)員忙期，且當(dāng)N(0)=0時(shí)系統(tǒng)不實(shí)行Min(N,D)-策略，到達(dá)的第一個(gè)顧客立即被服務(wù)，所以服務(wù)員閑期和服務(wù)員忙期構(gòu)成一個(gè)延遲更新過(guò)程，運(yùn)用更新過(guò)程理論與全概率分解技術(shù)得到

其中bk表示從初始狀態(tài)N(0)=0出發(fā)的第k個(gè)服務(wù)員忙期長(zhǎng)度，表示第k個(gè)系統(tǒng)閑期長(zhǎng)度，k≥1．

類(lèi)似地，當(dāng)i=1,2,···時(shí)，同理可得

對(duì)(3)式和(4)式作L變換，有

由(5)式和(6)式可得關(guān)系式

將(7)式代入(5)式，經(jīng)整理可得(1)式，再把(1)式代入(7)式可得(2)式．再由關(guān)于Laplace變換的Abelian定理

經(jīng)計(jì)算得到Ai(t)(i=0,1,2,···)的平穩(wěn)結(jié)果的表達(dá)式，從而完成定理1的證明．

下面討論從初始條件i(i=0,1,2,···)出發(fā)，在(0,t]中離去顧客的平均數(shù)．令

也就是說(shuō)Mi(t)表示系統(tǒng)從初始狀態(tài)N(0)=i出發(fā)，在(0,t]內(nèi)服務(wù)完顧客的平均數(shù)，

為Mi(t)的Laplace-Stieltjes變換．

定理3[17]當(dāng)N=1時(shí)，對(duì)?(s)>0，有

而且平穩(wěn)結(jié)果

證明 當(dāng)N=1時(shí)，本文研究的排隊(duì)系統(tǒng)成為經(jīng)典M/G/1排隊(duì)系統(tǒng)，證明過(guò)程見(jiàn)文獻(xiàn)[17]．

定理4當(dāng)N≥2且D>0時(shí)，對(duì)?(s)>0，有

而且平穩(wěn)結(jié)果

證明 令

1) 令T(t)=E[(0,b]內(nèi)離去的顧客數(shù),b≤t],C(t)=E[(0,t]內(nèi)離去的顧客數(shù),b>t≥0]．

考慮到顧客的到達(dá)過(guò)程是同參數(shù)的齊次Poisson流，顧客的離去只發(fā)生在服務(wù)員忙期，在服務(wù)員忙期b內(nèi)，由于服務(wù)時(shí)間形成一個(gè)更新過(guò)程{χk,k=1,2,···}，且服務(wù)員忙期b的結(jié)束時(shí)刻為更新點(diǎn)，于是用b對(duì)M(t)進(jìn)行全概率分解，得

則

2) 又令內(nèi)離去的顧客數(shù),內(nèi)離去的顧客數(shù),類(lèi)似地，用對(duì)M(t)進(jìn)行全概率分解，有

3) 由于顧客的離去只發(fā)生在服務(wù)員忙期，對(duì)M0(t)進(jìn)行全概率分解得到

當(dāng)i=1,2,···時(shí)，有

(13)式中的第三項(xiàng)為

將(11)式和(14)式代入(13)式，得

對(duì)(12)式和(15)式作LS變換，得

由(17)式和(18)式可得關(guān)系式

將(19)式代入(18)式可得進(jìn)一步可得

則(8)式得證．由于Mi(t)是關(guān)于t的增函數(shù)，根據(jù)Tauberian定理有

再利用定理2和引理2可得到(9)式，從而完成定理4的證明．

定理5若G(t)是非格的，且E[χ2]<∞，則對(duì)i=1,2,···，有

其中?表示Laplace-Stieltjes變換

證明 由作反演變換得

因此

根據(jù)Laplace-Stieltjes變換的Abelian定理可得

再運(yùn)用定理2和引理2即可得到(20)式．

推論1若G(t)是非格的，且E[χ2]<∞，則對(duì)i=1,2,···，當(dāng)t充分大時(shí)，計(jì)算Mi(t)的漸近表達(dá)式為

注2從本文五個(gè)定理可以得到如下結(jié)論：

l) 由定理1和定理2可知

這表明平穩(wěn)狀態(tài)下，服務(wù)員繁忙的概率(服務(wù)員為顧客服務(wù)的穩(wěn)態(tài)概率)為ρ，空閑的概率(休假的穩(wěn)態(tài)概率)為1?ρ；

2) 定理3和定理4中的結(jié)論表明，在平穩(wěn)狀態(tài)條件(ρ<1)下，系統(tǒng)在單位時(shí)間內(nèi)離去顧客平均數(shù)只與到達(dá)率λ有關(guān)，與服務(wù)率以及預(yù)先給定的數(shù)N和D無(wú)關(guān)．也就是說(shuō)對(duì)于Min(N,D)-策略M/G/1排隊(duì)系統(tǒng)與標(biāo)準(zhǔn)的M/G/1排隊(duì)系統(tǒng)，雖然有關(guān)Ai(t),Mi(t)瞬態(tài)結(jié)果不一樣，但其極限結(jié)果都一樣，所以根據(jù)定理5可得漸近表達(dá)式是一樣的．

因?yàn)樵贛in(N,D)-策略M/G/1排隊(duì)系統(tǒng)與標(biāo)準(zhǔn)的M/G/1排隊(duì)系統(tǒng)中，服務(wù)員處于繁忙的穩(wěn)態(tài)概率一樣！而在服務(wù)員處于繁忙的條件下，服務(wù)過(guò)程一樣，均是服務(wù)時(shí)間形成的更新過(guò)程，即

其中M(t)表示以服務(wù)時(shí)間作為更新間隔時(shí)間的更新過(guò)程在(0,t]時(shí)間內(nèi)的更新函數(shù)．這種結(jié)構(gòu)上的分解結(jié)果使得系統(tǒng)的離去過(guò)程更容易理解，可簡(jiǎn)化對(duì)離去過(guò)程的研究，為研究排隊(duì)網(wǎng)絡(luò)提供了理論基礎(chǔ)．

5 一些特殊情形

推論2當(dāng)N→∞時(shí)，本文研究的排隊(duì)系統(tǒng)為D-策略M/G/1排隊(duì)系統(tǒng)，有

推論3當(dāng)D→∞時(shí)，本文研究的排隊(duì)系統(tǒng)成為N-策略M/G/1排隊(duì)系統(tǒng)，有

推論4當(dāng)N=1時(shí)，本文研究的排隊(duì)系統(tǒng)成為經(jīng)典M/G/1排隊(duì)系統(tǒng)，有

與文獻(xiàn)[17]中的相應(yīng)結(jié)論完全一致．

致謝：本文作者對(duì)審稿人表示衷心感謝！

參考文獻(xiàn)：

[1]Ke J C.ModifiedTvacation policy for anM/G/lqueueing system with an unreliable server and startup[J].Mathematical and Computer Modelling,2005,41(11):1267-1277

[2]Kin D J,Moon S A.Randomized control ofT-policy for anM/G/1 system[J].Computer and Industrial Engineering,2006,51(4):684-692

[3]唐應(yīng)輝，黃蜀娟，余玅妙，等.推廣的(t,T)策略下M/G/1排隊(duì)系統(tǒng)隊(duì)長(zhǎng)分布的遞推解及最優(yōu)策略[J].工程數(shù)學(xué)學(xué)報(bào)，2009,26(2):251-259 Tang Y H,Huang S J,Yu M M,et al.The optimum policy and recursion solution of the queue-length distribution inM/G/1 queue system with generalized(t,T)policy[J].Chinese Journal of Engineering Mathematics,2009,26(2):251-259

[4]Lee H W,Beak J W,Jeon J.Analysis of theMX/G/1 queue underD-policy[J].Stochastic Analysis and Applications,2005,23(4):785-808

[5]Wang K H,Kuo C C,Ke J C.Optimal control of theD-policyM/G/1 queueing system with server breakdowns[J].American Journal of Applied Sciences,2008,5(5):565-573

[6]Lee H W,Kim S A,Lee S W.Analysis and cost optimization of theM/G/1 queue under theD-policy and LCFS discipline[J].Stochastic Analysis and Applications,2008,26(1):39-59

[7]Kella O.The threshold policy in theM/G/1 queue with server vacations[J].Naval Research Logistics,1989,36(1):111-123

[8]Hur S,Paik S J.The ef f ect of dif f erent arrival rates on theN-policy ofM/G/1 with server setup[J].Applied Mathematical Modelling,1999,23(4):289-299

[9]吳錦標(biāo)，尹小玲，劉再明.具有N-策略和負(fù)顧客的反饋搶占型的M/G/1重試可修排隊(duì)系統(tǒng)[J].應(yīng)用數(shù)學(xué)學(xué)報(bào)，2009,32(2):323-335 Wu J B,Yin X L,Liu Z M.TheM/G/1 retrialG-queues withN-policy,feedback,preemptive resume and unreliable server[J].Acta Mathematicae Applicatae Sinica,2009,32(2):323-335

[10]唐應(yīng)輝，蒲會(huì)，余玅妙.帶啟動(dòng)時(shí)間的N-策略M/G/1排隊(duì)系統(tǒng)的隊(duì)長(zhǎng)[J].系統(tǒng)工程理論與實(shí)踐，2011,31(1):131-137 Tang Y H,Pu H,Yu M M.Queue size ofM/G/1 queueing system withN-policy and set-up times[J].Systems Engineering–Theory&Practice,2011,31(1):131-137

[11]井彩霞，崔穎，田乃碩.Min(N,V)-策略休假的M/G/1排隊(duì)系統(tǒng)分析[J].運(yùn)籌與管理，2006,15(3):53-58 Jing C X,Cui Y,Tian N S.Analysis of theM/G/1 queueing system with Min(N,V)-policy[J].Operations Research&Management Science,2006,15(3):53-58

[12]唐應(yīng)輝，吳文青，劉云頗，等.基于多重休假的Min(N,V)-策略M/G/1排隊(duì)的隊(duì)長(zhǎng)分布[J].系統(tǒng)工程理論與實(shí)踐，2014,34(6):1533-1546 Tang Y H,Wu W Q,Liu Y P,et al.The queue length distribution ofM/G/1 queueing system with Min(N,V)-policy based on multiple server vacations[J].Systems Engineering–Theory&Practice,2014,34(6):1533-1546

[13]唐應(yīng)輝，吳文青，劉云頗.基于單重休假的Min(N,V)-策略M/G/1排隊(duì)系統(tǒng)分析[J].應(yīng)用數(shù)學(xué)學(xué)報(bào)，2014,37(6):976-995 Tang Y H,Wu W Q,Liu Y P.Analysis ofM/G/1 queueing system with Min(N,V)-policy based on single server vacation[J].Acta Mathematicae Applicatae Sinica,2014,37(6):976-995

[14]Lee H W,Seo W J,Lee S W,et al.Analysis of theMAP/G/1 queue under the Min(N,D)-policy[J].Stochastic Models,2010,26(1):98-123

[15]Lee H W,Seo W J.The performance of theM/G/1 queue under the dyadic Min(N,D)-policy and its cost optimization[J].Performance Evaluation,2008,65(10):742-758

[16]魏瑛源，唐應(yīng)輝，余玅妙.基于Min(N,D)-策略的M/G/1排隊(duì)系統(tǒng)的隊(duì)長(zhǎng)分布及最優(yōu)策略[J].系統(tǒng)科學(xué)與數(shù)學(xué)，2015,35(6):729-744 Wei Y Y,Tang Y H,Yu M M.Queue length distribution and optimum policy forM/G/1 queueing system under Min(N,D)-policy[J].Journal of Systems Science and Mathematical Sciences,2015,35(6):729-744

[17]唐應(yīng)輝，唐小我.排隊(duì)論：基礎(chǔ)與分析技術(shù)[M].北京：科學(xué)出版社，2006 Tang Y H,Tang X W.Queueing Theory:Fundamentals&Analytical Techniques[M].Beijing:Science Press,2006

[18]Ross S M.Stochastic Processes[M].New York:John Wiley&Sons,1983