基于Min(N,D,V)-策略和單重休假的M/G/1排隊系統隊長分布的瞬態和穩態解

王 敏, 唐應輝

(四川師范大學數學科學學院，成都 610068)

1 引言

根據實際背景和應用的需要，在平衡顧客等待時間的同時也為了降低系統成本，從而增加系統的收入，學者們在研究經典排隊系統的同時，提出并研究了許多休假排隊模型和有控制策略的排隊模型，取得了較豐碩的成果[1-23]，大大拓寬了早期排隊論的研究和應用領域.經典的休假策略有服務員的單重休假、服務員的多重休假和多級適應性休假等，而經典的控制策略有T-策略、D-策略和N-策略等.隨著研究的深入，一些把服務員休假與控制策略相結合的排隊模型也得到了學者們的關注，例如把N-控制策略與服務員單重(多重)休假相結合，就產生了N-策略單重休假排隊模型、N-策略多重休假排隊模型，以及具有休假中斷機制的Min(N,V)-策略休假排隊模型.從管理和成本的角度，當生產和制造的環境發生較大改變時，系統想要轉換成另一種控制策略，但大多數情況下，由于成本的原因要拋棄現有的硬件系統設施是不可能的，于是學者們把N-策略和D-策略等結合起來就提出了二維混合控制策略的排隊模型，如Min(N,D)-控制策略的排隊系統模型[15]，并且在這些方面的推廣研究也取得了較好成果[10-21].

文獻[15]研究的具有Min(N,D)-控制策略的排隊系統模型，其主要模型特征是把N-策略與D-策略有機結合起來，不僅分析了系統的排隊性能指標，而且在建立費用結構的基礎上，用數值計算例子討論了系統的二維最優控制策略，并與單一的N-策略和D-策略進行了比較分析，說明了混合控制策略優于單一的控制策略.本文在此基礎上，把服務員的休假機制引入其中，提出一種服務員可休假且在休假時間中根據Min(N,D,V)-控制策略可立即中斷休假的M/G/1 排隊模型，即具有Min(N,D,V)-控制策略和服務員單重休假的M/G/1 排隊模型：每當系統變空時，服務員就去休假(或去做輔助性工作，以增加系統的收入).如果在假期中到達的顧客數達到N個或者到達的顧客數所需服務時間總量超過D(D ≥0)，服務員馬上結束休假并開始為顧客服務.這種假期中斷機制對于控制系統隊長是有益的，而且可以克服系統頻繁轉換所帶來的費用問題，對系統的優化具有重要意義.本文應用更新過程理論和全概率分解知識，借用拉普拉斯變換工具，分析了在任意初始狀態條件下系統隊長的瞬態分布和穩態分布特征，得到了隊長瞬態分布解的拉普拉斯變換表達式和方便計算穩態隊長分布數值解的遞推表達式，從而進一步給出了穩態隊長的隨機分解結果和附加隊長分布解的顯示表達式，使我們更清楚地了解到該排隊模型的結構.

本文研究服務員具有單重休假，而且在休假中根據Min(N,D,V)-策略可中斷休假的M/G/1 排隊系統，其模型刻畫如下：

1)M/G/1 型排隊模型[23]：相鄰兩個顧客之間的到達是相互獨立的，其每個間隔時間τ有分布F(t)=1-e-λt，每個顧客的服務是相互獨立的，其每個顧客的服務時間χ有任意分布G(t)，且設平均服務時間為1/μ(0＜μ＜∞)；

2) 服務員采取單重休假機制和系統采取Min(N,D,V)-控制策略：每當系統變空時，服務員馬上開始一次隨機時間長度V的休假，且休假時間V服從任意分布V(t).但是，服務員在休假時間中根據Min(N,D,V)-控制策略可立即中斷休假，即在服務員的休假期間，如果系統中到達的顧客數達到了N個(N ≥1，事先設定的正整數閾值)，或者到達系統等待服務的顧客所需服務時間總量不小于D(D ≥0，事先設定的實數閾值)，無論哪一個先發生，處于休假期的服務員立即結束休假回到系統中為顧客服務(在這種情況下，服務員的實際休假時間長度達不到約定的休假時間長度V)；如果在服務員的休假期間系統中有顧客到達，但到達數沒有達到N個，且到達系統等待服務的顧客所需服務時間總量也小于D，則等到此次休假結束后服務員再回到系統中，且立即為在現場的顧客服務；如果服務員此次休假結束時系統中仍沒有顧客，則服務員留在系統中直到有顧客到達并立即服務；

3) 隨機變量τ、χ和V是相互獨立的，而且假設在t= 0 時刻，如果系統是空的，則不采取該休假機制和控制策略，服務員留在系統中等待顧客到達后立即對其進行服務(這樣的假設更符合實際情況，但穩態結果與此假設無關).

2 一些符號的說明和準備

一些符號說明：N(t)表示系統在任意時刻t的隊長，即時刻t在系統中的顧客數；

分別表示相應的G(t)關于t的拉普拉斯(L)變換和拉普拉斯-斯蒂爾切斯(LS)變換；G(k)(t)表示G(t)的k(≥1)重卷積，即

且

引入如下概念：

1) 系統閑期：系統連續保持空閑(無顧客)的一段時間.如果我們用表示系統第j個系統閑期的長度，則由到達過程為參數λ(λ ＞0)的泊松過程知其分布為P{≤t}=F(t)=1-e-λt,t ≥0,j ≥1；

2) 系統忙期：從第一個顧客到達空閑的系統起，直到系統再次變空為止的這段時間；

3) 服務員非忙期：從系統剛變空的時刻起，直到服務員休假結束回到系統而且開始為顧客服務的時刻為止的這段時間；

4) 服務員忙期：從服務員開始為顧客服務的時刻起，直到系統再次變空為止的這一段時間.

令b表示標準的M/G/1 排隊系統中從一個顧客開始的服務員忙期(從服務員開始為顧客服務的時刻起，直到系統再次變空為止的這一段時間)，對t ≥0,?(s)＞0，令

則有如下引理.

引理1[23]對?(s)＞0,b(s)是方程z=g(s+λ-λz)在|z|＜1 內的唯一根，且

其中ω(0＜ω ＜1)是方程z=g(λ-λz)在(0,1)內的根，表示系統的交通強度，?(s)表示復變量s的實部.

又令Qj(t) =P{b ＞t ≥0;N(t) =j}表示在服務員忙期b中隊長為j(j ≥1)的瞬態概率，并且t= 0 時，只有一個顧客，服務員忙期b剛開始，即Q1(0) = 1,Qj(0) =0,j ＞1.

引理2[23]令

為Qj(t)的拉普拉斯變換，對?(s)＞0，有

其中當j ＜0 時，有且求和

3 系統隊長分布的瞬態解

令pij(t) =P{N(t) =j|N(0) =i}表示初始時刻有i個顧客的條件下，時刻t隊長為j的瞬態概率，

定理1對?(s)＞0，有

其中

當求和的上標小于下標，即k ＜i時，求和下同.

上第(3)式的第三項為

對(3)-(5)式作L 變換，有

在N(0) = 0 初始條件下，根據模型假設中第3)條：在初始時刻系統中無顧客時服務員不休假，系統也不采取Min(N,D)-控制策略，所以

對(7)式作L 變換得到

在(6)式中，取i=1，結合(8)式可得

注1當N=1 或D=0 時，本文研究的排隊系統等價于文獻[23]討論的服務員無休假的經典M/G/1 排隊系統，所以下面對N=1 或D=0 的情況不再討論.

定理2當N ≥2 且D ＞0 時，對?(s)＞0，有：

1) 當j=1,2,···,N-1 時

2) 當j ≥N時

其中

證明 當j=1,2,···,N-1 時，因為“在時刻t隊長為j”可分為如下兩種情形.

情形1“時刻t落在服務員假期中且隊長為j”.

情形2“時刻t落在服務員忙期中且隊長為j”.

所以，當i ≥1，類似定理1 的分解，得

其中

(15)式的第二項為

把(16)式代入(15)式作L 變換，可得

同理可得

對(18)式作L 變換得到

當j ≥N時，在時刻t隊長為j當且僅當時刻t落在服務員忙期中且隊長為j，于是當i ≥1 時，使用全概率分解技術，同理可得

余下的推證過程完全仿照j=1,2,···,N-1 時的推導過程.

4 系統隊長分布的穩態解及穩態隊長的隨機分解結構

定理3令j=0,1,2,···，則：

此時{pj,j=0,1,2,···}構成概率分布，其中

證明 由

而

當j=0 時，有

1) 當ρ ＞1 或ρ=1 時，有

且E(b)=∞，而

于是使用洛必達法則，可得

對于j ≥1，結合(11)-(14)式，使用洛必達法則，完全仿照p0的推導過程可得.

由于

經計算可得

將(33)-(35)式代入(32)式，整理即可證明.

定理4(穩態隊長的隨機分解結構) 令P(z)表示該系統穩態隊長分布的概率母函數，當ρ ＜1 時，有

且平均隊長為

于是

定理5本文研究的基于Min(N,D,V)-策略和單重休假的M/G/1 排隊系統的穩態隊長可分解成獨立的兩部分之和：一部分是文獻[23]中的經典M/G/1 排隊系統的穩態隊長，另一部分是由服務員單重休假機制和Min(N,D)-策略引起的附加隊長Ld，且附加隊長有如下離散分布

證明 由上面(37)式可知本文研究的排隊系統的穩態隊長可分解為獨立的兩部分之和.下面求附加隊長Ld的離散分布.令

其中

然后利用

經過計算整理可得，這里H(m)(z)表示H(z)關于z求m(m= 1,2,···,N- 1)階導數，H(0)(z)=H(z).

5 一些特殊情形

推論1當P{V=T} = 1 時，即服務員事先約定的休假時間是一個固定時間長度T(T ＞0).對ρ ＜1，有

系統穩態隊長分布的概率母函數為

平均隊長為

其中

推論2當N →∞時，本文研究的排隊系統是在D-策略控制下服務員單重休假且休假可中斷的M/G/1 排隊系統.對ρ ＜1 時，有

母函數為

平均隊長為

其中

推論3當N →∞,P{V=T}=1 時，本文研究的排隊系統是在D-策略控制下服務員具有固定單重休假時間T且休假可中斷的M/G/1 排隊系統.對ρ ＜1 時，有

母函數為

平均隊長為

其中

推論4當D →∞時，本文研究的排隊系統是在N-策略控制下服務員單重休假且休假可中斷的M/G/1 排隊系統，即等價于文獻[14]研究的基于單重休假的Min(N,V)-策略控制的M/G/1 排隊系統.在上面所得的結果中，令D →∞即可得與文獻[14]完全一致的相應結果.

推論5當D →∞,P{V=T}=1 時，即系統是基于固定單重休假時間T的Min(N,T)-策略控制的M/G/1 排隊系統，對ρ ＜1 時，有

母函數為

平均隊長為

其中

推論6當P{V= 0} = 1 或D= 0 時，本文研究的排隊系統等價于文獻[23]研究的經典M/G/1 排隊系統.在上面所得的結果中，令P{V= 0} = 1 或D= 0 即可得到與文獻[23]完全一致的相應結果.

推論7當P{V=∞} = 1 時，本文研究的排隊系統等價于文獻[15]研究的Min(N,D)-控制策略的M/G/1 排隊系統.在上面所得的結果中，令P{V=∞}=1 即可得到與文獻[15]完全一致的相應結果.

6 附加平均隊長對系統參數的敏感性分析

在本節中，我們通過數值計算實例來分析系統的附加平均隊長E[Ld]隨著一些參數的變化而變化的情況.由定理5 可知附加平均隊長E[Ld]為

例1當服務時間服從參數μ(＞0)的負指數分布G(t) = 1-e-μt與休假時間服從參數θ(＞0)的負指數分布V(t)=1-e-θt時，代入上述表達式得到附加平均隊長E[Ld]為

取λ=0.5,ρ=0.75,D=10，然后運用Matlab 軟件編程進行計算得到E[Ld]隨N與θ的變化情況，見表1 與圖1，小數點后保留四位.

取λ=0.5,ρ=0.75,θ=0.25，然后運用Matlab 軟件編程進行計算得到E[Ld]隨N與D的變化情況，見表2 與圖2，小數點后保留四位.

表1: λ =0.5, ρ =0.75, D =10，E[Ld]隨N 與θ 的變化情況

表2: λ =0.5, ρ =0.75, θ =0.25，E[Ld]隨N 與D 的變化情況

圖1: E[Ld]隨N 與θ 的變化情況

圖2: E[Ld]隨N 與D 的變化情況

取λ=0.5,ρ=0.75,N=4，然后運用Matlab 軟件編程進行計算得到E[Ld]隨D與θ的變化情況，見表3 與圖3，小數點后保留四位.

表3: λ =0.5, ρ =0.75, N =4，E[Ld]隨D 與θ 的變化情況

圖3: E[Ld]隨 D 與 θ 的變化情況

例2當服務時間服從參數μ(＞0)的負指數分布G(t) = 1-e-μt與P{V=T} = 1時，即服務員事先約定的休假時間是一個固定時間長度T(＞0)，代入上述表達式得到附加平均隊長E[Ld]為

取λ=0.5,ρ=0.75,D=10，然后運用Matlab 軟件編程進行計算得到E[Ld]隨N與T的變化情況，見表4 與圖4，小數點后保留四位.

表4: λ=0.5, ρ=0.75, D =10，E[Ld]隨N 與T 的變化情況

圖4: E[Ld]隨N 與T 的變化情況

從圖1 和圖4 可以看出，取定參數λ= 0.5,ρ= 0.75,D= 10，當休假時間的參數確定或者休假時間是一個固定時間長度T(＞0)，隨著N取值的不斷增大，系統的附加平均隊長E[Ld]都是先增大而后趨于平穩保持不變，這是因為在N取值增大時，受Min(N,V)-控制策略的影響，N所起的作用越來越小，當N超過某一值時，系統的附加平均隊長幾乎由服務員的休假決定.且當服務員的休假時間越來越短時，這使得到達系統的顧客有較大機會被服務，因此系統的附加平均隊長E[Ld]呈現減小的趨勢.

取λ=0.5,ρ=0.75,T=10，然后運用Matlab 軟件編程進行計算，得到E[Ld]隨N與D的變化情況，見表5 與圖5，小數點后保留四位.

從圖2 和圖5 可以看出，取定參數λ= 0.5,ρ= 0.75，當D(＞0)確定時，隨著N取值的不斷增大，系統的附加平均隊長E[Ld]都是先增大而后趨于平穩保持不變，這是因為在N取值不斷增大時，受Min(N,D)-控制策略的影響，N所起的作用越來越小，當N超過某一值時，系統的附加平均隊長E[Ld]幾乎由參數D決定.同理，隨著D取值增大，受Min(N,D)-控制策略的影響，D所起的作用越來越小，系統幾乎由參數N決定.

圖5: T =10，E[Ld]隨N 與D 的變化情況

表5: λ =0.5, ρ=0.75, T =10，E[Ld]隨N 與D 的變化情況

取λ= 0.5,ρ= 0.75,N= 4，然后運用Matlab 軟件編程進行計算得到E[Ld]隨D與T的變化情況，見表6 與圖6，小數點后保留四位.

從圖3 和圖6 可以看出，取定參數λ= 0.5,ρ= 0.75,N= 4，當休假時間的參數確定或者取定休假時間是一個固定時間長度T(＞0)，隨著D取值的不斷增大，系統的附加平均隊長E[Ld]都是先增大而后趨于平穩保持不變，這是因為在D取值增大且超過某一值時，D所起的作用越來越小，系統的附加平均隊長幾乎由休假時間決定.

表6: λ =0.5, ρ=0.75, N =4，E[Ld]隨D 與T 的變化情況

圖6: E[Ld]隨D 與T 的變化情況

7 結束語

本文討論了服務員采取單重休假機制和系統采取Min(N,D,V)-控制策略的M/G/1 排隊系統，分析了系統隊長的瞬態分布和穩態分布，得到了穩態隊長的隨機分解結構和附加隊長分布的顯示表達式，進一步給出了一些特殊情形下的相關結果.另外，通過數值計算實例討論了系統基于單重休假和Min(N,D,V)-策略機制而引起的附加平均隊長E[Ld]隨著N,D和休假時間V的變化情況，使得本文的研究有更好的應用價值.