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

葉晴晴,陳鈺

(南京信息工程大學 數學與統計學院,南京 210044)

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

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

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

本文剩余部分的結構如下:第一部分詳細描述了帶有工作故障的M/M/1重試排隊系統;第二部分證明該排隊系統的平穩條件,并得到重試空間中的顧客數與服務臺狀態的穩態聯合概率分布的顯示解; 第三部分推導出該排隊系統的幾個性能指標; 第四部分通過數值實驗討論了系統參數對系統性能指標的影響,并且對該模型進行了廣義特征值法和矩陣幾何解法的比較.

1 模型描述

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

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

(3)顧客到達系統時,如果服務臺處于空閑狀態,則立刻為該顧客提供服務.如果服務臺處于繁忙狀態,則顧客進入重試空間等待重試.重試空間發出服務請求的過程是參數為θ的泊松過程,即系統采取常數重試策略.

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

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

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

(1)

其中,

2 穩態分析

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

(2)

π*Ce<π*Be,

(3)

(4)

(5)

(6)

(7)

(8)

當穩態條件成立時,隨機過程{(N(t),I(t)),t≥0}達到平穩狀態,定義重試空間中的顧客數與服務臺狀態的穩態聯合概率分布為

(9)

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

π0A0+π1B=0,

(10)

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

(11)

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

(12)

Ψ(x)對應的特征行列式為: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的求解可參閱文獻[9],得到以下4個非零特征值

其中

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

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

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

(13)

其中,

系統的穩態概率向量πk(k≥0)可表示為特征值r1和r2與其對應的左特征向量γ1和γ2的線性組合

(14)

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

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

(15)

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

(16)

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

(17)

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

(18)

(19)

3 性能指標

本部分基于上述理論結果,分析系統的各項性能指標如下:

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

(20)

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

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

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

(21)

(3)系統服務臺處于空閑和繁忙狀態的概率為PF和PB:

(22)

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

(4)系統服務臺處于正常工作和工作故障狀態的概率為PN和PW:

(23)

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

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

得到如下遞歸關系:

(24)

(25)

(26)

(27)

(28)

(29)

(30)

(31)

(32)

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

(33)

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

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

4 數值實驗

4.1 參數的靈敏度分析

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

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

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

4.2 矩陣幾何解法

20世紀,文獻[8]對結構矩陣分析方法進行了系統的研究.隨后,文獻[13]中提到的矩陣幾何解的方法被引入到GI/M/1休假排隊的研究,將矩陣幾何解從數值形式推廣到矩陣的形式.

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

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

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

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

5 結 論

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