具有多重休假和兩階段服務(wù)的MX/G/1重試排隊系統(tǒng)

程慧慧, 田中連

(華北水利水電大學數(shù)學與統(tǒng)計學院， 鄭州 450045)

很多學者對具有Bernoulli單重休假排隊系統(tǒng)進行研究, 而對于具有多重休假的排隊系統(tǒng)研究較少。 多重休假最初由Levy等[1]提出, 隨后得到廣泛發(fā)展。原小娟等[2]在具有啟動時間的二次多選擇服務(wù)M/G/1排隊基礎(chǔ)上,引入了空竭服務(wù)、多重休假策略,即當系統(tǒng)為空時, 服務(wù)臺進行一次隨機休假, 若休假結(jié)束時系統(tǒng)中仍沒有顧客排隊, 服務(wù)臺將繼續(xù)進行下一次隨機休假, 直到某次休假結(jié)束時系統(tǒng)中有顧客排隊。 Kumar等[3]將多重休假和Bernoulli休假相結(jié)合, 進一步研究了具有啟動失敗和Bernoulli多重休假的MX/G/1重試排隊系統(tǒng)的性能指標。 賀靈悅等[4]把啟動時間引進到多重休假和系統(tǒng)采取Min(N,V)策略控制的M/G/1排隊系統(tǒng)中, 討論了系統(tǒng)隊長的瞬態(tài)分布和穩(wěn)態(tài)分布。 Rajadurai等[5]引入了多重工作休假的概念, 討論多重工作休假策略下具有不耐煩顧客和反饋的M/G/1重試排隊的重要性能。 Xu等[6]將多重休假運用到多服務(wù)臺的排隊系統(tǒng)中,分析了具有多重休假和不耐煩顧客的M/M/2排隊系統(tǒng)隊長的分布。

對于具有兩階段服務(wù)的排隊系統(tǒng), Kumar等[7]將兩階段服務(wù)策略擴展到重試排隊系統(tǒng)中,研究帶有搶占優(yōu)先權(quán)和兩階段的服務(wù)的M/G/1重試排隊模型的穩(wěn)態(tài)分布。朱翼雋等[8]也對此類系統(tǒng)進行研究。 后來, Wang等[9]進一步研究了具有二次多選擇服務(wù)的重試排隊系統(tǒng), 推廣了具有二次單選擇的重試排隊系統(tǒng)。 近年來, Wei等[10]采用嵌入馬氏鏈的方法研究了具有二次可選服務(wù)和不耐煩顧客的離散時間Geom/G/1重試排隊系統(tǒng)的系統(tǒng)性能。 Varalakshmi等[11]在兩階段服務(wù)的基礎(chǔ)上, 將即時反饋和G-隊列的概念相結(jié)合,采用補充變量和矩陣幾何解的方法研究了系統(tǒng)穩(wěn)定狀態(tài)的概率分布。 徐秀麗等[12]在M/M/1多重休假排隊驅(qū)動系統(tǒng)的基礎(chǔ)上引入可選服務(wù), 采用擬生滅過程探討第二次服務(wù)可選的M/M/1多重休假驅(qū)動系統(tǒng)的流排隊系統(tǒng)的性能。

近年來,很多學者對兩階段服務(wù)的重試排隊模型進行研究,但是沒有文獻研究顧客批量到達、多重休假和二次多選擇服務(wù)的重試排隊模型。 現(xiàn)在兩階段服務(wù)的基礎(chǔ)上, 引入啟動時間和多重休假策略, 考慮了具有啟動時間、多重休假和兩階段服務(wù)的MX/G/1重試排隊系統(tǒng)。 采用嵌入馬爾科夫鏈的方法和補充變量法對系統(tǒng)穩(wěn)定狀態(tài)進行分析。

1 模型簡介

1.1 到達過程

1.2 重試過程

假設(shè)系統(tǒng)中無等待區(qū)域。 如果批次到達的顧客發(fā)現(xiàn)服務(wù)臺空閑, 則其中一個顧客立即進入第一階段的服務(wù)。 如果顧客到達時發(fā)現(xiàn)服務(wù)臺正在啟動或服務(wù)狀態(tài),則該批次的所有顧客都進入到重試區(qū)域進行排隊。 假設(shè)重試只發(fā)生在服務(wù)臺空閑時刻, 并且只有隊首的顧客允許進行重試。 相鄰重試時間之間相互獨立且具有相同的分布函數(shù)A(x), 相應(yīng)概率密度函數(shù)為a(x), Laplace-Stieltjes變換(LS變換)為A*(u)。

1.3 服務(wù)過程

1.4 休假過程

當一次服務(wù)結(jié)束時, 服務(wù)臺如文獻[3]中描述的Bernoulli休假策略進行休假。 服務(wù)臺或以概率q進行一次休假, 或以概率p(p=1-q)等待服務(wù)下一個顧客。 當服務(wù)臺完成一次服務(wù)時, 若重試區(qū)域為空, 則服務(wù)臺進行一次隨機休假。 休假時間獨立同分布于函數(shù)V(x), 設(shè)其密度函數(shù)為v(x), LS變換為V*(u), 前兩階矩為v1、v2。 當重試區(qū)域沒有顧客排隊時, 系統(tǒng)總在休假。 如果休假結(jié)束時, 重試區(qū)域仍為空, 則服務(wù)臺繼續(xù)進行下一次隨機休假, 直到某次休假結(jié)束時, 發(fā)現(xiàn)重試區(qū)域有顧客在排隊, 則立即結(jié)束休假進入服務(wù)狀態(tài)。

1.5 啟動過程

當服務(wù)臺休假結(jié)束后, 需要一段時間進行啟動。 相鄰啟動時間之間相互獨立并且服從分布函數(shù)D(x), 概率密度函數(shù)為d(x), 其LS變換為D*(x), 第一、二階原點矩為d1、d2。

2 系統(tǒng)穩(wěn)定的條件

采用嵌入馬爾科夫鏈的方法對系統(tǒng)穩(wěn)定狀態(tài)條件進行分析。令{tn,n∈N}表示第n個顧客服務(wù)完成時刻, 或第n次休假結(jié)束時刻, 或啟動終止時刻,C(t)表示服務(wù)臺的狀態(tài),N(t)為重試區(qū)域隊長,則Xn={C(tn+),N(tn+)}是狀態(tài)空間S={1,2,3,4}×{0,1,2,…}∪{(0,0)}上的嵌入馬爾科夫鏈。

定理1嵌入馬爾科夫鏈{Xn,n>0}是遍歷的充要條件為

下面證明必要性。 文獻[13]中定理1給出了馬爾科夫鏈的非遍歷性條件, 即如果序列{Xn}(n≥0)滿足Kaplan條件,xj<, 并且存在N使得xj≥0(j≥N), 那么{Xn}(n≥0)是非遍歷的。 記P=[pij]為一步轉(zhuǎn)移概率矩陣, 由于存在整數(shù)k, 當j0)時,pij=0, 根據(jù)文獻[13]中定理3知, Kaplan條件滿足。 所以不等式保證了馬爾科夫鏈{Xn,n>0}的非遍歷性。 則由{Xn,n>0}遍歷性得

3 穩(wěn)定狀態(tài)概率分布

利用已過時間作為補充變量,建立一個馬爾科夫模型,對排隊系統(tǒng)穩(wěn)定狀態(tài)性能進行分析。

令t→, 則：

采用補充變量法對系統(tǒng)進行分析, 可得到以下的微分方程：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

n≥1

(9)

邊界條件為

(10)

(11)

(12)

(13)

(14)

(15)

(16)

正則條件為

(17)

為了求解微分方程, 定義下列概率母函數(shù):

定理2在平穩(wěn)狀態(tài)下,Xn={C(tn),N(tn)}有以下的概率分布：

(18)

Q(0)(x,z)=

[1-B0(x)]exp{-λ[1-C(z)]x}

(19)

S0(0)[1-Bk(x)]×

exp{-λ[1-C(z)]x}

(20)

D(x)]exp{-λ[1-C(z)]x}

(21)

S(x,z)={z[p+qV*(λ)]-{p+qD*[λ-

S0(0)[1-V(x)]exp{-λ[1-C(z)]x}

(22)

證明在等式(1)～式(16)兩邊同時乘以zn,并對n求和可得到：

(23)

μ0(x)}Q(0)(x,z)=0

(24)

μk(x)}Q(k)(x,z)=0

(25)

(26)

(27)

邊界條件可變?yōu)?/p>

(28)

(29)

(30)

(31)

(32)

解式(23)～式(27)可得到：

P(x,z)=P(0,z)[1-A(x)]exp{-λx}

(33)

Q(0)(x,z)=Q(0)(0,z)[1-B0(x)]×

exp{-λ[1-C(z)]x}

(34)

Q(k)(x,z)=Q(k)(0,z)[1-Bk(x)]×

exp{-λ[1-C(z)]x}

(35)

R(x,z)=R(0,z)[1-D(x)]exp{-

λ[1-C(z)]x}

(36)

S(x,z)=S(0,z)[1-V(x)]exp{-

λ[1-C(z)]x}

(37)

從式(8)求解得到：

兩邊同時乘以η(x)并對x進行積分,有：

(38)

將等式(33)～式(37)代入式(28)～式(32)中, 整理可得到定理2。

(39)

{λ[1-C(z)]H(z)})S0(0)

(40)

λC(z)]}{C(z)+[1-

C(z)]H(z)})S0(0)

(41)

λC(z)][p+qV*(λ)]-V*(λ)}-

{λ[1-C(z)]H(z)})S0(0)

(42)

qV*(λ)]-{p+qD*[λ-

C(z)]H(z)})S0(0)

(43)

V*(λ)]d1+[p+qV*(λ)]v1}

(44)

對定理2中式(18)～式(22)分別進行上述積分,即可得到定理3。

4 系統(tǒng)相關(guān)性能指標

推論1(1)系統(tǒng)中顧客數(shù)的概率母函數(shù)為

(2)重試區(qū)域的顧客數(shù)的概率母函數(shù)為

推論2在平穩(wěn)性條件下, 可得到以下的系統(tǒng)相關(guān)指標：

(1)服務(wù)臺處于空閑狀態(tài)但系統(tǒng)不為空的概率為

(2)服務(wù)臺處于繁忙狀態(tài)的概率為

(3)系統(tǒng)處于啟動狀態(tài)的概率為

V*(λ)]d1+[p+qV*(λ)]v1}+

(4)系統(tǒng)處于休假狀態(tài)的概率為

V*(λ)]d1+[p+qV*(λ)]v1}-

Ls=K′(1)=

Lq=L′(1)=

其中：

[p+qV*(λ)]v1};

5 數(shù)值分析

利用MATLAB通過數(shù)值計算, 說明參數(shù)對重試區(qū)域顧客數(shù)的影響。

假設(shè)休假時間和服務(wù)時間都服從指數(shù)分布, 為了使分析更具有一般性, 在重試時間服從以下3種分布。

(1)指數(shù)分布：y=ηe-ηx。

(2)埃爾朗分布：y=η2xe-ηx。

(3)超指數(shù)分布：y=cηe-ηx+(1-c)η2e-η2x。

在服從這3種情況下進行分析, 選擇適當?shù)膮?shù), 在滿足定理1的條件下,可得到結(jié)果如圖1、圖2所示。

圖1 重試區(qū)域平均隊長(Lq)隨概率(θ0)變化圖

圖2 重試區(qū)域平均隊長(Lq)隨休假概率(q)變化圖

圖1表示重試區(qū)域平均隊長隨著只接受第一階段服務(wù)概率θ0的變化情況,從圖1中可以看出：重試區(qū)域中顧客平均隊長隨著只接受第一階段服務(wù)的概率θ0的增加而減少。 隨著只接受第一階段服務(wù)后離開顧客的比率增加, 則接受第二階段服務(wù)的顧客減少,從而重試區(qū)域排隊顧客也相應(yīng)減少, 這與實際生活中相符合。

圖2表示重試區(qū)域平均顧客數(shù)隨休假概率變化情況, 重試區(qū)域平均隊長隨著休假概率q的增加而增加。 隨著休假概率q的增加,新到達顧客發(fā)現(xiàn)服務(wù)臺休假,從而進入重試區(qū)域的比率也增加,從而重試區(qū)域顧客平均隊長增加, 實際中也是如此。

6 隨機分解

隨機分解是休假排隊系統(tǒng)的重要研究方法。 休假排隊系統(tǒng)中的穩(wěn)態(tài)指標可以分解為經(jīng)典無休假系統(tǒng)中的相應(yīng)指標與休假導致的附加指標之和的形式[15]。 令Π(z)為具有兩階段服務(wù)的MX/G/1排隊系統(tǒng)中顧客數(shù)的概率母函數(shù)(平穩(wěn)狀態(tài)下), 則由文獻[7]可知：

引入廣義休假的概念, 將重試時間、休假時間和啟動時間作為廣義休假時間, 也就是廣義休假時間從一個顧客服務(wù)結(jié)束開始到下一次服務(wù)開始。令χ(z)表示在廣義休假狀態(tài)下, 任意時刻系統(tǒng)中顧客數(shù)的概率母函數(shù), 則

因此可計算出：

λC(z)]S0(0){C(z)+[1-

由推論1可知：

因此可得到K(z)=Π(z)χ(z)。

7 結(jié)論

利用嵌入馬爾科夫鏈和補充變量的方法, 得到了系統(tǒng)穩(wěn)定狀態(tài)存在的條件, 同時給出了穩(wěn)定狀態(tài)時的概率分布和相關(guān)系統(tǒng)性能指標。 引入廣義休假的概念, 證明了系統(tǒng)的隨機分解性。