具有N-策略和延遲單重休假且休假不中斷的M/G/1排隊系統

何亞興，唐應輝

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

1.引言

在對具有經典N-策略、T-策略、D-策略控制的排隊模型的研究基礎上[1-8]，隨著研究的深入和實際應用，一些具有聯合控制的排隊模型也得到了學者們的關注[9-18].文[9]把N-策略和服務員多重休假結合，研究了有Min(N，V)-策略控制的M/G/1排隊系統，而且服務員的休假是可以中斷的，即在服務員的假期中，如果到達的顧客數達到事先設定的正整數閾值N，服務員立即中斷該次休假回到系統為顧客服務，這種在服務員的休假可以中斷的情況下，系統在達到穩態時服務員忙期開始的顧客數不超過N個，文[9]利用穩態隊長的隨機分解結構給出了穩態隊長分布的概率母函數，從而得到平均隊長的表達式.文[10]繼續討論該模型，不僅討論了從任意初始狀態出發的瞬態隊長分布，獲得了瞬態隊長分布關于時間t的Laplace變換表達式，而且使用洛必達法則，經過簡單計算獲得了穩態隊長分布的遞推表達(通過母函數是很難得到穩態隊長分布的表達式的)，而獲得便于做數值計算的穩態隊長分布表達式在系統容量的優化設計中有重要意義.文[11]把N-策略與服務員的單重休假結合起來，研究了服務員具有單重休假且休假可中斷和系統采取Min(N，V)-策略控制的排隊系統.文[12]從任意初始狀態出發，詳細研究了具有Min(N，D)-策略控制的M/G/1排隊系統，其中服務員具有多重休假且休假可中斷，應用更新過程理論和全概率分解技術，不僅得到了系統隊長的瞬態分布關于時間t的Laplace變換表達式，而且得到了便于作數值計算的隊長穩態分布的遞推表達式，并通過隊長穩態分布的數值計算討論了系統容量的優化設計問題，然后在建立費用結構模型基礎上，通過數值計算例子討論了最優控制策略(N*，D*).文[13]將Min(N，V)-策略引入到離散時間的Geo/G/1排隊系統中.文[14]把N-策略和服務員多級適應休假結合，推廣了文[9-11]的研究模型.由于服務設備(服務臺)在運行過程會因為老化磨損等原因發生故障，因此文[15]研究了具有溫儲備失效特征和單重休假Min(N，V)-策略的M/G/1可修系統排隊系統，并用數值計算例子討論了最優控制策略N*.文[16-17]和[18]分別將N-策略、D-策略和服務員的單重(多重)休假機制結合，引入具有二維策略控制的Min(N，D)-控制策略，提出建立了系統具有Min(N，D，V)-策略控制的M/G/1排隊系統模型.

但是，在以上有策略控制和服務員休假機制的排隊系統研究中，大多文獻都假定服務員根據系統所采取的控制策略可中斷休假.事實上，在實際中情況并非完全如此，例如服務員休假的地方離工作單位較遠，或者所從事的輔助工作不能立即中斷，此時需等待服務員長途歸來或完成輔助工作后才能回到系統為顧客服務.文[8]研究了N-策略和服務員單重休假且休假不中斷的M/G/1排隊系統模型，運用更新過程理論，全概率分解技術和Laplace變換工具，研究了系統隊長的瞬態分布和穩態分布，但有關結果是錯誤的.另外，在我們的實際生活當中，有很多的休假排隊系統是在服務員完成服務和系統變空以后，不能立刻去休假的，而是要經過一段準備休假的延遲時間，這段時間是很有必要的，如銀行或者很多商店在下班之前，會清點一下賬目或清點貨物或者整理器材等等，如果在這一段時間又有顧客到達，為了不損失顧客和提升信譽，他們又會接待顧客，接待完以后，又得重新清點賬目或者整理器材，直到清點完以后也沒有顧客到達，才開始去休假.因此，基于上述，本文把“延遲休假”、“N-策略”、“服務員單重休假且休假不中斷”這三者結合，提出建立如下排隊系統模型:

1) M/G/1型的排隊系統:顧客相繼到達的時間間隔τ有分布F(t) = 1-e-λt，顧客的服務時間χ是任意分布G(t)，記平均服務時間為1/μ(0 ＜μ＜∞);

2) 服務員采取延遲單重休假且休假不中斷機制，服務的啟動是實行N-策略控制:每當系統變空時，服務員不是立即去休假，而是有“延遲時間”Y(隨機的)，“延遲時間”Y 服從任意分布Y(t).如果有顧客在延遲時間Y 內到達，服務員立即為顧客服務，直到系統再次變空再重新做休假準備; 如果沒有顧客在延遲時間Y 內到達，則延遲時間結束以后服務員立刻去休假一次，休假時間V 服從任意分布V(t).當服務員休假轉來，系統中等待服務的顧客數大于或者等于事先設定的正整數閾值N個，服務員立刻啟動系統設備為顧客服務，直到系統再次變空; 若發現系統中等待服務的顧客數小于N個，則服務員就待在系統中處于空閑狀態(在崗)直到系統內到達顧客數達到N個再啟動系統設備為顧客服務;

3) 所涉及隨機變量τ、χ、Y、V 是相互獨立的.

另外，根據實際情況，進一步假設在t = 0時，如果系統中無顧客，服務員就待在系統中直到第一個顧客到達，而且立即服務，也就說，只有在服務員繁忙一段時間以后才實行延遲單重休假且休假不中斷機制和系統啟動服務的N-策略控制(這種假設更符合實際情況).

2.隊長的瞬態分布和穩態分布

首先，一個“系統閑期”是指從系統剛變空的時刻起，直到其后第一個顧客到達的時刻為止的這一段時間.如果用表示第j個“系統閑期”長度，則由于到達過程為參數λ(＞0)的Poisson過程易知“系統閑期”的分布為=F (t)=1-e-λt，j ≥1.

其次，一個“服務員忙期”是指從服務員開始為顧客服務的時刻起，直到系統再次變空為止的這一段時間.若令b表示該系統從一個顧客開始的“服務員忙期”長度，B(t)=P {b ≤t}，則有如下引理:

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

注2.1N(t)表示系統在時刻t的隊長，即時刻t在系統中的顧客數;與分別表示相應G(t)的拉普拉斯(L)變換和拉普拉斯-斯蒂爾切斯(LS)變換;G(k)(t)表示相應G(t)的k重卷積，

令b〈i〉表示從i個顧客開始的“服務員忙期”長度，因為到達過程是泊松過程，所以有分布P{b〈i〉≤t}=B(i)(t)，t ≥0，i ≥1.

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

引理2.2[6]令為Qj(t)的L變換，對?(s)＞0和j ≥1，有

下面討論系統隊長的瞬態和穩態的概率分布.令pij(t) = P {N(t)=j|N(0)=i}表示在初始時刻有i個顧客的條件下，在時刻t隊長為j的瞬態概率，

定理2.1對?(s)＞0和i ≥1，有

其中

證令顯然隊長為零的充要條件是時刻t處于系統閑期中，運用全概率分解技術，有

上式第三項實際上可以分成延遲期有顧客到達和無顧客到達兩種情況:

1) (2.4)式中第一項就為延遲期有顧客到達，則到達一個顧客后服務員就立即結束延遲期進入忙期為顧客服務，如圖2.1所示

圖2.1

則按圖2.1所示進行分解為

2) (2.4)式中第二項為延遲期無顧客到達，延遲期結束以后服務員立刻休假，如圖2.2所示

圖2.2

① 假期到達人數不足N個，即休假期中到達n(0 ≤n ≤N -1)個，則服務員休假轉來處于待崗狀態，直到后面再到達N -n個，才開始為顧客服務.假期無顧客到達與休假期到達n(0 ＜n ≤N -1)個分別如圖2.3，圖2.4所示

圖2.3

圖2.4

② 假期到達人數大于等于N個，即服務員休假轉來之后發現系統中顧客人數為n(n ≥N)個，則立即為顧客服務，如圖2.5所示

圖2.5

于是

(2.6)式中第一項為

(2.6)式中第二項為

將(2.4)-(2.8)式代入(2.3)式整理得到

同理，對i ≥1，有

對(2.9)-(2.10)式作L變換，得

再將(2.13)代入(2.11)式，經過整理可得到(2.1)式，再把(2.1)代入(2.13)式可得(2.2)式，證畢.

定理2.2對?(s)＞0和i ≥1，有

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

2) 當j ≥N時，

其中

Δ(s)，AN(s)如定理2.1所述.

證當j = 1，2，··· ，N -1時，“時刻t隊長為j”當且僅當“時刻t落在服務員假期中且隊長為j”或者“時刻t落在服務員忙期中且隊長為j”，類似定理2.1的分解，得

(2.18)式中的第一項表示時刻t處于第一個服務員忙期中且隊長為j的概率，第二項表示在延遲期中有顧客到達時，時刻t處于第一個服務員忙期之后且隊長為j的概率.

當延遲期無顧客到達時服務員就立刻休假，(2.18)式中的第三項表示無論假期中到達多少個顧客，時刻t處于下一個服務員忙期之前且隊長為j的概率，如圖2.6(時刻t 處于假期中)，圖2.7(時刻t處于假期結束后的服務員閑期中)所示.

圖2.6

圖2.7

進一步(2.18)式中的第三項為

第四項表示假期到達n(0 ≤n ≤N -1)個顧客，t落在下一個“服務員忙期”開始之后且隊長為j的概率，如圖2.8(假期中無顧客到達)，圖2.9(假期中到達n(0 ＜n ≤N -1)個)所示.

圖2.8

圖2.9

則

第五項表示假期中到達n(n ≥N)個顧客，t落在下一個“服務員忙期”開始之后且隊長為j的概率，如圖2.10所示.

我說：“這下你知道孩子為什么磨蹭了吧？”她很驚訝地說：“難道是因為我嗎？不會吧！我每天都在催他做事情呀！我對他要求很嚴的！我現在之所以覺得應該找點事情做，是不想讓我兒子看不起我！”

圖2.10

則

將(2.19)-(2.21)式代入(2.18)式整理得

同理

對(2.22)-(2.23)式作L變換，得

由(2.24)-(2.25)式得到p0j(s)，pij(s)的關系式為

再將(2.26)式代入(2.24)式，經過整理化簡可得到(2.14)式，再將(2.14)式代入(2.26)式，得證(2.15)式.

當j ≥N時，“時刻t隊長為j”當且僅當“時刻t落在服務員假期中且隊長為j”或者“時刻t落在服務員忙期中且隊長為j”，同理得

余下證明過程類似1 ≤j ＜N時的推導過程，證畢.

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

證由下面求事實上，當＞1或ρ =注意到此時或且E(b) = ∞以及與當E(b)=∞，有

再將(2.34)-(2.35)式代入(2.33)式中，即可完成證明.

定理2.4令P延遲-Min(N，V)(z)表示該系統穩態隊長分布的概率母函數，則當ρ ＜1時，有

而且平均隊長為

證由可得

將(2.39)-(2.41)式代入(2.38)式整理得(2.36)式，再由經過計算即得(2.37)式.

定理2.5本文研究的具有N-策略和延遲單重休假且休假不中斷的M/G/1排隊系統的穩態隊長可以分解成獨立的兩部分之和: 一部分是經典排隊系統的穩態隊長，一部分是由N-策略延遲單重休假且休假不中斷的策略機制引起的附加隊長Ld，且附加隊長Ld有如下離散分布

證由上面定理2.4可知本文研究的排隊系統的穩態隊長可分解成獨立的兩部分之和，下面證明附加隊長有上式的離散分布，令

其中

推論2.1當P {Y =0} = 1時，本文研究的系統就成為了N-策略單重休假且休假不中斷的M/G/1排隊系統，即文[8]中研究的系統，在上述所有結論中由y(λ)=1，有

注2.2文[8]的母函數有誤，文[8]的母函數為

當z =1時，

文[8]的正確的母函數即為(2.45)式.

推論2.2當P {Y =∞} = 1時，本文研究的系統就成為了經典的M/G/1排隊系統，在上述所有結論中令y(λ)=0即得到與文[6]完全一致的結論.

推論2.3當P {V =0}=1，本文研究的系統就成為了延遲N-策略M/G/1排隊系統，在上述所有結論中令V (t)=1，v(λ(1-z))=1，即得到與文[7]完全一致的結論.

3.費用模型下的最優控制策略

建立如下的費用模型

1) R: 系統(服務臺)在一個更新周期內的固定消耗(或系統啟動)費用;

2) h: 一個顧客在系統中逗留(包括等待和服務)單位時間的成本費用.

記FN為延遲單重休假且休假不中斷和N-策略的控制機制下系統長期運行單位時間內所產生的成本期望費用.由更新報酬過程理論知

服務員忙期的平均長度為

由于服務員忙期開始時在系統內的顧客數為上一個“服務員非忙期”內到達的顧客數，而顧客到達過程是參數λ的泊松過程，因此“服務員非忙期”的平均長度為

故系統一個更新周期(由一個“服務員忙期”和一個“服務員非忙期”構成)的平均長度為

于是，系統長期運行單位時間內所產生的成本期望費用為

下面計算服務員忙期開始時系統中的平均顧客數E(Qb).而Qb的分布，經計算，可得

于是

將(2.37)，(3.5)式代入(3.1)式得

實例取服務時間χ的分布G(t) = 1-e-μt，延遲期Y 的分布Y (t) = 1-e-αt，t ≥0，休假時間V 的分布V (t)=1-e-θt，則

表3.1 取R=100，h=5，λ=0.6，μ=0.8，ρ=0.75，α=0.8，θ =0.1，FN隨N的變化

表3.2 取R=100，h=5，λ=0.6，μ=0.8，ρ=0.75，α=0.8，θ =10，FN隨N的變化

圖3.1 取R=100，h=5，λ=0.6，μ=0.8，ρ=0.75，α=0.8，θ =0.1，FN隨N的變化

圖3.2 取R=100，h=5，λ=0.6，μ=0.8，ρ=0.75，α=0.8，θ =10，FN隨N的變化

從表3.1，表3.2，圖3.1和圖3.2上看出，當休假時間V 參數θ固定時，隨著N的增大，FN呈現先減小后增大的趨勢，θ =0.1時，在N =6的時候FN取得最小值41.728433; θ =10時，在N =3的時候FN取得最小值26.000012.