張 杰

(阜陽師范學院 數(shù)學與統(tǒng)計學院，安徽 阜陽 236037)

帶休假延遲和啟動時間的M/M/1多重休假排隊系統(tǒng)分析

張 杰

(阜陽師范學院 數(shù)學與統(tǒng)計學院，安徽 阜陽 236037)

考慮了帶休假延遲和啟動時間的M/M/1多重休假排隊系統(tǒng)，運用QBD過程和矩陣幾何解等工具，給出過程穩(wěn)態(tài)隊長的具體形式，在此基礎上, 推導出穩(wěn)態(tài)條件下隊長和平穩(wěn)等待時間的隨機分解結構以及系統(tǒng)的附加隊長分布和附加延遲LST的具體形式. 并進一步得到系統(tǒng)處在各種狀態(tài)的概率和穩(wěn)態(tài)指標的均值。

M/M/1休假排隊；休假延遲；啟動時間；QBD過程；矩陣幾何解；隨機分解

近年來，休假排隊成為應用概率中的一個研究熱點，取得了有價值的結果[1-3]。帶啟動時間的排隊系統(tǒng)，在復雜通信網絡、計算機系統(tǒng)等諸多領域有著廣泛的應用，不同啟動機制及休假策略的連續(xù)時間排隊，得到了較為深入的研究[4-8]。休假延遲策略由Leung[9]提出并受到廣泛關注[10,11]。隨后，根據(jù)不同的應用背景，各種控制策略的M/M/1排隊得到了研究[12-14]。顏娜等[15]考慮了更一般的情形，即GI/M/1排隊模型。類似地，魏瑛源等[16]考慮了離散時間帶啟動和延遲排隊系統(tǒng)的隊長分布。特別的，[12-16]中模型均可看作搶占優(yōu)先權排隊[17]情形。王建軍[18]和李沛等[19]分別使用M/G/1型排隊系統(tǒng)結構矩陣解析法，討論顧客服務完離去后系統(tǒng)的穩(wěn)態(tài)指標。

本文主要考慮在一個M/M/1排隊系統(tǒng)中，引入帶有休假延遲和啟動時間的多重休假策略，利用QBD過程和由Netus發(fā)展的矩陣幾何解[20]方法，詳細分析了系統(tǒng)在穩(wěn)態(tài)條件下的隊長分布及其處在各種狀態(tài)的概率，推導出穩(wěn)態(tài)指標的隨機分解結果，并進一步得到附加隊長分布與附加延遲LST的具體形式和均值。

1 模型描述

考慮經典M/M/1排隊系統(tǒng)，即顧客到達時間間隔序列{τn,n≥1}獨立同分布F(t)=1-e-λt，t≥0；每個顧客的服務時間分布獨立，同參數(shù)為μ的負指數(shù)分布。系統(tǒng)一旦沒有顧客，服務臺首先開始1個隨機長度為D的休假延遲期，延遲時間服從參數(shù)為β的指數(shù)分布；休假延遲期如果有新的顧客達到，則服務臺立刻開始服務，直到系統(tǒng)又空出而再次進入休假延遲期；休假延遲期結束時若無顧客，服務臺開始休假；當一個休假期結束時，如果系統(tǒng)中無顧客，則服務臺開始另一次獨立同分布的休假，否則需要經歷一個啟動過程，這一時間A服從參數(shù)為α的負指數(shù)分布，啟動期結束后一個忙期正式開始；假定休假時間V服從參數(shù)為θ的指數(shù)分布。

假設到達間隔、休假延遲時間以及休假狀態(tài)與啟動時間之間均相互獨立。

設Q(t)表示系統(tǒng)在時刻t時的顧客數(shù)，

由模型假設易知{Q(t),J(t)}是具有狀態(tài)空間Ω={(0,0),(0,1)}∪{(k,j)|k≥1,j=0,1,2}的Markov過程，其中(0,1)表示處于服務臺休假延遲期，(k,0)(k≥0)表示服務臺在休假狀態(tài)且有k個顧客，(k,1)(k≥1)表示處于服務臺啟動期且系統(tǒng)中有k個顧客，(k,2)(k≥1)表示系統(tǒng)處于忙期且有k個顧客。

其中

R2B+RA+C=0

(1)

的最小非負解R，其中R稱為率陣。

引理2 QBD過程{Q(t),J(t)}是正常返的當且僅當ρ<1。

證明 由矩陣幾何解[20]可知，QBD過程{Q(t),J(t)}是正常返的當且僅當R的譜半徑SP(R)<1，并且線性方程組(x0,x1,x2,x3,x4)B[R]=0有正解。由于

2 穩(wěn)態(tài)隊長分布

當ρ<1時，設(Q,J)表示QBD過程{Q(t),J(t)}的穩(wěn)態(tài)極限。令

定理1 若ρ<1，則(Q,J)的穩(wěn)態(tài)概率分布由(2)式給出

證明 由矩陣幾何解方法，有(πk0,πk1,πk2)=(π10,π11,π12)Rk-1,k≥1，且

(π00,π01,π10,π11,π12)滿足(π00,π01,π10,π11,π12)B[R]=0。將B[R]代入，得到方程組

最后，使用正規(guī)化條件可以確定常數(shù)因子K。

由(2)式可知，系統(tǒng)穩(wěn)態(tài)時服務臺分別處于休假期、休假延遲期、啟動期和忙期的概率分布為

定理2 記Q表示此系統(tǒng)的穩(wěn)態(tài)隊長，則當ρ<1 時，Q可被分解為2個獨立的隨機變量之和：Q=Q0+Qd，其中Q0為無休假M/M/1經典排隊模型中相應的穩(wěn)態(tài)隊長，服從參數(shù)為1-ρ的幾何分布；Qd是帶休假延遲和啟動時間的M/M/1排隊系統(tǒng)的附加隊長，服從修正的幾何分布

P{Qd=k}=

可以證明δ1+δ2+rδ3+β′δ4=(K*)-1，因此，Qd(z)是一個PGF。把Qd(z)展成z的冪級數(shù)，得到附加顧客數(shù)Qd的分布。

3 平穩(wěn)等待時間

記穩(wěn)態(tài)時系統(tǒng)中顧客的等待時間為W，可以得到以下隨機分解結果：

定理3 假設采用FCFS規(guī)則進行服務，在平穩(wěn)狀態(tài)下，當ρ<1 時，帶有休假延遲和啟動時間的M/M/1排隊系統(tǒng)顧客的平穩(wěn)等待時間W可分解成2個相互獨立的隨機變量之和：W=W0+Wd，其中W0是標準M/M/1系統(tǒng)中顧客的等待時間，服從參數(shù)為μ(1-ρ)的指數(shù)分布；附加延遲Wd與W0相互獨立，其LST為

并服從修正的指數(shù)分布。其中

證明 由穩(wěn)態(tài)時系統(tǒng)中顧客數(shù)Q的PGF與等待時間W的LST之間的經典關系[21]，

由定理2，系統(tǒng)中顧客數(shù)Q的PGF為

推論2 平穩(wěn)狀態(tài)時平均附加延遲為

系統(tǒng)平穩(wěn)狀態(tài)時等待時間的均值為

4 小結

本文對帶有延遲休假期和啟動時間的多重休假M/M/1排隊系統(tǒng)進行了分析，推導出穩(wěn)態(tài)條件下的隊長和等待時間分布的母函數(shù)及其隨機分解結構，并給出附加隊長和附加延遲分布等系統(tǒng)排隊指標。這一模型為通信網絡等系統(tǒng)的優(yōu)化設計提供了理論基礎，具有一定的應用價值。另外，如何對模型進行完善使研究更具實用性，這些結果是否可以推廣到離散時間情形，是值得進一步研究的問題。

[1] Doshi B T. Queueing systems with vacations — A survey[J]. Queueing Systems, 1986, 1(1): 29-66.

[2] Takagi H. Vacation and priority systems[M]. 1st. Amsterdam: North-Holland, 1991: 107-119.

[3]Tian Naishuo, Zhang Gz. Vacation queueing models-theory and applications[M]. New York: Springer Verlag, 2006: 1-56.

[4] 田乃碩．PH-啟動時間的 GI/M/1排隊[J]．數(shù)學的實踐與認識，1993(4)：1-7．

[5] 蒲 會，唐應輝．帶啟動-關閉期的多重休假M/G/1排隊系統(tǒng)的隊長分布[J]．數(shù)學的實踐與認識，2011，41(10)：120-128．

[6] 劉名武，馬永開．啟動延遲N-策略批到達多重休假排隊[J]．數(shù)學的實踐與認識，2011，41(13)：137-143．

[7] 朱翼雋，劉海燕，王逢佳．帶啟動時間、N策略和負顧客的M/M/1工作休假排隊[J]．江蘇大學學報 (自然科學版)，2012，33(5)：616-620．

[8] 唐應輝，李沁洪，余玅妙．休假結束立即啟動的M/G/1單重休假排隊系統(tǒng)分析[J]．應用數(shù)學，2014，27(2)：447-456．[9] Leung, Kin K. On the Additional Delay in an M/G/1 Queue with Generalzed Vacations and Exhaustive Service[J]. Operations.Research，1992,40: 5272-5283.

[10]岳德權，趙 瑋．具有延誤休假的GI/M/1排隊系統(tǒng)[J]．運籌學雜志，1994，13(1)：33-38．

[11]Deng Y L, Braun W J, Zhao Y Q. M/M/1 queueing system with delayed controlled vacation[J]. 0R Transactions, 1999, 3(4): 17-30.

[12]徐秀麗，高 紅，田乃碩．對帶啟動時間和可變服務率的M/M/1休假排隊的分析[J]．應用數(shù)學學報，2008，31(4)：692-699．

[13]胡 彬，朱翼雋，周宗好．負顧客、帶啟動期和備用服務員的M/M/1休假排隊系統(tǒng)[J]．系統(tǒng)工程理論與實踐，2012，32(2)：349-354．

[14]徐祖潤，朱翼雋，羅海軍．帶關閉期和啟動期及負顧客的工作休假排隊[J]．江蘇大學學報(自然科學版)，2012，33(2)：244-248．

[15]顏 娜，吳云江．帶有啟動時間和單重工作休假的GI/M/1排隊系統(tǒng)分析[J]．工程數(shù)學學報，2014，31(4)：529-538．

[16]魏瑛源，唐應輝．帶啟動時間的延遲N-策略Geo/G/1排隊系統(tǒng)的隊長分布及容量的優(yōu)化設計[J]．高校應用數(shù)學學報A輯，2013，28(4)：391-405．

[17]張宏波，史定華．M/M/1搶占優(yōu)先權排隊平穩(wěn)指標的尾部分析[J]．系統(tǒng)科學與數(shù)學，2014，34(1)：1-9．

[18]王建軍，楊德禮．帶啟動-關閉期的多重休假M/G/1排隊[J]．燕山大學學報，2005，29(1)：8-12．

[19]李 沛，徐秀麗，曹學云，等．帶啟動一關閉期和N策略的多重休假M/G/1排隊[J]．數(shù)學的實踐與認識，2011，41(13)：145-149．

[20]Netus M. Matrix-Geometric solutions in stochastic models[M]. Baltimore: the johns hopkins university press, 1981: 80-120.

[21]Keilson J, Servi L D. A distributional form of Little's Law[J]. Operations Research Letters, 1988, 7(5): 223-227.

Analysis of multiple vacation M/M/1 queue with delayed vacation and setup time

ZHANG Jie

(SchoolofMathematicsandStatistics,FuyangNormalUniversity,FuyangAnhui236037,China)

This paper considers an M/M/1 queue system with multiple vacation,delayed vacation and setup time. By applying quasi-birth-death (QBD) process and matrix-geometric solution method, the analytic expression of the stationary queue length and stochastic decomposition structures of the stationary queue length and waiting time are given. Meanwhile, it is demonstrated that the additional queue length and the expression of the laplace-stieltjes transformation of additional delay. Moreover, expectation of stationary indices, the steady state probabilities that the system in vacation delay, vacation period, setup time and busy period are calculated respectively.

M/M/1 queue with vacation；delayed vacation；setup time；quasi birth and death process;matrix-geometric solution；stochastic decomposition

2015-01-16

國家特色專業(yè)(TS11496)；安徽省高校自然科學研究項目(KJ2014ZD21)；阜陽師范學院優(yōu)秀重點學科(2010XK6-03)；阜陽師范學院質量工程項目(2014JXTD01)資助。

張 杰(1981-)女，碩士，講師，研究方向：隨機運籌學。

O226

A

1004-4329(2015)03-021-04

10.14096/j.cnki.cn34-1069/n/1004-4329(2015)03-021-04