基于GI/M/1 型Markov 過(guò)程的Geo/Geo/1多重工作休假排隊(duì)系統(tǒng)分析

張宏波, 彭培讓

(河南財(cái)政金融學(xué)院統(tǒng)計(jì)與數(shù)學(xué)學(xué)院，鄭州 450046)

1 引言

離散時(shí)間休假排隊(duì)模型由于在計(jì)算機(jī)系統(tǒng)、控制系統(tǒng)、通訊系統(tǒng)等領(lǐng)域有重要的潛在應(yīng)用價(jià)值，因而得到了大量的研究.詳細(xì)的介紹可以參見(jiàn)文獻(xiàn)[1—5].

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

在Tian 等[8]對(duì)Geo/Geo/1 多重工作休假排隊(duì)模型的研究中，作者把系統(tǒng)中的顧客數(shù)作為水平，把服務(wù)臺(tái)的狀態(tài)作為位相，對(duì)該排隊(duì)系統(tǒng)建立了無(wú)限水平有限位相的QBD 過(guò)程模型.因?yàn)檫@時(shí)服務(wù)臺(tái)要么位于正規(guī)忙期，要么位于工作休假狀態(tài)，所以所得QBD 過(guò)程的位相只取2 個(gè)不同值.從而通過(guò)對(duì)模型求解，可得到平穩(wěn)狀態(tài)時(shí)服務(wù)臺(tái)位于忙期或位于工作休假的概率.然而，對(duì)多重工作休假排隊(duì)系統(tǒng)，因?yàn)楫?dāng)一次休假結(jié)束時(shí)，只要系統(tǒng)仍然沒(méi)有顧客，服務(wù)臺(tái)將進(jìn)入另一個(gè)獨(dú)立休假.因此，休假可以連續(xù)進(jìn)行，這樣，我們應(yīng)考慮已知服務(wù)臺(tái)位于工作休假狀態(tài)時(shí)，它具體位于第幾次工作休假的概率，這一問(wèn)題用文獻(xiàn)[8]中的模型無(wú)法直接回答.鑒于此，在本文中，我們對(duì)該排隊(duì)系統(tǒng)應(yīng)用無(wú)限位相GI/M/1 型Markov 過(guò)程重新建模，通過(guò)對(duì)該過(guò)程的求解，不但可得該模型的經(jīng)典結(jié)果，如平穩(wěn)隊(duì)長(zhǎng)分布等，還對(duì)上述問(wèn)題作了回答.所得新結(jié)果使得對(duì)服務(wù)臺(tái)狀態(tài)的刻畫(huà)更為具體.

在本文的其余部分，首先，在第2 節(jié)給出所研究排隊(duì)系統(tǒng)的一個(gè)新數(shù)學(xué)模型；然后，在第3 節(jié)對(duì)模型求解，并對(duì)本文討論的排隊(duì)系統(tǒng)進(jìn)行分析；第4 節(jié)給出若干數(shù)值例子；最后，第5 節(jié)是小結(jié)部分.

2 模型描述

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

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

其中對(duì)l ≥1，狀態(tài)(0,l)表示服務(wù)臺(tái)位于正規(guī)忙期且這時(shí)系統(tǒng)中有l(wèi)個(gè)顧客；對(duì)k ≥1 及l(fā) ≥0，狀態(tài)(k,l)表示服務(wù)臺(tái)位于第k次工作休假且系統(tǒng)中有l(wèi)個(gè)顧客.

當(dāng)把狀態(tài)按字典規(guī)則排序時(shí)[10]，上述Markov 過(guò)程的轉(zhuǎn)移概率矩陣具有如下所示的分塊矩陣形式

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

因此，所得過(guò)程是一個(gè)無(wú)限位相的GI/M/1 型Markov 過(guò)程[11].

都是無(wú)窮維向量，這時(shí)由文獻(xiàn)[11]知平穩(wěn)分布滿(mǎn)足如下所示的算子幾何解

其中R 是一個(gè)無(wú)窮維矩陣，稱(chēng)為率算子且對(duì)本文所討論的情形，它是下述矩陣方程的最小非負(fù)解

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

以及規(guī)一化條件共同確定.

3 平穩(wěn)分析

本小節(jié)對(duì)所建立的模型求解，并對(duì)排隊(duì)系統(tǒng)的平穩(wěn)狀態(tài)進(jìn)行分析.為了求解模型，首先給出率算子R 以及初始分量π0和π1，有下述兩個(gè)引理.

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

其中

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

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

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

從而易得其兩個(gè)特征根為

因此

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

由此即得引理的結(jié)論.

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

其中π01待定.

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

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

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

由此即得(9)式.

其次，由(5)出發(fā)可以驗(yàn)證

所以有

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

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

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

這是一個(gè)二階非齊次線性差分方程，且當(dāng)ρ ＜1 時(shí)，易求得其唯一收斂解為

有了引理1 和引理2，現(xiàn)在給出本文的兩個(gè)主要結(jié)論如下.

定理1 令bl表示平穩(wěn)狀態(tài)時(shí)服務(wù)臺(tái)處于正規(guī)忙期且系統(tǒng)中有l(wèi)個(gè)顧客的概率，令wk表示平穩(wěn)狀態(tài)時(shí)服務(wù)臺(tái)處于休假狀態(tài)且恰好處于第k次休假的概率，則有

其中

是一個(gè)常數(shù).

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

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

推論2 令Nw表示平穩(wěn)狀態(tài)時(shí)服務(wù)臺(tái)在一次工作休假期連續(xù)進(jìn)行休假的次數(shù)，則有

可得推論的結(jié)論.

定理2 令L表示平穩(wěn)狀態(tài)時(shí)系統(tǒng)中的顧客數(shù)，則有

其中K的定義見(jiàn)定理1.

證明 因?yàn)?/p>

再由(8),(18)兩式出發(fā)，經(jīng)過(guò)計(jì)算易得.

在方程(19)的基礎(chǔ)上，可以進(jìn)一步討論該排隊(duì)模型平穩(wěn)隊(duì)長(zhǎng)和平穩(wěn)逗留時(shí)間的隨機(jī)分解結(jié)果，相應(yīng)的結(jié)果可參見(jiàn)文獻(xiàn)[8].

4 數(shù)值例子

在前面的分析中，我們得到了Geo/Geo/1 多重工作休假排隊(duì)一些平穩(wěn)指標(biāo)的結(jié)果，特別是得到了平穩(wěn)狀態(tài)時(shí)服務(wù)臺(tái)位于第k次休假的概率wk以及一個(gè)休假期內(nèi)連續(xù)休假次數(shù)Nw的分布以及平均次數(shù)，這些是關(guān)于該排隊(duì)模型的新結(jié)果.本小節(jié)用數(shù)值例子對(duì)上述新指標(biāo)進(jìn)行分析，考慮這些指標(biāo)隨著某些參數(shù)變化的規(guī)律.其它指標(biāo)，如平穩(wěn)隊(duì)長(zhǎng)、平穩(wěn)逗留時(shí)間隨某些參數(shù)的變化情形可以參見(jiàn)文獻(xiàn)[8].

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

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

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

第二個(gè)例子考慮一個(gè)休假期間平均休假次數(shù)ENw隨某些參數(shù)的變化規(guī)律.首先是ENw隨p的變化情形，令q= 0.7, θ= 0.3,0.4,0.5，令p ∈[0.3,0.6].相應(yīng)的曲線如圖2(a)所示.由該圖可以看出，當(dāng)θ固定時(shí)，ENw隨p的增加而減?。坏珜?duì)固定的p,ENw隨θ的增加而增加.

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

圖2 一個(gè)休假期平均休假次數(shù)ENw 隨參數(shù)的變化曲線

5 小結(jié)

本文用一種新的方法討論了經(jīng)典的Geo/Geo/1 多重工作休假排隊(duì)系統(tǒng)，給出了一些新的結(jié)論，它們對(duì)排隊(duì)模型平穩(wěn)狀態(tài)時(shí)服務(wù)臺(tái)的狀態(tài)進(jìn)行了更為細(xì)致的刻畫(huà)，因而，具有重要的意義.

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