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

何亞興，唐應輝

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

1.引言

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

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

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

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

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

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

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

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

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

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

注2.1N(t)表示系統(tǒng)在時刻t的隊長，即時刻t在系統(tǒng)中的顧客數(shù);與分別表示相應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ài)概率，且t=0時只有一個顧客，“服務員忙期”b剛開始，即Q1(0)=1，Qj(0)=0，j ＞1.

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

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

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

其中

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

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

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

圖2.1

則按圖2.1所示進行分解為

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

圖2.2

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

圖2.3

圖2.4

② 假期到達人數(shù)大于等于N個，即服務員休假轉(zhuǎn)來之后發(fā)現(xiàn)系統(tǒng)中顧客人數(shù)為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)式，經(jīng)過整理可得到(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處于假期結(jié)束后的服務員閑期中)所示.

圖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所示.

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

圖2.10

則

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

同理

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

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

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

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

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

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

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

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

定理2.4令P延遲-Min(N，V)(z)表示該系統(tǒng)穩(wěn)態(tài)隊長分布的概率母函數(shù)，則當ρ ＜1時，有

而且平均隊長為

證由可得

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

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

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

其中

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

注2.2文[8]的母函數(shù)有誤，文[8]的母函數(shù)為

當z =1時，

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

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

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

3.費用模型下的最優(yōu)控制策略

建立如下的費用模型

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

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

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

服務員忙期的平均長度為

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

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

于是，系統(tǒng)長期運行單位時間內(nèi)所產(chǎn)生的成本期望費用為

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

于是

將(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，F(xiàn)N隨N的變化

表3.2 取R=100，h=5，λ=0.6，μ=0.8，ρ=0.75，α=0.8，θ =10，F(xiàn)N隨N的變化

圖3.1 取R=100，h=5，λ=0.6，μ=0.8，ρ=0.75，α=0.8，θ =0.1，F(xiàn)N隨N的變化

圖3.2 取R=100，h=5，λ=0.6，μ=0.8，ρ=0.75，α=0.8，θ =10，F(xiàn)N隨N的變化

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