帶單重工作休假和休假中斷的M/G/1排隊系統

盧國云，徐秀麗，王繼利，劉春平

(燕山大學 理學院 河北 秦皇島 066004)

帶單重工作休假和休假中斷的M/G/1排隊系統

盧國云，徐秀麗，王繼利，劉春平

(燕山大學 理學院 河北 秦皇島 066004)

研究單重工作休假和休假中斷的M/G/1排隊系統,得到了其嵌入Markov鏈的轉移概率矩陣，采用M/G/1型結構矩陣解析法，得到離去時刻穩態隊長的母函數的解析表達式.采用經典隨機分解方法，給出了隊長的條件隨機分解結構、條件等待時間的隨機分解結果、穩態等待時間的LST變換及穩態下平均等待時間等性能指標.給出數值例子，并討論了系統參數對幾個主要性能指標的影響，從而驗證了理論分析的合理性和有效性.

單重工作休假； 休假中斷；M/G/1型矩陣； 隨機分解

0 引言

現實生活中有很多休假排隊，在休假時服務員不是完全停止工作，而是以一個比正常服務率相對低一些的服務率工作，這樣的休假制度稱為工作休假.目前工作休假排隊系統，是國內外專家研究的重點[1-3].文獻[4]提出了休假中斷策略，考慮了具有離散時間的GI/Geo/1的多種工作休假及休假終止模型.

目前，研究單重工作休假排隊模型的不多，本文研究的是帶有單重工作休假和休假中斷策略的M/G/1排隊系統.當系統處于休假期，一旦有新顧客到達，以低速服務顧客，顧客離去后仍有顧客，則休假中斷，回到正常工作期，以高速率服務其他顧客.它的應用背景在于設置了低速運行期，從而減少運營成本降低能源消耗，考慮了休假中斷策略，增強了系統的應急能力，而且在多重工作休假的基礎上，縮短了休假時間，增加了系統閑期，以便接待隨時到達的顧客，提高系統收益和顧客滿意率.此外，本文使用隨機分解理論給出了帶單重工作休假和休假中斷排隊的M/G/1排隊及經典休假M/G/1排隊的關系，豐富了工作休假排隊理論.

1 模型描述與嵌入Markov鏈

在一個到達率為λ服務率為μb的經典M/G/1排隊系統中，同時引入單重工作休假和休假中斷策略.當一次服務完成，系統變空時，服務員開始長度為V的休假，V服從參數為θ的指數分布.如果在休假期內有顧客到達，服務員將以服務率μv接待顧客，而非完全停止服務.當休假期間的一個顧客服務完成，系統中仍有顧客，則服務員立即結束休假，以正常速率μb(μv<μb)服務其他顧客，即休假中斷發生,否則服務員繼續休假.同時，若休假結束系統中無顧客，服務員進入通常的閑期，直到有新顧客到達，以服務率μb開始一個正規忙期.此模型記為M/G/1(SWV,VI)模型,模型描述如下:

2)休假期間內的服務時間Sv獨立同分布, 具有一般分布函數Gv(x),且設LST變換，均值和k階矩分別為:

3)假設到達時間間隔、工作休假時間、正常服務期內的服務時間和工作休假期內的服務時間彼此獨立，且遵循FCFO的服務規則.

其中，bk(dk)表示V>Sv(V=Sv)，且在一次休假服務時間Sv內到達k個顧客的概率；vk表示V

因此，{bk,k≥0}，{vk,k≥0}和{dk,k≥0}是不完全概率分布,且有

顯然,

為考慮狀態0向其他狀態轉移的情況，引入記號α，α=P{V>T}，其中T表示到達間隔.

首先，考慮第n次顧客離去后瞬間系統中有顧客，則其轉移情況同無休假M/G/1排隊，有

P{Ln=m-1+j|Ln=m}=aj,j≥0,m≥1.

下面考慮狀態0的轉移情況

當V>T時，有3種情況造成離去時刻從狀態0轉移到j：(i)V>Sv，且在一次休假服務時間Sv內到達j個顧客；(ii)V

當V

P{Ln=j|Ln=0}=(1-α)aj+α(bj+cj+dj),j≥0.

2 穩態隊長及隨機分解

(1)

下面給出穩態隊長的母函數.

定理1當ρ<1時，離去時刻的穩態隊長的母函數為

L(z)=K(1-ρ){z[(1-α)A(z)+α(B(z)+C(z)+D(z))]-A(z)}/[z-A(z)],

(2)

證明對πk(k≥0)取母函數，且由(1)式有

進而得

L(z)=π0{z[(1-α)A(z)+α(B(z)+C(z)+D(z))]-A(z)}/[z-A(z)].

(3)

由正規化條件L(1)=1，可得

將π0代入(3)式，引入記號K，定理得證.

定理2若ρ<1，離去時刻穩態隊長L可以分解成兩個隨機變量之和L=L0+Ld，其中L0為經典M/G/1排隊在離去時刻的穩態隊長,附加隊長Ld的母函數表達式為Ld(z)=[1-Ψ(z)]/[Ψ′(1)(1-z)],其中,

Ψ(z)=z[(1-α)A(z)+α(B(z)+C(z)+D(z))]/A(z).

3 等待時間的隨機分解

定義S=0或1，取決于任一顧客以休假服務率服務完成或正常速率服務完成，在下面的穩態等待時間隨機分解中，將用到處于這兩種狀態的概率，因此，我們給出

Pb=P{S=1}=1-Pv

當顧客以正常服務速率服務完成時，剩余顧客即為此顧客等待時間Wb和正常服務時間Sb到達的顧客.因此，有

(4)

由條件概率可得

因此，任一顧客的穩態等待時間W的LST變換為:

4 數值例子

圖1 M/(M1,M2)/1(SWV,VI)系統中E(L)隨μv的變化趨勢Fig.1 The curves of E(L)with the change of μv in the M/(M1,M2)/1(SWV,VI)model

通過分析，我們得到了平均穩態隊長、平均等待時間的表達式.對于不同的系統，參數不同.當然，改變參數，例如降低服務速率μv，就會影響模型的隊長、等待時間等.所以，我們給出一些具體情況下的數值例子來說明模型可以有效地代表一些實際問題.

從圖1可看出，在3種不同的休假率θ下，平均隊長隨休假服務率μv的增大而減小；固定μv及其他特征，平均隊長隨θ的增大而減小，這是符合實際情形的.

而在實際問題中，為使系統性能更好，需選用不同的休假策略，在此，以兩種模型M/(M1,M2)/1(SWV,VI)和M/(M1,E2)/1(SWV,VI)對比，由圖2形象的給出了休假服務率μv對平均隊長及平均等待時間的影響.

圖2 不同模型的對比Fig.2 The comparison of different models

從圖2中可以分析出增大休假服務率μv，可以減少系統中聚集的顧客數以及等待時間，節省資源，達到充分利用的目的，同時給出了服從不同時間分布的平均隊長的對比.例子說明，根據實際情形，設置不同的休假策略，再適當改變μv,ρ(θ)的值，可以使系統性能提升.

[1] 田乃碩.休假隨機服務系統[M].北京:北京大學出版社,2001:148-165.

[2] Servi L D, Finn S G.M/M/1 queue with working vacations (M/M/1/WV)[J].Perform Evaluation,2002, 50(1):41-52.

[3] Wu D,Takagi H.M/G/1 queue with multiple working vacations[J].Perform Evaluation,2006,63(7):654-681.

[4] Li Jihong,Tian Naishuo.The discrete-time GI/Geo/1 queue with working vacation and vacation interruption[J].Applied Mathematics and Computation,2007,185(1):1-10.

[5] Neuts M.Matrix-Geometric Solutions in Stochastic Models[M].Baltimore:Johns Hopkins University Press, 1981:40-65.

[6] Shanthikumar T.On stochastic decomposition inM/G/1 type queues with generalized server vacations[J].Oper Res,1988,36(4):566-569.

M/G/1QueuewithSingleWorkingVacationandVacationInterruption

LU Guo-yun, XU Xiu-li, WANG Ji-li, LIU Chun-ping

(CollegeofScience,YanshanUniversity,Qinhuangdao066004,China)

AnM/G/1 queue system with a single working vacation and working interruption was studied.AnM/G/1-type transition probability matrix of the embedded Markov chain was obtained.And using theM/G/1-type matrix analysis method, the PGF of the stationary queue length for the customers at departure epochs was derived.By the classic stochastic decomposition solution, the stochastic decomposition results of the stationary queue length and the conditional waiting time were presented.And some performance measures of the system such as the LST of the stationary waiting time and the expected waiting time were also obtained.Numerical examples were presented to show the influence of the system parametes on several main performance characteristics,and the rationality and the effectiveness of the theoretical analysis were proved.

single working vacation; vacation interruption;M/G/1-type matrix; stochastic decomposition

O 226

A

1671-6841(2011)03-0006-05

2010-05-31

國家自然科學基金資助項目，編號10671170；河北省自然科學基金資助項目，編號F2008000864.

盧國云(1984-)，女，碩士研究生，主要從事排隊論研究，E-mail:luguoyun114@126.com.