基于GI/M/1 型Markov 過程的Geo/Geo/1多重工作休假排隊系統分析

張宏波, 彭培讓

(河南財政金融學院統計與數學學院，鄭州 450046)

1 引言

離散時間休假排隊模型由于在計算機系統、控制系統、通訊系統等領域有重要的潛在應用價值，因而得到了大量的研究.詳細的介紹可以參見文獻[1—5].

Servi 和Finn[6]最先對M/M/1 排隊引進了工作休假策略.在這種情形下，與普通休假不同，服務臺不是完全停止工作，而是為在休假期間到達系統的顧客以較低的服務率提供服務.隨后，各種含有工作休假策略的排隊模型得到了大量的研究.特別是針對離散時間排隊情形，例如，Li 等[7]研究了具有多重工作休假以及休假中斷的GI/Geo/1 排隊；Tian 等[8]研究了Geo/Geo/1 多重工作休假排隊；關于多重工作休假的Geo/G/1 排隊的詳盡分析可參見文獻[4].另外，Li 等[5]還研究了批到達的Geo/G/1 多重工作休假排隊系統.

在Tian 等[8]對Geo/Geo/1 多重工作休假排隊模型的研究中，作者把系統中的顧客數作為水平，把服務臺的狀態作為位相，對該排隊系統建立了無限水平有限位相的QBD 過程模型.因為這時服務臺要么位于正規忙期，要么位于工作休假狀態，所以所得QBD 過程的位相只取2 個不同值.從而通過對模型求解，可得到平穩狀態時服務臺位于忙期或位于工作休假的概率.然而，對多重工作休假排隊系統，因為當一次休假結束時，只要系統仍然沒有顧客，服務臺將進入另一個獨立休假.因此，休假可以連續進行，這樣，我們應考慮已知服務臺位于工作休假狀態時，它具體位于第幾次工作休假的概率，這一問題用文獻[8]中的模型無法直接回答.鑒于此，在本文中，我們對該排隊系統應用無限位相GI/M/1 型Markov 過程重新建模，通過對該過程的求解，不但可得該模型的經典結果，如平穩隊長分布等，還對上述問題作了回答.所得新結果使得對服務臺狀態的刻畫更為具體.

在本文的其余部分，首先，在第2 節給出所研究排隊系統的一個新數學模型；然后，在第3 節對模型求解，并對本文討論的排隊系統進行分析；第4 節給出若干數值例子；最后，第5 節是小結部分.

2 模型描述

對經典的Geo/Geo/1 多重工作休假排隊系統，假設顧客的到達發生在時隙(n,n+), n≥0，顧客的離去發生在時隙(n-,n), n ≥1，按照Hunter[9]的約定，本文考慮的是早到系統.設到達間隔獨立同分布，共同的分布是參數為p的幾何分布而服務時間服從參數為q的幾何分布.假設休假時間服從參數為θ的幾何分布，且在休假期，系統為到達的顧客提供服務的速率為η，其中η ＜q.另外，在本文中，對任意實數x ∈(0,1)，定義ˉx=1-x.

令Ln表示時刻n時系統中的顧客數，則按照早到規則，在時隙(n-,n)離去的顧客不再計入Ln.令Jn表示時刻n時服務臺的狀態，且規定Jn= 0 表示服務臺位于正規忙期，而對k ≥1，Jn=k表示服務臺位于工作休假狀態且恰好位于第k次休假.考慮二維Markov 過程{Jn,Ln,n ≥0}，其狀態空間為

其中對l ≥1，狀態(0,l)表示服務臺位于正規忙期且這時系統中有l個顧客；對k ≥1 及l ≥0，狀態(k,l)表示服務臺位于第k次工作休假且系統中有l個顧客.

當把狀態按字典規則排序時[10]，上述Markov 過程的轉移概率矩陣具有如下所示的分塊矩陣形式

其中A0=diag{ˉpq,0,0,···},A=diag{ˉpθ,0,0,···},

因此，所得過程是一個無限位相的GI/M/1 型Markov 過程[11].

都是無窮維向量，這時由文獻[11]知平穩分布滿足如下所示的算子幾何解

其中R 是一個無窮維矩陣，稱為率算子且對本文所討論的情形，它是下述矩陣方程的最小非負解

另外，初始向量π0和π1由線性方程組

以及規一化條件共同確定.

3 平穩分析

本小節對所建立的模型求解，并對排隊系統的平穩狀態進行分析.為了求解模型，首先給出率算子R 以及初始分量π0和π1，有下述兩個引理.

引理1 率算子R 的具體形式如下所示

其中

都是位于(0,1)中的常數.

證明 由率算子的概率解釋[10]可知對本文討論的模型，R 除了第一行外其余各行元素皆為0.現在令(r0,r1,···)表示其非零行，則通過簡單的代數運算可知方程(2)的分量形式為

其中方程(7)是一個二階線性齊次差分方程，且特征方程為

從而易得其兩個特征根為

因此

這里γ和δ都是待定常數.另外，由常規的代數運算容易驗證r ∈(0,1), s ＞1，所以為了得到方程(2)的最小非負解，常數δ必須為0，因而由(6)可知

由此即得引理的結論.

引理2 在平穩分布中，初始向量π0和π1的分量由以下兩式給出

其中π01待定.

證明 因為π0和π1滿足線性方程組(3)和(4)，由各子矩陣的具體形式，易知方程(4)的分量形式為

其中方程(11)是一個二階齊次線性差分方程，由類似于引理1 中的方法可得其收斂解為

因而π11=rπ10，代入(10)式后化簡，再由γ的定義可得

由此即得(9)式.

其次，由(5)出發可以驗證

所以有

把上式代入方程(3)后，并利用(9)進行化簡，可得其分量形式為

最后，由π1l的表達式和(15)式，可得

再由(12)式以及γ的定義，把上式右邊化簡可得

這是一個二階非齊次線性差分方程，且當ρ ＜1 時，易求得其唯一收斂解為

有了引理1 和引理2，現在給出本文的兩個主要結論如下.

定理1 令bl表示平穩狀態時服務臺處于正規忙期且系統中有l個顧客的概率，令wk表示平穩狀態時服務臺處于休假狀態且恰好處于第k次休假的概率，則有

其中

是一個常數.

證明 首先給出Markov 過程的聯合平穩分布.由算子幾何解(1)式以及(9)式和(13)式，可得

因此，再由(8)式以及歸一化條件可得

推論2 令Nw表示平穩狀態時服務臺在一次工作休假期連續進行休假的次數，則有

可得推論的結論.

定理2 令L表示平穩狀態時系統中的顧客數，則有

其中K的定義見定理1.

證明 因為

再由(8),(18)兩式出發，經過計算易得.

在方程(19)的基礎上，可以進一步討論該排隊模型平穩隊長和平穩逗留時間的隨機分解結果，相應的結果可參見文獻[8].

4 數值例子

在前面的分析中，我們得到了Geo/Geo/1 多重工作休假排隊一些平穩指標的結果，特別是得到了平穩狀態時服務臺位于第k次休假的概率wk以及一個休假期內連續休假次數Nw的分布以及平均次數，這些是關于該排隊模型的新結果.本小節用數值例子對上述新指標進行分析，考慮這些指標隨著某些參數變化的規律.其它指標，如平穩隊長、平穩逗留時間隨某些參數的變化情形可以參見文獻[8].

第一個例子考慮平穩狀態時服務臺位于第k次休假的概率wk隨k變化的情形.首先，令q= 0.6, θ= 0.3, η= 0.3，對p= 0.1,0.3,0.5 三種情形下wk的變化曲線，如圖1(a)所示.由該圖可以看出，當p固定時，wk隨k的增加而減少；同樣地，當k固定時，wk也隨p的增加而減少.

其次，令p=0.3, q=0.7, θ=0.3，對η=0.1,0.3,0.5 三種情形下wk的變化曲線，如圖1(b)所示.由該圖可以看出，這時曲線的變化規律與前一情形類似.

圖1 位于第k 次休假的概率wk 隨k 的變化曲線

第二個例子考慮一個休假期間平均休假次數ENw隨某些參數的變化規律.首先是ENw隨p的變化情形，令q= 0.7, θ= 0.3,0.4,0.5，令p ∈[0.3,0.6].相應的曲線如圖2(a)所示.由該圖可以看出，當θ固定時，ENw隨p的增加而減小；但對固定的p,ENw隨θ的增加而增加.

其次，考慮ENw隨η的變化情形，令p= 0.6, q= 0.8, θ= 0.3,0.4,0.5，令η ∈[0.1,0.5].相應的曲線如圖2(b)所示.由該圖可以看出，當θ固定時，ENw隨η的增加而增加；同時對固定的η,ENw隨θ的增加而增加.

圖2 一個休假期平均休假次數ENw 隨參數的變化曲線

5 小結

本文用一種新的方法討論了經典的Geo/Geo/1 多重工作休假排隊系統，給出了一些新的結論，它們對排隊模型平穩狀態時服務臺的狀態進行了更為細致的刻畫，因而，具有重要的意義.

另外，應用本文方法能否對其它多重工作休假排隊模型如M/G/1 工作休假排隊或GI/M/1 工作休假排隊進行研究，是有意義的值進一步考慮的問題.