程慧慧， 田中連

(華北水利水電大學 數(shù)學與統(tǒng)計學院,河南 鄭州 450046)

0 引言

重試排隊模型是排隊論發(fā)展過程中衍生出的一類重要排隊系統(tǒng)。近年來，具有一個階段服務的一般重試排隊模型得到廣泛的關(guān)注，但在一些分布式系統(tǒng)控制中，服務臺可能分兩個階段進行服務。在第一個階段對傳入的作業(yè)進行初步處理，如果符合某種標準，則進行第二階段的服務。此外，兩階段服務的排隊模型在計算機和通信網(wǎng)絡中也有廣泛的應用。對具有第二階段可選服務的重試排隊模型關(guān)注，KUMAR B K等[1]研究了帶有優(yōu)先權(quán)和兩階段服務的M/G/1重試排隊模型，陳佩樹等[2]研究了具有Bernoulli休假和可選服務的M/G/1重試反饋排隊模型。近年來，ARIVUDAINAMBI D等[3]考慮了二次可選服務和休假的重試排隊，JAIN M等[4]研究了具有兩階段服務、不耐煩顧客和階段性修理的Mx/G/1重試休假排隊，其中第二階段有多重服務可以選擇。除了對連續(xù)時間兩階段重試模型的研究，具有離散時間兩階段重試排隊模型也有一些成果。WANG J等[5]研究了具有啟動失敗和可選服務的Geo/G/1重試排隊模型，WEI C M等[6]討論了具有不耐煩顧客和二次可選服務的離散時間的Geom/G/1重試隊列。

在經(jīng)過長時間的服務后，服務臺可能會出現(xiàn)故障，從而導致啟動失敗，進入修理期。對于具有啟動失敗的重試排隊模型的研究，KUMAR B K等[7]討論了帶有反饋、啟動失敗的M/G/1重試排隊模型的性能指標。高珊等[8]考慮了有啟動失敗和負顧客的M～X/G/1重試排隊模型。WANG J等[9]研究了具有啟動失敗、反饋和準入策略的M～X/G/1重試排隊模型。

本文在啟動失敗和第二階段可選服務的基礎上，引入反饋排隊機制，考慮具有啟動失敗、第二階段可選服務和反饋的M/G/1重試排隊模型。具有反饋機制的重試排隊最早出現(xiàn)在分時操作計算機中。在分時計算機操作系統(tǒng)中，系統(tǒng)任務分成很多時間間隔，如果所需的總處理時間超過間隔的長度之和，信息將反饋到系統(tǒng)中，系統(tǒng)根據(jù)反饋進行下一輪工作，直至達到所需的處理時間。此外，反饋機制在通信系統(tǒng)中也有廣泛的應用。

1 模型描述

2 系統(tǒng)穩(wěn)定狀態(tài)分析

當系統(tǒng)處于穩(wěn)定狀態(tài)時，無論初始的分布是怎樣的，系統(tǒng)將趨于不變的概率分布。在系統(tǒng)穩(wěn)定狀態(tài)的條件下，分析系統(tǒng)穩(wěn)定狀態(tài)的性質(zhì)。

2.1 系統(tǒng)的遍歷性

采用嵌入馬爾科夫鏈的方法對系統(tǒng)穩(wěn)定狀態(tài)條件進行分析。嵌入馬爾科夫鏈方法的關(guān)鍵是嵌入點的選擇。對于模型，選擇嵌入點為顧客服務完成時刻或修理結(jié)束時刻。令{tn；n∈N}為第n個顧客服務完成時刻或修理結(jié)束時刻，C(tn+)為第n個顧客離開后或修理結(jié)束后重試區(qū)域的顧客數(shù)，則Xn={C(tn+),X(tn+)}形成嵌入馬爾科夫鏈。

引理1(Forster準則)[9]一個不可約、非周期的馬爾科夫鏈Xn是遍歷的，如果存在非負函數(shù)f(j)和ε>0，使得均值偏移量xj=E(f(Xn+1)-f(Xn)/Xn=j)是有限的,并且除有限個j外幾乎所有j∈N都有xj<ε。

引理2[10]一個不可約、非周期的馬爾科夫鏈Xn是非遍歷的，如果xj滿足Kaplan條件，xj<∞(j≥0)并且存在自然數(shù)j0∈N，當j≥j0時，有xj≥0。

證明(充分性)顯而易見，{Xn;n≥1}是一個不可約、非周期的馬爾科夫鏈。令f(j)=j，則

2.2 隊長的平穩(wěn)分布

系統(tǒng)在任意時刻t的狀態(tài)可用馬爾科夫過程{C(t),N(t),ξ0(t),ξ1(t),ξ2(t),ξ3(t),t≥0}表示，其中，C(t)表示t時刻系統(tǒng)所處的狀態(tài)，N(t)表示在t時刻重試區(qū)域的顧客數(shù)。當C(t)=0,N(t)>0時，ξ0(t)表示逝去的重試時間；當C(t)=1,N(t)≥0時，ξ1(t)表示正在進行基本服務的顧客已經(jīng)逝去的基本服務時間；當C(t)=2,N(t)≥0時，ξ2(t)表示正在進行可選服務的顧客已經(jīng)逝去的可選服務時間；當C(t)=3，N(t)≥1時，ξ3(t)表示逝去的修理時間。令γ(x),μ(x),ν(x),η(x)分別為重試、基本服務、可選服務和修理的條件完成率函數(shù)，則

令

P0(t)=P{C(t)=0,N(t)=0};

Pn(x,t)dx=P{C(t)=0,N(t)=n,x≤ξ0(t)

Qn(x,t)dx=P{C(t)=1,N(t)=n,x≤ξ1(t)

Rn(x,t)dx=P{C(t)=2,N(t)=n,x≤ξ2(t)

Sn(x,t)dx=P{C(t)=3,N(t)=n,x≤ξ3(t)

根據(jù)對狀態(tài)轉(zhuǎn)移概率動態(tài)分析可得到

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

邊界條件為

(9)

(10)

(11)

(12)

(13)

(14)

正則條件為

(15)

(16)

(17)

(18)

(19)

(20)

平穩(wěn)狀態(tài)重試區(qū)域的隊長分布為

(21)

證明采用概率母函數(shù)的方法求解微分差分方程(1)～(14)。首先定義概率母函數(shù)

在方程(1)～(14)中，令t→∞，即

然后方程(2)～(14)兩邊同時乘zn，并對n求和，可得

(22)

(23)

(24)

(25)

邊界條件為

(26)

(27)

(28)

(29)

解方程(22)～(25)，可得

(30)

(31)

(32)

(33)

將式(30)～(33)代入式(26)～(29)，可得

P(0,z)=(θ1+θ0z)β*(λ(1-z))Q(0,z)+(pz+q)V*(λ(1-z))R(0,z)+
Φ*(λ(1-z))S(0,z)-λP0，

(34)

(35)

R(0,z)=θ2β*(λ(1-z))Q(0,z)，

(36)

(37)

將式(34)～(37)聯(lián)合，可解得P(0,z),Q(0,z),R(0,z)和S(0,z)，并將其代回式(30)～(33)，并對x進行積分，即可得到定理中的(16)～(19)。令z=1，運用洛必達法則，根據(jù)正則條件P0+P(1)+Q(1)+R(1)+S(1)=1，可以得到

P0如式(20)。

平穩(wěn)狀態(tài)重試區(qū)域中隊長的概率母函數(shù)L(z)=P0+P(z)+Q(z)+R(z)+S(z)，即

3 系統(tǒng)的性能指標

除了隊長的分布外，還常用忙期分布、閑期分布和平均隊長作為系統(tǒng)性能指標的測度。

3.1 系統(tǒng)中顧客數(shù)的分布

令K(z)表示系統(tǒng)穩(wěn)定狀態(tài)時顧客總數(shù)的概率母函數(shù)，由于K(z)=P0+P(z)+zQ(z)+zR(z)+S(z)，由(16)～(20)計算可得

(38)

3.2 服務臺繁忙或空閑的概率

服務臺的忙期是從新到達顧客發(fā)現(xiàn)服務臺空閑，成功啟動服務臺開始服務時刻起，到顧客離開服務臺并且重試區(qū)域沒有顧客為止。服務臺忙期的概率H=P(1)+Q(1)，計算可得

相對于忙期分布，服務臺處于空閑狀態(tài)或修理狀態(tài)的概率為

3.3 平均隊長

其中，

F′(1)=αA*(λ)(1-θ0-θ2p),F″(1)=-2αλA*(λ)((θ0+θ2p)β1+θ2pν1),

G″(1)=αλ(2β1(A*(λ)-θ0-θ2p-1)+2θ2ν1(A*(λ)-λβ1-p-1)-λ(β2+θ2ν2))+

其中，

M′(1)=αA*(λ)(θ1+θ2q),M″(1)=2αλA*(λ)((θ1+θ2q)β1+θ2qν1),

N″(1)=αλ(2β1(A*(λ)-θ0-θ2p-1)+2θ2ν1(A*(λ)-λβ1-p-1)-λ(β2+θ2ν2))+

4 隨機分解定理

隨機分解定理是休假排隊系統(tǒng)的重要性質(zhì)，廣泛應用于休假隨機排隊系統(tǒng)中。在休假排隊系統(tǒng)中，任意時刻顧客數(shù)的概率母函數(shù)可以分解為以下兩部分的乘積：一個是無休假系統(tǒng)中處于穩(wěn)定狀態(tài)時顧客數(shù)的概率母函數(shù)；另一個是休假排隊系統(tǒng)中服務臺處于休假狀態(tài)時顧客數(shù)的概率母函數(shù)[13]。

本文考慮的模型屬于無休假的排隊模型，為了研究其隨機分解性質(zhì)，引入廣義休假狀態(tài)的概念。廣義休假期從服務臺完成任意一次服務到成功啟動服務臺，則系統(tǒng)處于廣義休假狀態(tài),即系統(tǒng)處于空閑或修理狀態(tài)。令Π(z)表示無休假、第二階段可選服務和反饋的M/G/1排隊系統(tǒng)穩(wěn)定狀態(tài)時顧客總數(shù)的概率母函數(shù)；χ(z)表示本文所考慮系統(tǒng)處于廣義休假狀態(tài)時顧客總數(shù)的概率母函數(shù)。

定理3K(z)=Π(z)χ(z)。

由(16)式可知，A*(λ)=1，則可得到

根據(jù)式(38)計算可得K(z)=Π(z)χ(z)，故本文所考慮模型符合隨機分解性質(zhì)。

5 結(jié)論

研究具有啟動失敗、第二階段可選服務和反饋的重試排隊模型。在穩(wěn)定狀態(tài)的前提下，求得系統(tǒng)遍歷性的充分必要條件。通過求解微分差分方程得到系統(tǒng)中重試區(qū)域隊長分布，同時得到了系統(tǒng)中顧客總數(shù)、忙時分布和閑時分布等一些指標，最后驗證所研究模型具有隨機分解性質(zhì)。