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

何亞興，唐應(yīng)輝

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

1.引言

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

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

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

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

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

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

2.隊(duì)長(zhǎng)的瞬態(tài)分布和穩(wěn)態(tài)分布

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

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

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

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

令b〈i〉表示從i個(gè)顧客開始的“服務(wù)員忙期”長(zhǎng)度，因?yàn)榈竭_(dá)過(guò)程是泊松過(guò)程，所以有分布P{b〈i〉≤t}=B(i)(t)，t ≥0，i ≥1.

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

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

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

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

其中

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

上式第三項(xiàng)實(shí)際上可以分成延遲期有顧客到達(dá)和無(wú)顧客到達(dá)兩種情況:

1) (2.4)式中第一項(xiàng)就為延遲期有顧客到達(dá)，則到達(dá)一個(gè)顧客后服務(wù)員就立即結(jié)束延遲期進(jìn)入忙期為顧客服務(wù)，如圖2.1所示

圖2.1

則按圖2.1所示進(jìn)行分解為

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

圖2.2

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

圖2.3

圖2.4

② 假期到達(dá)人數(shù)大于等于N個(gè)，即服務(wù)員休假轉(zhuǎn)來(lái)之后發(fā)現(xiàn)系統(tǒng)中顧客人數(shù)為n(n ≥N)個(gè)，則立即為顧客服務(wù)，如圖2.5所示

圖2.5

于是

(2.6)式中第一項(xiàng)為

(2.6)式中第二項(xiàng)為

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

同理，對(duì)i ≥1，有

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

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

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

1) 當(dāng)j =1，2，···N -1時(shí)，

2) 當(dāng)j ≥N時(shí)，

其中

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

證當(dāng)j = 1，2，··· ，N -1時(shí)，“時(shí)刻t隊(duì)長(zhǎng)為j”當(dāng)且僅當(dāng)“時(shí)刻t落在服務(wù)員假期中且隊(duì)長(zhǎng)為j”或者“時(shí)刻t落在服務(wù)員忙期中且隊(duì)長(zhǎng)為j”，類似定理2.1的分解，得

(2.18)式中的第一項(xiàng)表示時(shí)刻t處于第一個(gè)服務(wù)員忙期中且隊(duì)長(zhǎng)為j的概率，第二項(xiàng)表示在延遲期中有顧客到達(dá)時(shí)，時(shí)刻t處于第一個(gè)服務(wù)員忙期之后且隊(duì)長(zhǎng)為j的概率.

當(dāng)延遲期無(wú)顧客到達(dá)時(shí)服務(wù)員就立刻休假，(2.18)式中的第三項(xiàng)表示無(wú)論假期中到達(dá)多少個(gè)顧客，時(shí)刻t處于下一個(gè)服務(wù)員忙期之前且隊(duì)長(zhǎng)為j的概率，如圖2.6(時(shí)刻t 處于假期中)，圖2.7(時(shí)刻t處于假期結(jié)束后的服務(wù)員閑期中)所示.

圖2.6

圖2.7

進(jìn)一步(2.18)式中的第三項(xiàng)為

第四項(xiàng)表示假期到達(dá)n(0 ≤n ≤N -1)個(gè)顧客，t落在下一個(gè)“服務(wù)員忙期”開始之后且隊(duì)長(zhǎng)為j的概率，如圖2.8(假期中無(wú)顧客到達(dá))，圖2.9(假期中到達(dá)n(0 ＜n ≤N -1)個(gè))所示.

圖2.8

圖2.9

則

第五項(xiàng)表示假期中到達(dá)n(n ≥N)個(gè)顧客，t落在下一個(gè)“服務(wù)員忙期”開始之后且隊(duì)長(zhǎng)為j的概率，如圖2.10所示.

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

圖2.10

則

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

同理

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

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

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

當(dāng)j ≥N時(shí)，“時(shí)刻t隊(duì)長(zhǎng)為j”當(dāng)且僅當(dāng)“時(shí)刻t落在服務(wù)員假期中且隊(duì)長(zhǎng)為j”或者“時(shí)刻t落在服務(wù)員忙期中且隊(duì)長(zhǎng)為j”，同理得

余下證明過(guò)程類似1 ≤j ＜N時(shí)的推導(dǎo)過(guò)程，證畢.

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

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

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

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

而且平均隊(duì)長(zhǎng)為

證由可得

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

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

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

其中

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

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

當(dāng)z =1時(shí)，

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

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

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

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

建立如下的費(fèi)用模型

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

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

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

服務(wù)員忙期的平均長(zhǎng)度為

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

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

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

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

于是

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

實(shí)例取服務(wù)時(shí)間χ的分布G(t) = 1-e-μt，延遲期Y 的分布Y (t) = 1-e-αt，t ≥0，休假時(shí)間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上看出，當(dāng)休假時(shí)間V 參數(shù)θ固定時(shí)，隨著N的增大，F(xiàn)N呈現(xiàn)先減小后增大的趨勢(shì)，θ =0.1時(shí)，在N =6的時(shí)候FN取得最小值41.728433; θ =10時(shí)，在N =3的時(shí)候FN取得最小值26.000012.