對服務率可變的T-SPH/M/1/N排隊基于廣義特征值方法的分析?

張宏波,楊憲立,封平華

(河南教育學院數學系，鄭州 450046)

1 引言

眾所周知，PH分布[1]是吸收Markov過程吸收時間的分布，它在隨機模型的分析中有著重要的應用，可參見文獻[1,2]．Shi等[3]把PH分布推廣到了可數狀態吸收M arkov過程的情形，并稱之為SPH分布(離散時間時稱為IPH分布)，推廣后的分布的重要應用可以參見文獻[4]．

本文考慮一種特殊的SPH分布，即在其表示(β,T)中，β=(1,0,0,…)，而

是一個三對角形式的無窮維矩陣，其中c>a>0．我們稱這種特殊形式的分布為T-SPH分布，因而T-SPH分布是可數狀態吸收生滅過程吸收時間的分布．該分布是SPH分布中一個重要的子類，例如，根據定義，經典的M/M/1排隊忙期的分布即是此類分布．另外，與T-SPH分布有關的一些排隊模型，可以參見文獻[5,6]．

現在我們考慮有限T-SPH/M/1/N排隊模型，即假設顧客按照間隔為T-SPH分布的更新過程到達一個服務臺．服務時間獨立同分布，且服從參數為μn的指數分布，這里假設服務率依賴于當前系統中的顧客數n，且μn隨著n的增加而嚴格遞增．另外，我們進一步假設系統中最多容納N個顧客(其中N是一個正整數)，從而一個到達的顧客如果發現系統中有N個顧客，他將離開系統．上述排隊模型具有重要的應用及理論意義．首先，如果系統中排隊的顧客數越多，服務臺的服務速率應越快，以緩解排隊擁擠，因此我們假設μn是n的遞增函數具有一定的現實意義．其次，等待空間有限同樣具有現實意義及應用背景，比如計算機存儲空間有限，停車位有限等都反映為等待空間有限．最后，因為T-SPH分布是M/M/1忙期的分布，所以其LST是無理函數，而PH分布的一個標志特征是其LST是有理函數[7]，所以T-SPH分布不是PH分布，這說明SPH分布類是比連續時間PH分布類嚴格大的一個分布類，因而本文考慮的模型是相應的PH/M/1/N模型[1]的推廣．

具體來說，所考慮的T-SPH/M/1/N排隊模型可以用一個無限水平，有限位相的擬生滅(QBD)過程來描述(參見第2節)[1]．我們知道，這種類型的QBD過程可以用著名的矩陣解析方法來分析，然而在分析時需要求解一個二次矩陣方程的最小非負解[1,2]，這往往是一個困難的問題，特別是對本文所建立的QBD過程，其轉移概率矩陣中的子塊不具有重復的行，求解相應的矩陣方程更為不便．因此本文中，我們用譜展開方法來分析該模型．譜展開方法也稱為廣義特征值方法，關于該方法的討論可參見文獻[8]．它已經應用于許多排隊模型的分析之中，例如文獻[9,10]用該方法討論了M/M/1搶占優先權排隊；文獻[11,12]用該方法討論了串聯排隊模型等．

2 模型描述

對T-SPH/M/1/N排隊，分別用L(t)和J(t)表示時刻t時系統中的顧客數以及服務位相，從而有0≤L(t)≤N．這時{(J(t),L(t)),t≥0}是一個QBD過程，且其狀態空間為

這里為了討論方便，假設位相從0開始編號．顯然，當狀態按字典規則排列時[1]，QBD過程{(J(t),L(t)),t≥0}的無窮小生成元具有如下所示的三對角分塊矩陣形式

其中的子塊均為N+1階方陣，具體形式如下

以及A=a I,C=c I．這里I表示N+1階單位方陣，而

并約定μ0=0．

由著名的飄移性條件容易證明[13]，QBD過程{(J(t),L(t)),t≥0}遍歷的充分必要條件是c>a．因而當c>a時，該過程的平穩分布唯一存在．如果記平穩分布為(π0,π1,…)，其中πn=(πn0,πn1,…,πnN),n=0,1,…是N+1維向量，則它滿足以下方程組

3 廣義特征值問題

方程(2)是一個2階常矩陣系數齊次向量差分方程，其特征矩陣多項式為D(x)=A+x B+x2C，把矩陣A,B和C的具體形式代入后，可得

其中

設x和g分別表示滿足方程gD(x)=0的常數(可能是復數)以及N+1維行向量，它們分別稱為矩陣D(x)的廣義特征值以及與之對應的左特征向量[14]．這時通過直接驗證可知πn=g xn?1是差分方程(2)的一個解．M itrani和Chakka[8]證明了，當QBD過程{(J(t),L(t)),t≥0}遍歷時，特征多項式D(x)恰好有N+1個嚴格位于單位圓內的特征值．如果用x0,x1,…,xN表示這些特征值，并用g0,g1,…,gN表示與之相應的左特征向量，則方程(2)的解具有如下形式

其中αi,i=0,1,…,N是待定常數，它們由(1)和歸一化條件確定．

因此，對QBD過程，其平穩分布的求解問題轉化為計算矩陣D(x)特征值以及與之相應的左特征向量．這種方法文獻中稱為譜展開方法[8]或廣義特征值方法[9,11]．為了求解本文所討論的模型，首先給出下述引理．

引理1如果c>a，則特征矩陣多項式D(x)恰好有N+1個位于(0,1)內的特征根x0,x1,…,xN，其具體形式如下

特別地，．

證明 顯然x和g滿足gD(x)=0的充分必要條件是det D(x)=0．然而因為

所以上述行列式取值為0，如果di(x)=0對某i成立．這也說明為了求特征根，我們只需求解方程di(x)=0,i=0,1,…,N．通過簡單的代數計算，我們可以得到N+1對特征根如下

其中i=0,1,…,N．

容易驗證當c>a時，有xi1∈(0,1),xi2≥ 1，所以如果把xi1記為xi，并注意γ0=a+c，則可得引理的結論．

定理1對由(4)式給出的特征值xi,i=0,1,…,N，如果記其相應的左特征向量為gi=(gi0,gi1,…,giN)，則有

這里規定空的乘積為1．

證明 首先容易驗證，對任意的i=0,1,…,N，方程giD(xi)=0的分量形式為

現在考慮i=0的情形．因為，所以由(6)及(7)式易得g0j=0,j=1,2,…,N，而g00取任意值．然而特征向量不能為0，所以不失一般性，取g00=1．

其次，對任意的i=1,2,…,N，因為dj(xi)當i=j時值為0，而其余情形下值非零，所在(6)式中當j=i時，有

從而gi,i+1=0．再由(6)式中相應于j=i+1,i+2,…,N時的等式可得gij=0,j=i+2,…,N，而gii可取任意值．假設gii=0，則由(6)中其余的等式知gi=0，所以0．仍設gii=1，由此出發，由(6)中相應于j=0,1,…,i?1的等式易得

其中空乘積規定為1．

最后，因為

從而把上式代入方程(8)并做適當的化簡，即得定理的結論．

注1由xi的定義以及定理1證明的后半部分可得

以上關系式在后面將會用到．

注2在方程(6)和(7)中，關于j求和，并注意到μ0=0，可得

現在由xi的定義，當i>0時，上述最后一個等式說明

其中e和e1都是N+1維列向量，其中第一個元素全為1，第二個除了第一個位置元素為1外，其余位置為0．

4 平穩隊長分布

現在分析T-SPH/M/1/N排隊的平穩隊長．對該模型，我們關心的是系統穩態時一個到達的顧客看到的顧客數，用La表示(任意時刻的隊長也可做類似分析，略)．若定義

則(p0,p1,…,pN)表示排隊系統的平穩到達隊長分布，它可以由所考慮的QBD過程的聯合平穩分布確定．

對前述QBD過程，其聯合平穩分布由(3)給出，其中待定常數αi,i=0,1,…,N由方程(1)以及規一化條件確定．如果記

則方程(3)可以改寫為如下所示矩陣形式

其中α =(α1,α2,…,αN)．現在常數(α0,α)可由下述引理給出．

引理2我們有α0=1?ξ．另外，α=(α1,α2,…,αN)滿足下述線性方程組

其中

是一個N階下Hessenberg矩陣，其元素具體形式如下

其中是一個例外．

證明 首先由方程(11)和歸一化條件可得

因而α0=1?x0=1?ξ．

其次，由方程(12)可得π0=(α0,α)G和π1=(α0,α)ΛG，代入方程(1)可得

現在，由G e=e1和(B0+A)e=0出發容易驗證

這說明方程(14)中的第一個方程可以去掉，而且容易驗證其余的方程滿足

其中矩陣H由矩陣GB0+cΛG刪除第一行和第一列后所得到的矩陣．最后，由關系(9)和(10)易得其元素的具體表達式，如引理中所示．

定理2對有限T-SPH/M/1/N排隊，其平穩到達隊長分布{pn,n=0,1,…,N}由下式給出

其中αi由引理2所給出．

證明 令L和J分別表示穩態時系統中的顧客數和服務位相，則一個顧客到達時看到系統中已經有n個顧客的概率為

現在由方程(2)，我們有π0=(α0,α)G，所以

另外，由方程(11)可得

因而由上述最后一個等式以及(16)可得定理結論．

注3對一個有限排隊系統，我們有必要考慮一個到達的顧客被拒絕的概率．在系統穩態時，這一概率顯然為pN，稱為損失概率．對本文考慮的模型，由方程(15)，損失概率為．另外，一個到達的顧客發現系統忙的概率為pB=1?p0．

在前面的討論中，我們對μn所作的唯一假定是它關于系統中顧客數n單調遞增．現在我們討論兩種特殊形式的μn，每種情形下，我們給出平穩隊長的具體表達式，見下面兩個推論，其中假設μ是一個正常數．另外，這兩個推論由(15)式出發經過簡單的計算可得，具體細節此處從略．

推論1當μn=nμ時，平穩到達隊長分布{pn,n=0,1,…,N}由下式給出

推論2當μn=n+μ時，平穩到達隊長分布{pn,n=0,1,…,N}由下式給出

5 數值例子

由前面的分析結果可以給出T-SPH/M/1/N排隊平穩隊長的數值結果．在計算時首先用Gauss消元法求解方程組(13)，然后再應用(15)即可得到平穩隊長．本小節給出兩個數值例子來說明該方法的有效性．

首先考慮參數取值為a=1,c=7以及μn=nμ．其中表1給出了當μ=5,N=19時平穩隊長的數值結果．

表1: 平穩隊長pn的數值結果(情形1)

另外，圖1至圖3分別給出了穩態時系統忙的概率pB，損失概率pN以及平均平穩隊長E(La)隨系統容量N的變化情況．在每種情形下我們考慮了μ取三個不同值：μ=1,3和5．可以看出，pB和E(La)隨著N的增加而遞增而pN關于N遞減．另外，N對損失概率pN的影響較為明顯．

其次，第二個例子考慮參數取值為a=1,c=3和μn=n+μ的情形，先給出當μ=2而N=15時平穩隊長的結果，如表2所示．

對該例，我們還畫出了pN,pB和E(La)隨μ變化的曲線，且每種情形考慮N取三種不同的值，分別如圖5和圖6所示．可以看出，當μ增加時，pN,pB和E(La)都減小．然而，系統容量N對pB和E(La)的影響較小而對損失概率pN的影響較大．

表2: 平穩隊長pn的數值結果(情形2)

圖1:pN隨N的變化曲線

圖2:pB隨N的變化曲線

圖3:E(La)隨N的變化曲線

圖4:pN隨μ的變化曲線

圖5:pB隨μ的變化曲線

圖6:E(La)隨μ的變化曲線

參考文獻：

[1]Neuts M F.Matrix-geometric Solutions in Stochastic Models:an Algorithmic Approach[M].Baltimore:The Johns Hopkins University Press,1981

[2]Breuer L,Baum D.An Introduction to Queueing Theory and Matrix-analytic Methods[M].Netherlands:Springer,2005

[3]Shi D H,Guo J L,Liu L M.On the SPH-distribution class[J].Acta Mathematica Scientia,2005,25B(2):201-214

[4]Alfa A S.Discrete time queues and matrix-analytic methods[J].Sociedad de Estadistica e Investigaci′on TOP,2002,10(2):147-210

[5]Zhang H B,Shi D H.Analysis of two queueing models with explicit rate operators and stationary distributions[J].International Journal of Information and Management Sciences,2011,22(2):177-188

[6]Zhang H B,Shi D H,Hou Z T.Explicit solution for queue length distribution of M/T-SPH/1 queue[J].Asia-Pacific Journal of Operational Research,2014,31(1):1-19

[7]O′Cinneide C A.Characterization of phase-type distributions[J].Stochastic Models,1990,6(1):1-57

[8]Mitrani I,Chakka R.Spectral expansion solution for a class of Markov models:application and comparison with the matrix-geometric method[J].Performance Evaluation,1995,23(3):241-260

[9]Drekic S,Grassmann W K.An eigenvalue approach to analyzing a finite source priority queueing model[J].Annals of Operations Research,2002,112(1-4):139-152

[10]Drekic S,Douglas G W.A preemptive priority queue with balking[J].European Journal of Operational Research,2005,164(2):387-401

[11]Grassmann W K,Drekic S.An analytical solution for a tandem queue with blocking[J].Queueing Systems,2000,36(1-3):221-235

[12]Grassmann W K,Tavakoli J.A tandem queuewith a movable server:an eigenvalue approach[J].SIAM Journal on Matrix Analysis and Applications,2002,24(2):465-474

[13]Latouche G,Ramaswami V.Introduction to Matrix-analytic Methods in Stochastic Modeling[M].Philadelphia:SIAM,1999

[14]Gohberg P,Lancaster P,Rodman L.Matrix Polynomials[M].New York:Academic Press,1982