帶有工作故障的M/M/1重試排隊系統(tǒng)的性能分析

葉晴晴,陳鈺

(南京信息工程大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院,南京 210044)

在現(xiàn)實生活中,排隊系統(tǒng)的服務(wù)臺長期工作導(dǎo)致故障的出現(xiàn),傳統(tǒng)穩(wěn)定可靠的排隊模型已經(jīng)不能說明現(xiàn)實情況.2012年,文獻(xiàn)[1]首次提出工作故障策略,即服務(wù)臺在正常工作狀態(tài)下可能發(fā)生故障,發(fā)生故障后服務(wù)臺立刻進(jìn)行修理,并且以較低的服務(wù)速率繼續(xù)為顧客服務(wù).2018年,文獻(xiàn)[2]討論了具有工作故障的MAP/M/1隊列,采用矩陣幾何解法求出系統(tǒng)的穩(wěn)態(tài)隊長,并且給出了一個遞推公式來獲得平均逗留時間的近似值.2021年,文獻(xiàn)[3]考慮了一個具有工作故障和延遲工作休假的M/M/1隊列,采用廣義特征值法推導(dǎo)出系統(tǒng)的穩(wěn)態(tài)概率分布與若干性能指標(biāo).同年,文獻(xiàn)[4]研究了完全故障且可中斷啟動時間M/M/1排隊模型,基于“收益-成本”效用函數(shù),研究顧客進(jìn)隊的個體最優(yōu)策略,并且通過解平衡方程進(jìn)而分析統(tǒng)籌全局的社會最優(yōu)收益．

為了避免服務(wù)器在正常工作狀況下出現(xiàn)數(shù)據(jù)的擁堵現(xiàn)象,文獻(xiàn)[5]首次發(fā)表了有關(guān)重試排隊研究的文章.當(dāng)?shù)竭_(dá)的顧客發(fā)現(xiàn)服務(wù)臺處于繁忙狀態(tài)且暫時不能提供服務(wù)時,顧客便會進(jìn)入一個重試空間,在一段隨機(jī)時間后顧客再次嘗試直至服務(wù)臺可以進(jìn)行服務(wù),這便是重試排隊系統(tǒng).近年來,重試排隊系統(tǒng)研究引起了眾多學(xué)者的關(guān)注,已經(jīng)廣泛應(yīng)用于通信網(wǎng)絡(luò)和計算機(jī)網(wǎng)絡(luò),解決了許多實際問題.2019年,文獻(xiàn)[6]研究了一類帶休假的M/M/c阻塞重試排隊問題,利用矩陣幾何解法導(dǎo)出了系統(tǒng)的穩(wěn)態(tài)隊長以及一些性能指標(biāo).2020年,文獻(xiàn)[7]考慮了一類具有一般重試次數(shù)和單工作休假的M/G/1重試隊列,使用補(bǔ)充變量方法處理了服務(wù)器狀態(tài)和軌道中的客戶數(shù)的生成函數(shù),導(dǎo)出了一些系統(tǒng)主要的性能指標(biāo).

基于以上分析,本文把重試排隊與工作故障策略結(jié)合,考慮帶有工作故障的M/M/1重試排隊模型,該模型可應(yīng)用于鐵路12306、大麥網(wǎng)、景區(qū)票務(wù)管理系統(tǒng)等網(wǎng)上購票系統(tǒng).考慮一個擁有無限顧客容量的購票系統(tǒng),當(dāng)顧客進(jìn)入購票系統(tǒng)進(jìn)行購票請求時,如果系統(tǒng)處于繁忙狀態(tài),則顧客需要進(jìn)行刷新頁面來請求購票; 如果系統(tǒng)處于空閑狀態(tài),則該顧客可以直接進(jìn)行購票,但是在購票過程中系統(tǒng)可能出現(xiàn)故障,在故障的狀態(tài)下購票系統(tǒng)并不會完全崩潰,仍然可以為顧客提供購票服務(wù),但是此時系統(tǒng)的搶票速率要低于正常購票狀態(tài)下的速率.經(jīng)過一段時間的較低速率的搶票后,購票系統(tǒng)經(jīng)過自動維修便可以調(diào)整為正常工作狀態(tài).顧客購票成功后便可退出購票軟件.這種網(wǎng)上購票系統(tǒng)由于系統(tǒng)繁忙而進(jìn)行的刷新頁面與重試排隊模型相對應(yīng),購票系統(tǒng)出現(xiàn)故障的情況與工作故障模型相對應(yīng).

本文剩余部分的結(jié)構(gòu)如下:第一部分詳細(xì)描述了帶有工作故障的M/M/1重試排隊系統(tǒng);第二部分證明該排隊系統(tǒng)的平穩(wěn)條件,并得到重試空間中的顧客數(shù)與服務(wù)臺狀態(tài)的穩(wěn)態(tài)聯(lián)合概率分布的顯示解; 第三部分推導(dǎo)出該排隊系統(tǒng)的幾個性能指標(biāo); 第四部分通過數(shù)值實驗討論了系統(tǒng)參數(shù)對系統(tǒng)性能指標(biāo)的影響,并且對該模型進(jìn)行了廣義特征值法和矩陣幾何解法的比較.

1 模型描述

(1)顧客的到達(dá)服從參數(shù)為λ的泊松過程.

(2)排隊系統(tǒng)在正常工作期,服務(wù)臺的服務(wù)時間服從參數(shù)為μ的指數(shù)分布,服務(wù)臺在正常工作的過程中隨時可能發(fā)生故障,故障的到達(dá)是參數(shù)為α的泊松過程.一旦服務(wù)臺出現(xiàn)故障,便立刻進(jìn)行維修,維修時間服從參數(shù)為β的指數(shù)分布,服務(wù)臺在維修期間并沒有完全停止服務(wù),而是以較低的服務(wù)速率η(η<μ)繼續(xù)提供服務(wù).

(3)顧客到達(dá)系統(tǒng)時,如果服務(wù)臺處于空閑狀態(tài),則立刻為該顧客提供服務(wù).如果服務(wù)臺處于繁忙狀態(tài),則顧客進(jìn)入重試空間等待重試.重試空間發(fā)出服務(wù)請求的過程是參數(shù)為θ的泊松過程,即系統(tǒng)采取常數(shù)重試策略.

(4)假設(shè)顧客的到達(dá)間隔時間、服務(wù)臺故障的到達(dá)間隔時間、重試的間隔時間、正常工作期服務(wù)時間、工作故障期服務(wù)時間和服務(wù)臺維修時間相互獨立.服務(wù)順序為先來先服務(wù)(FCFS),重試空間的容量是無限的.

帶有工作故障的M/M/1重試排隊系統(tǒng)在任意時刻t可用2個隨機(jī)變量進(jìn)行描述:N(t)表示t時刻重試空間中的顧客數(shù),I(t)表示t時刻服務(wù)臺所處狀態(tài)且I(t)=0表示服務(wù)臺處于工作故障狀態(tài)且空閑,I(t)=1表示服務(wù)臺處于工作故障狀態(tài)且繁忙,I(t)=2表示服務(wù)臺處于正常工作狀態(tài)且空閑,I(t)=3表示服務(wù)臺處于正常工作狀態(tài)且繁忙.該隨機(jī)過程{(N(t),I(t)),t≥0}是一個二維的連續(xù)時間馬爾科夫過程,狀態(tài)空間為Ω={(k,i),k≥0,i=0,1,2,3},狀態(tài)轉(zhuǎn)移圖見圖1.

按照字典順序排列,該連續(xù)時間馬爾科夫過程{(N(t),I(t)),t≥0}的無窮小生成元可表示為

(1)

其中,

2 穩(wěn)態(tài)分析

引理1連續(xù)時間馬爾科夫過程{(N(t),I(t)),t≥0}的穩(wěn)態(tài)條件為:

(2)

π*Ce<π*Be,

(3)

(4)

(5)

(6)

(7)

(8)

當(dāng)穩(wěn)態(tài)條件成立時,隨機(jī)過程{(N(t),I(t)),t≥0}達(dá)到平穩(wěn)狀態(tài),定義重試空間中的顧客數(shù)與服務(wù)臺狀態(tài)的穩(wěn)態(tài)聯(lián)合概率分布為

(9)

引入穩(wěn)態(tài)概率向量為π=(π0,π1,…,πk,…),其中πk(k≥0)為4維行向量.根據(jù)矩陣Q得到平穩(wěn)方程

π0A0+π1B=0,

(10)

πk-1C+πkA+πk+1B=0,k≥1.

(11)

方程(11)所滿足的特征矩陣為

(12)

Ψ(x)對應(yīng)的特征行列式為:det[Ψ(x)]=x2·(ax4+bx3+cx2+dx+h),其中

a=θ2ημ,b=-θ(ηl1+μ2+αβη),h=λ2(λ+θ)(λ+β+θ),

c=λθη(λ+θ)+λθμ(λ+β+θ)-αβ[(λ+β+θ)(λ+θ)+λη]+l1l2,

d=-λ(λ+θ)[(λ+β+θ)(λ+β+η)-λη]-λ(λ+β+θ)[(λ+θ)(λ+μ+α)-λμ],

l1=(λ+θ)(λ+μ+α)-λμ,l2=(λ+β+θ)(λ+β+η)-λη.

特征方程det[Ψ(x)]=0為一元六次方程,其中有2個零特征值.對于一元四次方程ax4+bx3+cx2+dx+h=0的求解可參閱文獻(xiàn)[9],得到以下4個非零特征值

其中

δ0=c2-3bd+12ah,δ1=2c2-9bcd+27b2h+27ad2-72ach,

根據(jù)文獻(xiàn)[10]的命題2,如果排隊系統(tǒng)處于平穩(wěn)狀態(tài),Ψ(x)有且僅有4個特征值嚴(yán)格處于單位圓盤中.注意到Ψ(x)有2個零特征值,故設(shè)在單位圓盤中2個非零特征值為r1和r2,對應(yīng)的左特征向量為γ1和γ2.根據(jù)方程γnΨ(rn)=0,n=1,2,得到非零特征值r1和r2的左特征向量為

γn=(1,f1,f2(rn),f3(rn)),n=1,2,

(13)

其中,

系統(tǒng)的穩(wěn)態(tài)概率向量πk(k≥0)可表示為特征值r1和r2與其對應(yīng)的左特征向量γ1和γ2的線性組合

(14)

其中t1和t2是待定系數(shù).注意到π0A0+π1B=0等價于

(λ+β)π00=ηπ01,

(15)

(λ+β+η)π01=λπ00+απ03+θπ10,

(16)

λπ02=βπ00+μπ03,

(17)

(λ+μ+θ)π03=βπ00+λπ02+θπ12.

(18)

(19)

3 性能指標(biāo)

本部分基于上述理論結(jié)果,分析系統(tǒng)的各項性能指標(biāo)如下:

(1)重試空間的平均顧客數(shù)為E(N):

(20)

其中e=(1,1,1,1)T.

(2)重試空間中沒有顧客的概率為P0:

P0=π0e=(t1γ1+t2γ2)e.

(21)

(3)系統(tǒng)服務(wù)臺處于空閑和繁忙狀態(tài)的概率為PF和PB:

(22)

其中e1=(1,0,1,0)T,e2=(0,1,0,1)T.

(4)系統(tǒng)服務(wù)臺處于正常工作和工作故障狀態(tài)的概率為PN和PW:

(23)

其中e3=(0,0,1,1)T,e4=(1,1,0,0)T.

(5)任意顧客的平均逗留時間E(W).

得到如下遞歸關(guān)系:

(24)

(25)

(26)

(27)

(28)

(29)

(30)

(31)

(32)

任意顧客的平均逗留時間為

(33)

對于式(33)的計算本文采用自動微分算法,具體原理可見文獻(xiàn)[12].其實現(xiàn)可在MATLAB平臺下,利用ADMAT自動微分工具將作為輸入變量,通過調(diào)用函數(shù)在計算函數(shù)值的同時實現(xiàn)導(dǎo)數(shù)值的自動計算.任意顧客的平均逗留時間E(W)的具體計算過程可見表1中的算法1.

表1 計算任意顧客的平均逗留時間E(W)

4 數(shù)值實驗

4.1 參數(shù)的靈敏度分析

基于以上研究所獲得的系統(tǒng)穩(wěn)態(tài)性能指標(biāo),本部分進(jìn)行數(shù)值實驗來說明系統(tǒng)參數(shù)對這些性能指標(biāo)的影響.每個數(shù)值實驗的參數(shù)值選擇需滿足引理1中連續(xù)時間馬爾科夫過程{(N(t),I(t)),t≥0}的穩(wěn)態(tài)條件.

圖2至圖5假設(shè)系統(tǒng)參數(shù)為λ=1.5,θ=4,μ=2.5,η=1.6,α=0.5,β=2,繪制重試空間中沒有顧客的概率P0,服務(wù)臺空閑的概率PF以及服務(wù)臺處于工作故障狀態(tài)的概率PW分別隨參數(shù)μ,η,θ和β的變化曲線.圖2表明:P0和PF隨μ的增大而增大,PW隨μ的增大而減小; 圖3表明:P0,PF和PW隨η的增大而增大; 圖4表明:P0隨θ的增大而增大,PF和PW隨θ的增大而緩慢減小; 圖5表明:P0,PF和PW隨β的增大而減小.故從現(xiàn)實排隊系統(tǒng)管理者的角度來考慮,系統(tǒng)可以通過提高服務(wù)臺在正常工作狀態(tài)的服務(wù)速率,并加快對故障服務(wù)臺的維修速率,以此降低服務(wù)臺發(fā)生故障的概率,使服務(wù)臺得到最有效的使用.其次,增大服務(wù)臺在正常工作狀態(tài)與維修狀態(tài)下的服務(wù)速率,能夠有效緩解重試排隊系統(tǒng)的擁塞現(xiàn)象.

圖6至圖9假設(shè)系統(tǒng)參數(shù)為λ=1.5,θ=4,μ=2.5,η=1.6,α=0.5,β=2,繪制重試空間中的平均顧客數(shù)E(N)和任意顧客的平均逗留時間E(W)隨參數(shù)λ,μ,θ和β的變化曲線.圖6和圖7表明:β分別取2.0,2.5,3.0,改變μ的值,E(N)和E(W)隨μ的增大而減小,其中當(dāng)μ增大到某一固定值時,E(N)趨近于0.當(dāng)μ一定時,E(N)和E(W)隨β的增大而減小.圖8和圖9表明:θ分別取6,8,10,改變λ的值,E(N)和E(W)隨λ的增大而增大.當(dāng)λ一定時,E(N)和E(W)隨θ的增大而減小.故從排隊系統(tǒng)管理者的角度來考慮,系統(tǒng)的顧客量過大會導(dǎo)致隊列擁擠,新到達(dá)顧客要想接受服務(wù)需要等待較長的時間.對此管理者可做出提高服務(wù)臺正常工作期的服務(wù)速率,加快對故障服務(wù)臺的維修以及增大重試空間的重試率等策略來緩解隊列的擁塞現(xiàn)象,以此提高排隊系統(tǒng)整體的服務(wù)質(zhì)量.

4.2 矩陣幾何解法

20世紀(jì),文獻(xiàn)[8]對結(jié)構(gòu)矩陣分析方法進(jìn)行了系統(tǒng)的研究.隨后,文獻(xiàn)[13]中提到的矩陣幾何解的方法被引入到GI/M/1休假排隊的研究,將矩陣幾何解從數(shù)值形式推廣到矩陣的形式.

根據(jù)Q矩陣的特殊結(jié)構(gòu),本文研究的連續(xù)時間馬爾科夫過程{(N(t),I(t)),t≥0}為擬生滅過程,對該過程也可運用矩陣幾何解法進(jìn)行分析.首先需要求得二次矩陣方程R2B+RA+C=0的最小非負(fù)解R,由于A矩陣的結(jié)構(gòu)不能得到R的精確值,為此通過迭代公式R[n+1]=-(R2[n]B+C)A-1在MATLAB軟件中得到矩陣R的近似值.利用矩陣幾何解法可將系統(tǒng)的穩(wěn)態(tài)概率向量表示為πk=π0Rk,k≥0,其中π0根據(jù)矩陣方程π0(A0+RB)=0和歸一化條件π0(I-R)-1e=1確定,其中I為4階單位矩陣,e=(1,1,1,1)T.重試空間的平均顧客數(shù)可表示為E(N)=π0R[(I-R)-1]2e.

對于本文研究的帶有工作故障的M/M/1重試排隊系統(tǒng),設(shè)定幾組不同的參數(shù)值,把采用廣義特征值法和矩陣幾何解法得到的重試空間的平均顧客數(shù)分別記為E(N1)和E(N2),所有參數(shù)值的選擇滿足引理1中連續(xù)時間馬爾科夫過程{(N(t),I(t)),t≥0}的穩(wěn)態(tài)條件,比較結(jié)果可見表2.

表2 廣義特征值法和矩陣幾何解法的重試空間平均顧客數(shù)E(N)的比較

通過表2中進(jìn)行的5組數(shù)值實驗對E(N1)和E(N2)進(jìn)行比較得到:采用廣義特征值法與矩陣幾何解法得到的重試空間的平均顧客數(shù)的結(jié)果幾乎一致.相比矩陣幾何解法,本文采用的廣義特征值法能夠得到重試空間中的顧客數(shù)與服務(wù)臺狀態(tài)的穩(wěn)態(tài)聯(lián)合概率分布πk(k≥0)的顯示解,具有更高的實用性.

5 結(jié) 論

本文研究了帶有工作故障的M/M/1重試排隊系統(tǒng),通過工作故障策略和重試排隊模型的結(jié)合,考慮二維的連續(xù)時間馬爾科夫過程.基于廣義特征值法,將重試空間中的顧客數(shù)與服務(wù)臺狀態(tài)的穩(wěn)態(tài)聯(lián)合概率分布表示為特征值與特征向量的線性組合形式,并得到了重試空間中的平均顧客數(shù)與任意顧客的平均逗留時間等相關(guān)性能指標(biāo),通過數(shù)值例子討論了系統(tǒng)參數(shù)對系統(tǒng)性能指標(biāo)的影響.