一種帶有災(zāi)難和伯努利機(jī)制的M/M/1隊(duì)列

陳 潛， 劉力維， 閆俊娜

(1. 南京理工大學(xué) 理學(xué)院，南京 210094；2. 安陽學(xué)院 數(shù)理學(xué)院，河南 安陽 455000)

0 引 言

日常生活中到處都可看見隊(duì)列的身影，小到面包店，大到火車站、飛機(jī)場(chǎng)，排隊(duì)模型都發(fā)揮著不可或缺的作用?，F(xiàn)今，工業(yè)、互聯(lián)網(wǎng)、通訊、高新科技等發(fā)展迅速，災(zāi)難類排隊(duì)模型的應(yīng)用也越發(fā)普及。系統(tǒng)的運(yùn)行不是一帆風(fēng)順的，災(zāi)難發(fā)生會(huì)使系統(tǒng)失去工作能力，所有顧客從系統(tǒng)中永遠(yuǎn)離開。Yang等[1]考慮一個(gè)帶有清除機(jī)制的系統(tǒng)，首次將清除機(jī)制命名為“災(zāi)難”，求出系統(tǒng)隊(duì)長(zhǎng)的分布；Sudhesh等[2]在文獻(xiàn)[1]的基礎(chǔ)上研究了一類具有系統(tǒng)災(zāi)難的離散時(shí)間G/G/1隊(duì)列，導(dǎo)出系統(tǒng)中顧客人數(shù)的瞬態(tài)概率和穩(wěn)態(tài)概率。文獻(xiàn)[1，2]對(duì)于災(zāi)難類排隊(duì)模型的發(fā)展和應(yīng)用起到了重要作用，但是對(duì)于系統(tǒng)發(fā)生災(zāi)難后需要維修的情況考慮不全面。

災(zāi)難的發(fā)生意味著系統(tǒng)需要被維修。Economou等[3]研究了一個(gè)可修的M/M/1隊(duì)列，文中工作臺(tái)發(fā)生故障勿需等待就會(huì)得到維修，維修后會(huì)恢復(fù)其工作能力，使得維修在排隊(duì)模型中被廣泛研究。實(shí)際情況下，修理工到達(dá)后才可維修系統(tǒng)，即延遲維修；Yu等[4]在文獻(xiàn)[3]的基礎(chǔ)上考慮帶有延遲維修的M/M/1隊(duì)列，證明了穩(wěn)態(tài)存在的充要條件，使得維修狀態(tài)更加貼合實(shí)際；Rao等[5]研究?jī)呻A段馬爾可夫延遲維修排隊(duì)模型，服務(wù)器在服務(wù)的任何階段均可能出現(xiàn)故障，求出系統(tǒng)不同狀態(tài)下隊(duì)列長(zhǎng)度的均值和損失率，擴(kuò)充故障和延遲維修在系統(tǒng)中的范圍。但上述文獻(xiàn)對(duì)于工作人員休假情況研究不深入。

系統(tǒng)的工作必須由人指揮，注定需要安排工作人員休息。Keilson等[6]引入Bernoulli GI/G/1休假模型，證明窮舉服務(wù)的分解結(jié)果可擴(kuò)展到伯努利休假模型中；Arivudainambi等[7]研究了帶有伯努利休假的重試隊(duì)列，給出穩(wěn)態(tài)的充要條件，在模型求解過程中借用輔助變量法，使得模型求解更加便捷；徐金萍等[8]研究了帶有伯努利休假的M/M/1隊(duì)列，借助擬生滅理論，得出相關(guān)的概率表達(dá)式，為休假模型中擬生滅理論的應(yīng)用作出了推廣。

工作人員出錯(cuò)或系統(tǒng)卡頓會(huì)使當(dāng)前的服務(wù)出現(xiàn)問題，這時(shí)就需要反饋機(jī)制發(fā)揮作用。反饋指顧客經(jīng)過一次服務(wù)后沒有離去，而是回到隊(duì)首等待下次服務(wù)。潘致鋒等[9]分析一個(gè)帶有伯努利反饋機(jī)制的隊(duì)列，借助馬氏鏈方法,求解了穩(wěn)態(tài)下系統(tǒng)中顧客數(shù)的表達(dá)式，給出了逗留時(shí)間的LST(拉普拉斯變換)，推廣了馬氏鏈的應(yīng)用；Bouchentouf等[10]分析一個(gè)伯努利反饋隊(duì)列，導(dǎo)出了工作臺(tái)處于忙期時(shí)系統(tǒng)隊(duì)長(zhǎng)的顯式表達(dá)式；Shweta[11]研究離散時(shí)間下帶有反饋的隊(duì)列，使用生成函數(shù)法求出了系統(tǒng)和重試軌道的隊(duì)列長(zhǎng)度；Ye等[12]在文獻(xiàn)[1，3，6]的基礎(chǔ)上研究了伯努利休假下具有災(zāi)難和維修的單服務(wù)臺(tái)隊(duì)列，求出了穩(wěn)態(tài)隊(duì)長(zhǎng)的分布和一些性能指標(biāo)，但模型仍然不夠完善，還需補(bǔ)充。

綜上所述，為了使帶有災(zāi)難的排隊(duì)模型更加完善貼合現(xiàn)實(shí)；本文在帶有災(zāi)難和伯努利機(jī)制的隊(duì)列中加入了延遲維修和反饋狀態(tài)；利用馬氏鏈方法和強(qiáng)馬爾可夫性，求出相應(yīng)的性能指標(biāo)，使其具有更廣泛的意義和應(yīng)用價(jià)值。

1 模型描述

研究一個(gè)伯努利機(jī)制下具有災(zāi)難、延遲維修、反饋和休假的M/M/1隊(duì)列。顧客按強(qiáng)度為λ的泊松流到達(dá)，工作人員對(duì)系統(tǒng)最前端的顧客完成一次服務(wù)時(shí)，休假的概率為q(0

t時(shí)刻系統(tǒng)工作人員的狀態(tài)和人數(shù)分別用I(t)和N(t)表示，對(duì)上述排隊(duì)系統(tǒng)可構(gòu)建二維連續(xù)時(shí)間的馬爾可夫鏈{(I(t),N(t),t≥0)}。狀態(tài)空間Ω={{(i,n)}∪{(1,j)}∪{(4,0)},i=0,2,3;j=1,2,3，…;n=0,1,2，…}，其中

狀態(tài)轉(zhuǎn)移率圖如圖1所示，(4,0)對(duì)應(yīng)空閑狀態(tài)。

圖1 狀態(tài)轉(zhuǎn)移率圖

2 穩(wěn)態(tài)分布與系統(tǒng)隊(duì)長(zhǎng)

系統(tǒng)穩(wěn)態(tài)存在可由災(zāi)難的性質(zhì)分析得出，故定義穩(wěn)態(tài)概率：

可得出平衡方程,如式(1)—式(9)所示。

(λ+η)π0,0=μqmπ1,1

(1)

(λ+η)π0,n=μqmπ1,n+1+μqkπ1,n+λπ0,n-1,n≥1

(2)

λπ4,0=μpmπ1,1+ηπ0,0+γπ3,0

(3)

(λ+μ+α)π1,1=

μpmπ1,2+μpkπ1,1+ηπ0,1+γπ3,1+λπ4,0

(4)

(λ+μ+α)π1,n=

μpmπ1,n+1+μpkπ1,n+ηπ0,n+γπ3,n+λπ1,n-1,n≥2

(5)

(6)

(λ+β)π2,n=λπ2,n-1,n≥1

(7)

(λ+γ)π3,0=βπ2,0

(8)

(λ+γ)π3,n=λπ3,n-1+βπ2,n,n≥1

(9)

由正則化條件式(10)：

(10)

定義一些母函數(shù)：

故式(10)可表示為式(11)：

G0(1)+G1(1)+G2(1)+G3(1)+π4,0=1

(11)

將式(2)乘以zn，并對(duì)n從1到∞求和，再加上式(1)可得式(12)：

(12)

由式(6)、式(7)可得式(13)：

(13)

由式(8)、式(9)可得式(14)：

(14)

對(duì)式(5)乘以zn，并對(duì)n從2到∞求和，再加上式(2)、式(4)、式(12)和z×式(3)，可得式(15)：

(15)

由f″(z)在0

f′(0)(η+λ)2=

[α+μ(1-pk)+λ](η+λ)2-μqη(λ+kη)=

(α+μp-μpk+λ)(η+λ)2+μq(η2+λ2+ηλ)-μqkη2=

(α+μpm+λ)(η+λ)2+μq(mη2+λ2+ηλ)

因系統(tǒng)穩(wěn)態(tài)存在，在0

γz*G3(z*)-λz*(1-z*)π4,0=0

即如式(16)所示：

(16)

結(jié)合式(12)、式(13)、式(14)和式(16)，代入式(11)可得式(17)：

(17)

式(17)中：

A=λ(1-z*)[γ+λ(1-z*)][β+λ(1-z*)]

由式(17)代入式(16)可得式(18)：

(18)

由式(17)代入式(13)可得式(19)：

(19)

由式(17)代入式(14)可得式(20)：

(20)

式(20)中：y(z)=[γ+λ(1-z)][β+λ(1-z)]。結(jié)合式(18)和式(20)，代入式(15)可得式(21)：

(21)

由式(21)代入式(12)可得式(22)：

(22)

定理2 該隊(duì)列中，系統(tǒng)中顧客數(shù)的PGF(概率生成函數(shù)):

G(z)=G0(z)+G1(z)+G2(z)+G3(z)+π4,0

該式中各值已由式(18)—式(22)給出。

3 性能指標(biāo)分析

令系統(tǒng)中的隊(duì)列長(zhǎng)度為L(zhǎng)，則系統(tǒng)的平均隊(duì)長(zhǎng)為

工作人員處于休假期的概率:

Pv=G0(1)=

工作人員處于忙期的概率:

Pw=G1(1)=

工作人員處于延遲期的概率:

Pd=G2(1)=

工作人員處于維修期的概率:

Pm=G3(1)=

工作人員處于空閑狀態(tài)的概率:

Pi=π4,0=

4 穩(wěn)態(tài)逗留時(shí)間的LST

假設(shè)系統(tǒng)原來隊(duì)長(zhǎng)為n，標(biāo)記顧客到來為隊(duì)伍中的第n+1個(gè)顧客，標(biāo)記顧客在系統(tǒng)中消耗的時(shí)長(zhǎng)即為顧客在系統(tǒng)中的逗留時(shí)間，用W來表示，W*(s)就是W的拉普拉斯變換(LST)。

定理3 隊(duì)列中顧客逗留時(shí)間的LST：

W*(s)=

其中:

證明由強(qiáng)馬爾可夫性對(duì)5種狀態(tài)下的標(biāo)記顧客進(jìn)行分析。

(23)

(24)

(25)

(26)

(27)

(28)

(29)

(30)

(31)

對(duì)式(23)—式(31)求解，可得式(32)—式(39)：

(32)

(33)

(34)

(35)

(36)

(37)

(38)

(39)

由式(31)—式(34)得式(40)：

(40)

由式(33)、式(35)和式(40)可得式(41)：

(41)

由式(32)、式(33)和式(41)可得式(42)：

(42)

由式(38)、式(39)和式(41)可得式(43)：

(43)

由式(36)、式(37)和式(43)可得式(44)：

(44)

隊(duì)列中顧客逗留時(shí)間的LST即為

(45)

將式(31)、式(41)—式(44)代入式(45)。證畢。

5 數(shù)值模擬

本部分通過數(shù)值實(shí)驗(yàn)解釋各參數(shù)對(duì)系統(tǒng)中平均顧客人數(shù)的影響。

令λ=1,η=1.2,β=1.3,r=1.4,q=0.4,p=0.6,k=0.3,m=0.7，得到α和μ對(duì)于平均顧客人數(shù)E[L]的影響。如圖2所示，E[L]隨著μ的增長(zhǎng)而降低；當(dāng)保持μ為定值時(shí)，α的增長(zhǎng)會(huì)導(dǎo)致E[L]的降低。由曲線的傾斜程度可知，α的增大會(huì)導(dǎo)致μ對(duì)E[L]的影響越來越小。這是符合客觀實(shí)際的，災(zāi)難的暴發(fā)，會(huì)導(dǎo)致所有顧客離開。

圖2 α和μ對(duì)E[L]的影響

令λ=1,μ=1.6,η=1.2,r=1.4,q=0.4,p=0.6,k=0.3,m=0.7，得到α和β對(duì)于平均顧客人數(shù)E[L]的影響。如圖3所示，E[L]隨著β的增長(zhǎng)而降低；當(dāng)保持β為定值時(shí)，α的增長(zhǎng)會(huì)導(dǎo)致E[L]的降低。由曲線的傾斜程度可知，α的增大會(huì)導(dǎo)致β對(duì)E[L]的影響越來越大。故當(dāng)災(zāi)難爆發(fā)的概率較高時(shí)，需要提高修理工的到達(dá)速度，以加快系統(tǒng)的維修。

圖3 α和β對(duì)E[L]的影響

令λ=1,η=1.2,β=1.3,r=1.4,α=0.1，q=0.4,p=0.6，得到k和μ對(duì)于平均顧客人數(shù)E[L]的影響。如圖4所示，k趨于0時(shí)，服務(wù)速率越低，E[L]越大；k趨于1時(shí)，服務(wù)速率越低，E[L]越小。故當(dāng)反饋發(fā)生頻率已知時(shí)，需合理選擇服務(wù)速率，以達(dá)到最大的效益。

圖4 k和μ對(duì)E[L]的影響

本部分對(duì)其他帶有災(zāi)難和伯努利機(jī)制的隊(duì)列中已有的服務(wù)效率、災(zāi)難發(fā)生頻率、維修效率進(jìn)行模擬實(shí)驗(yàn)，表明本模型的有效性，在此基礎(chǔ)上對(duì)反饋部分進(jìn)行模擬實(shí)驗(yàn)，得出相應(yīng)建議。若社會(huì)管理者想要利益最大化，在保證工作臺(tái)質(zhì)量和維修效率的基礎(chǔ)上還應(yīng)當(dāng)根據(jù)反饋頻率合理選擇服務(wù)效率。

6 結(jié) 論

本文研究了伯努利機(jī)制下具有災(zāi)難、延遲維修、反饋和休假的單工作臺(tái)隊(duì)列，利用馬氏鏈方法和概率母函數(shù)技術(shù)對(duì)系統(tǒng)中顧客人數(shù)的穩(wěn)態(tài)概率分布進(jìn)行分析，給出若干穩(wěn)態(tài)指標(biāo)，最后利用數(shù)值模擬得出建議。在工業(yè)、互聯(lián)網(wǎng)、通訊和高新科技應(yīng)用中意義重大。本模型還可推廣到多服務(wù)臺(tái)、多階段服務(wù)等繼續(xù)進(jìn)行研究。