在隨機啟動(p, N)-策略控制下不中斷多重休假排隊系統(tǒng)的性能分析

袁雨梅,唐應(yīng)輝,劉雨欣,陳鐮元

(四川師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院,四川 成都 610068)

1.引言

在連續(xù)時間和離散時間排隊模型的研究中,有大量文獻(xiàn)研究了帶有服務(wù)員休假機制和系統(tǒng)控制策略的排隊模型,其中經(jīng)典的一維控制策略包括:N-策略、T-策略、D-策略等[1-3],典型的服務(wù)員休假有單重休假、多重休假和多級適應(yīng)性休假等[4-5].在此基礎(chǔ)上,許多作者做了大量的推廣和深入的研究工作[6-15],例如文[6]利用遞推法討論了帶反饋和單重休假的Geom/G/1 排隊系統(tǒng).進(jìn)一步,文[7]考慮了基于多重休假的GI/Geom(a,b)/1/N排隊系統(tǒng).基于實際應(yīng)用,文[9-10,12-13]研究了帶有Min(N,V)-策略的排隊系統(tǒng),Min(N,V)-策略是指每當(dāng)系統(tǒng)變空時,服務(wù)員就去休假或離開系統(tǒng)去做輔助性工作以增加系統(tǒng)的收入.在服務(wù)員的假期中,如果到達(dá)系統(tǒng)的顧客數(shù)達(dá)到了N個,服務(wù)員馬上結(jié)束休假并開始為顧客進(jìn)行服務(wù)直到系統(tǒng)再次變空,此時服務(wù)員的休假是可以中斷的.文[11,14]研究了有Min(N,D)-策略的排隊模型,這是將N-策略和D-策略聯(lián)合起來形成的二維控制策略.類似地,文[15]對帶雙閥值(m,N)-控制策略的M/G/1可修排隊系統(tǒng)進(jìn)行了研究,并通過數(shù)值計算實例討論了其最優(yōu)控制策略.

在前面的研究中服務(wù)員的休假時間都是可中斷的,但是在實際生活中的情況并不完全是這樣,如果服務(wù)員正在從事的輔助性工作的過程是無法終止的(例如某醫(yī)生幫其他醫(yī)生救治危重病人),那么這時候只能等服務(wù)員完成輔助性的工作后才能返回系統(tǒng)為顧客進(jìn)行服務(wù).于是將不中斷的休假引入到帶有控制策略的排隊系統(tǒng)研究中,例如文[16]在雙水平控制策略的基礎(chǔ)上將延遲不中斷單重休假與之結(jié)合起來,研究了有雙水平(m,N)-控制策略和延遲不中斷單重休假的M/G/1排隊系統(tǒng).文[17]提出了(p,N)-策略,即(p,N)-策略就是當(dāng)系統(tǒng)變空時,服務(wù)員就關(guān)閉系統(tǒng),當(dāng)系統(tǒng)累積的顧客數(shù)達(dá)到N個時,服務(wù)員以概率p(0≤p ≤1)啟動服務(wù),以概率(1?p)不啟動服務(wù),服務(wù)員處于通常的閑期直到系統(tǒng)中的顧客數(shù)大于N個時再開始為顧客服務(wù).文[18]利用最大熵法研究了有(p,N)-策略和服務(wù)臺不可靠的排隊系統(tǒng).最近,在一些具有(p,N)-策略的排隊模型研究的基礎(chǔ)上[19-21],文[21]討論了雙水平隨機(p,N1,N2)-策略的M/G/1排隊系統(tǒng),推廣了(p,N)-策略的研究.利用全概率分解技術(shù)及更新過程理論得到了系統(tǒng)的瞬時隊長分布及其拉普拉斯變換的遞推表達(dá)式,再利用洛必達(dá)法則得到了穩(wěn)態(tài)隊長分布及隊長的隨機分解結(jié)果.最后通過數(shù)值計算實例探究了穩(wěn)態(tài)隊長分布在系統(tǒng)容量設(shè)計中的重要作用,并在建立費用結(jié)構(gòu)模型的基礎(chǔ)上,通過數(shù)值計算實例討論了最優(yōu)控制策略(N?1,N?2).

基于上述,本文將“隨機啟動(p,N)-策略”與“不中斷多重休假”結(jié)合起來,建立了在隨機啟動(p,N)-策略控制下不中斷多重休假的M/G/1排隊系統(tǒng).本文的隨機啟動(p,N)-策略是指,當(dāng)服務(wù)員休假回來時,如果系統(tǒng)中等待服務(wù)的顧客數(shù)大于等于N(N ≥1)個,則服務(wù)員立即啟動服務(wù),若系統(tǒng)中有顧客但顧客數(shù)少于N個,則服務(wù)員以概率p(0≤p ≤1)啟動服務(wù),以概率(1?p)不啟動服務(wù),服務(wù)員處于通常的閑期直到系統(tǒng)中的顧客數(shù)累積到N個時才立即啟動服務(wù),如果系統(tǒng)中沒有顧客,則服務(wù)員就進(jìn)行另一次不中斷的休假.在此排隊模型中,既考慮了系統(tǒng)頻繁啟動而帶來的成本增加,也考慮了休假回來時在系統(tǒng)中等待顧客的心態(tài),貼近現(xiàn)實實際,也豐富了現(xiàn)有的排隊模型.然后我們將利用全概率分解技術(shù),討論系統(tǒng)從任意初始狀態(tài)開始的隊長的瞬時概率分布,推導(dǎo)出了隊長瞬態(tài)分布的拉普拉斯變換的遞推表達(dá)式.進(jìn)一步根據(jù)其遞推表達(dá)式,再利用洛必達(dá)法則得到隊長的穩(wěn)態(tài)分布表達(dá)式,同時得到了穩(wěn)態(tài)隊長分布的概率母函數(shù)、平均隊長以及附加隊長的顯示表達(dá)式等排隊性能指標(biāo).最后通過數(shù)值計算實例,討論了系統(tǒng)空閑率p0和附加平均隊長ˉLd關(guān)于一些參數(shù)的敏感性,以及穩(wěn)態(tài)隊長分布的表達(dá)式在系統(tǒng)容量設(shè)計中的重要作用.

2.問題的描述與一些符號說明

本文提出建立的排隊模型如下:

1) 顧客的到達(dá)間隔序列{τi,i ≥1}是相互獨立、同負(fù)指數(shù)分布F(t)1?e-λt,t ≥0,λ>0的隨機變量,顧客的服務(wù)時間序列{χi,i ≥1}獨立同一般分布G(t),記平均服務(wù)時間為1/μ(0<μ<∞).

2) 服務(wù)員的多重休假機制與啟動服務(wù)的隨機(p,N)-策略:每當(dāng)系統(tǒng)變空時,服務(wù)員就去進(jìn)行一次不中斷的休假.當(dāng)服務(wù)員休假回來時,如果系統(tǒng)中等待服務(wù)的顧客數(shù)大于等于N(N ≥1)個,則服務(wù)員立即啟動服務(wù)直到系統(tǒng)再次變空.若系統(tǒng)中有顧客但顧客數(shù)少于N個,則服務(wù)員以概率p(0≤p ≤1)啟動服務(wù),以概率(1?p)不啟動服務(wù),服務(wù)員處于通常的閑期直到系統(tǒng)中的顧客數(shù)累積到N個時才立即啟動服務(wù),如果系統(tǒng)中沒有顧客,則服務(wù)員就進(jìn)行另一次不中斷的休假,休假時間序列{Vi,i ≥1}獨立服從任意分布V(t).

3) 顧客的到達(dá)間隔時間τ、顧客的服務(wù)時間χ與服務(wù)員的休假時間V是彼此獨立的.

4) 在t0時刻,如果有顧客則立即開始服務(wù),如果系統(tǒng)是空的,則服務(wù)員留在系統(tǒng)中等待顧客的到達(dá)并立即服務(wù)(這樣的假設(shè)更符合實際情況,但穩(wěn)態(tài)結(jié)果與初始狀態(tài)假設(shè)無關(guān)).

3.隊長的瞬態(tài)分布和穩(wěn)態(tài)分布

表示在服務(wù)員忙期b中時刻t的瞬時隊長分布,且t0時只有一個顧客,服務(wù)員忙期b剛開始,即Q1(0)1,Qj(0)0,j>1.

下面我們使用一種直接的概率分析法來討論系統(tǒng)隊長的瞬態(tài)分布,而嵌入馬爾科夫鏈和補充變量分析等傳統(tǒng)分析技術(shù)是無法直接討論系統(tǒng)在任意時刻t隊長的瞬態(tài)分布的.令

再把(3.9)式代入(3.7)式,經(jīng)整理得(3.1)式,再把(3.1)式代入(3.9)式可得(3.2)式.證畢.

定理3.2對?(s)>0和i ≥1,有

證當(dāng)j1,2,···,N ?1時,“時刻t隊長為j”可分為三種情形:

1) 時刻t落在服務(wù)員忙期中且系統(tǒng)中顧客數(shù)為j;

2) 時刻t落在服務(wù)員假期中且系統(tǒng)中顧客數(shù)為j;

3) 時刻t落在假期結(jié)束后的服務(wù)員非忙期中且系統(tǒng)中顧客數(shù)為j.

類似定理3.1的分解,可得

對i ≥1,同理可得

(3.14)-(3.15)式的L變換

由(3.16)式和(3.17)式可得關(guān)系式

再把(3.18)代入(3.16),經(jīng)整理得(3.10),再把(3.10)式代入(3.18)式得(3.11)式.

當(dāng)j ≥N時,類似地,“時刻t隊長為j”可分為兩種情形:

1) 時刻t落在服務(wù)員忙期中且系統(tǒng)中顧客數(shù)為j;

2) 時刻t落在服務(wù)員假期中且系統(tǒng)中顧客數(shù)為j.

由全概率分解技術(shù),可得

對i ≥1,同理可得

(3.19)-(3.20)式的L變換

由(3.21)式和(3.22)式可得關(guān)系式

再把(3.23)代入(3.21),經(jīng)整理得(3.12),再把(3.12)式代入(3.23)式得(3.13)式,證畢.

在上面瞬態(tài)分析的基礎(chǔ)上,下面我們使用洛必達(dá)法則,結(jié)合引理3.1很容易得到隊長穩(wěn)態(tài)分布的遞推表達(dá)式,這是嵌入馬爾科夫鏈和補充變量分析等傳統(tǒng)分析技術(shù)不能得到的(嵌入馬爾科夫鏈和補充變量分析等傳統(tǒng)分析技術(shù)直接得到的只是穩(wěn)態(tài)分布的概率母函數(shù)).

將(3.29)式和(3.30)式代入(3.28)式,整理即可證明,證畢.

定理3.5(穩(wěn)態(tài)隊長的隨機分解) 本文研究的在隨機啟動(p,N)-策略控制下不中斷多重休假的M/G/1排隊系統(tǒng)的穩(wěn)態(tài)隊長可以分解成獨立的兩部分之和:一部分是經(jīng)典M/G/1排隊系統(tǒng)的穩(wěn)態(tài)隊長,另一部分是由多重休假與(p,N)-策略機制引起的附加隊長Ld,且附加隊長Ld有如下離散分布:

證由上面(3.31)式可知本文研究的排隊系統(tǒng)的穩(wěn)態(tài)隊長可分解成獨立的兩部分之和,下面證明附加隊長Ld有上式的離散分布,令

4.一些特殊情形

推論4.3當(dāng)p1時,即服務(wù)員休假結(jié)束時,系統(tǒng)中只要有顧客在等待服務(wù),服務(wù)員就立即為顧客服務(wù),則本文研究的模型等價于多重休假的M/G/1排隊系統(tǒng)[3,5],在上面所得結(jié)果中,令p1,即可得與文[3,5]完全一致的相應(yīng)結(jié)果.

推論4.4當(dāng)p1,P {V0}1時,即服務(wù)員不去進(jìn)行休假且只要系統(tǒng)中有顧客,服務(wù)員就立即為顧客服務(wù),則本文研究的模型等價于無休假的經(jīng)典M/G/1排隊系統(tǒng)[5],在上面所得結(jié)果中,令p1,P {V0}1,即可得與文[5]完全一致的相應(yīng)結(jié)果.

推論4.5當(dāng)N1時,即服務(wù)員休假結(jié)束時,只要系統(tǒng)中有一個顧客在等待服務(wù),服務(wù)員就立即為顧客服務(wù),則本文研究的模型等價于多重休假的M/G/1排隊系統(tǒng)[3,5],在上面所得結(jié)果中,令N1,即可得與文[3,5]完全一致的相應(yīng)結(jié)果.

推論4.6當(dāng)p0,P {V0}1時,本文研究的模型等價于N-策略M/G/1排隊系統(tǒng)[3],在上面所得結(jié)果中,令p0,P {V0}1,即可得與文[3]完全一致的相應(yīng)結(jié)果.

5.系統(tǒng)空閑率p0與附加平均隊長d關(guān)于系統(tǒng)參數(shù)的敏感性分析

在本節(jié)中,我們將通過數(shù)值計算實例來分析系統(tǒng)空閑率p0與附加平均隊長隨著p,N和休假時間V的變化情況.

取參數(shù)λ0.6,μ1.2,θ2.5,利用Matlab軟件編寫數(shù)值計算程序,圖5.1反映了附加平均隊長隨概率p和控制值N的變化情況,圖5.2反映了系統(tǒng)空閑率p0隨概率p和控制值N的變化情況.

圖5.2 λ=0.6,μ=1.2,θ=2.5時,p0隨p和N的變化情況

例5.2當(dāng)G(t)1?e-μt和休假時間為定長分布P{VT}1時,在ρ<1下,與p0的表達(dá)式分別為

取參數(shù)λ0.6,μ1.2,p0.6,利用Matlab軟件編寫數(shù)值計算程序,圖5.3反映了附加平均隊長d隨休假時間T和控制值N的變化情況,圖5.4反映了系統(tǒng)空閑率p0隨休假時間T和控制值N的變化情況.

圖5.3 λ=0.6,μ=1.2,p=0.6時,d隨T和N的變化情況

圖5.4 λ=0.6,μ=1.2,p=0.6時,p0隨T和N的變化情況

由圖5.2和圖5.4我們可以看出,當(dāng)休假時間V和概率p確定時,系統(tǒng)的空閑率p0是關(guān)于N的遞減函數(shù),這是由于當(dāng)休假時間V和概率p確定時,受N-策略的影響,使得系統(tǒng)中等待服務(wù)的顧客數(shù)增加,從而系統(tǒng)的空閑率p0呈現(xiàn)減小的變化趨勢.根據(jù)圖5.2可知,當(dāng)N的取值確定且概率p的取值不斷增大時,系統(tǒng)的空閑率p0呈現(xiàn)增大的變化趨勢,這是由于當(dāng)p增大時,進(jìn)入系統(tǒng)的顧客被及時服務(wù)的機率增大,從而使得系統(tǒng)的空閑率p0增大,而當(dāng)N大于某一值后,p0受N的影響變化得較緩慢,此時主要受p的影響,特別當(dāng)p1時,系統(tǒng)的空閑率p0是不變的,此時系統(tǒng)的空閑率完全受休假時間V的影響.而從圖5.4中我們可知,當(dāng)N的取值確定且休假時間T的取值不斷增大時,系統(tǒng)空閑率p0是逐漸減小的,這是隨著休假時間的變長,“服務(wù)員忙期”開始時的顧客數(shù)不斷增加的原因.另外,當(dāng)N小于某一值時,p0主要受T的影響,且隨著休假時間T的增大,休假時間在影響系統(tǒng)空閑率p0時起主導(dǎo)作用的時間越長,p0隨N的變化也越來越緩慢,而當(dāng)N大于某一值時,休假時間T在影響系統(tǒng)空閑率p0時所起的作用越來越小.

6.穩(wěn)態(tài)隊長分布{pj}的數(shù)值計算與系統(tǒng)容量的優(yōu)化設(shè)計

下面通過對穩(wěn)態(tài)隊長分布{pj,j ≥0}的數(shù)值計算來說明穩(wěn)態(tài)隊長分布{pj,j ≥0}在系統(tǒng)容量的優(yōu)化設(shè)計中的重要作用,從而體現(xiàn)了本文得到穩(wěn)態(tài)隊長分布{pj,j ≥0}的表達(dá)式(上面定理3.3)的意義.

大家知道,系統(tǒng)容量過大會導(dǎo)致系統(tǒng)的建設(shè)成本和管理成本太高,而過低的容量又會導(dǎo)致顧客的丟失,從而引起系統(tǒng)的損失.表6.1給出了在G(t)1?e-μt和V(t)1?e-θt,且令參數(shù)λ0.6,μ1.2,θ2.5,p0.6,N10時穩(wěn)態(tài)隊長分布{pj,j ≥0}的數(shù)值結(jié)果.由表6.1可以看出,當(dāng)j大于某一值后,此時的穩(wěn)態(tài)隊長分布pj取值已經(jīng)接近于零了,所以在系統(tǒng)的容量設(shè)計中,我們不需要把系統(tǒng)的容量設(shè)計成無窮大.根據(jù)表中數(shù)據(jù)可知:

表6.1 當(dāng)λ=0.6,μ=1.2,θ=2.5,p=0.6,N=10時,穩(wěn)態(tài)隊長分布{pj,j ≥0}的數(shù)值結(jié)果

由表格結(jié)果可知,若按平均隊長為標(biāo)準(zhǔn)進(jìn)行系統(tǒng)容量設(shè)計,則到達(dá)的顧客因系統(tǒng)容量不夠而損失的概率為0.5977,即使按比平均隊長大1個單位為參考標(biāo)準(zhǔn)設(shè)計,到達(dá)的顧客因為系統(tǒng)的容量不夠而損失的概率也達(dá)到了0.5096.所以我們只依靠平均隊長作為系統(tǒng)容量設(shè)計的標(biāo)準(zhǔn)是不合理的.

令M是待確定的系統(tǒng)容量,如果要求到達(dá)的顧客損失的概率不超過萬分之一,即損失的概率不超過0.0001,即

根據(jù)表6.1的數(shù)據(jù)我們可以得到M ≥19,即系統(tǒng)容量取M19即可,由此可見穩(wěn)態(tài)隊長分布在系統(tǒng)容量設(shè)計上的重要作用,這也體現(xiàn)了本文所獲得的穩(wěn)態(tài)隊長分布的表達(dá)式(定理3.3)有非常重要的應(yīng)用價值.

7.結(jié)語

本文將不中斷多重休假機制與隨機啟動(p,N)-策略結(jié)合起來,提出建立了一個新的排隊模型,然后使用直接的概率分解分析方法和路徑討論了系統(tǒng)的瞬態(tài)隊長分布,得到了瞬態(tài)隊長分布關(guān)于時間t的拉普拉斯變換的遞推表達(dá)式,并利用洛必達(dá)法則推得了穩(wěn)態(tài)隊長分布的遞推表達(dá)式,同時得到了一些其他排隊指標(biāo).最后通過數(shù)值計算實例討論了系統(tǒng)空閑率p0和附加平均隊長ˉLd關(guān)于系統(tǒng)參數(shù)的敏感性,并闡釋了穩(wěn)態(tài)隊長分布在系統(tǒng)容量設(shè)計中的重要價值,彌補了只依靠平均隊長進(jìn)行系統(tǒng)容量設(shè)計而帶來的不足,使得本文研究結(jié)果有更好的應(yīng)用價值.