分析M/M/1多重工作休假排隊的一種新方法

張宏波，鄭群珍，史定華

（1.河南教育學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，河南鄭州450046；2.上海大學(xué)理學(xué)院，上海200444）

?

分析M/M/1多重工作休假排隊的一種新方法

張宏波1，鄭群珍1，史定華2

（1.河南教育學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，河南鄭州450046；
2.上海大學(xué)理學(xué)院，上海200444）

用一種新方法對經(jīng)典的M/M/1工作休假排隊系統(tǒng)建立模型.對該模型，用無限位相GI/M/1型Markov過程和矩陣解析方法進行分析，不但得到了所討論排隊模型平穩(wěn)隊長分布的具體結(jié)果，還給出了平穩(wěn)狀態(tài)時服務(wù)臺具體位于第幾次工作休假的概率.這些關(guān)于服務(wù)臺狀態(tài)更為精確的描述是該排隊系統(tǒng)的新結(jié)果.

M/M/1排隊；工作休假；GI/M/1型Markov過程；矩陣幾何解；差分方程

§1　引　言

因為服務(wù)臺休假可以使服務(wù)臺的空閑狀態(tài)得到有效的利用以免資源浪費，因而帶有各種休假策略的排隊模型在一些實際隨機服務(wù)系統(tǒng)中有著重要的應(yīng)用，成為排隊論的一個研究熱點.詳細的介紹可以參見綜述論文［1］或?qū)Ｖ?］及其中引用的文獻.

Servi［3］最先引進了工作休假策略.在這種情形下，與普通休假不一樣，在工作休假期，服務(wù)臺不是完全停止工作，而是為在此期間到達系統(tǒng)的顧客以較低的服務(wù)率提供服務(wù). Servi研究了多重工作休假的M/M/1排隊，得到了平穩(wěn)隊長的PGF和平穩(wěn)逗留時間的LST.后來，劉等［4］用擬生滅（QBD）過程與矩陣幾何解的方法研究了該模型，得到了相應(yīng)平穩(wěn)指標(biāo)的解析結(jié)果以及隨機分解結(jié)構(gòu).另外，應(yīng)用矩陣解析方法，田等［5］研究了單重工作休假的M/M/1排隊，李［6］，Baba［7］研究了顧客成批到達的M/M/1單重工作休假排隊和多重工作休假排隊.最后，對到達率或服務(wù)率服從一般分布的模型也有不少研究，例如，Baba［8］討論了GI/M/1多重工作休假排隊而Wu［9］討論了M/G/1多重工作休假排隊模型.最后，關(guān)于工作休假排隊模型的詳細介紹還可以參見綜述文章［10］.

對經(jīng)典的M/M/1多重工作休假排隊模型，在［4］中，把系統(tǒng)中的顧客數(shù)作為水平，把服務(wù)臺的狀態(tài)作為位相，作者對該排隊系統(tǒng)建立了無限水平有限位相的QBD過程模型，因為這時服務(wù)臺要么位于正規(guī)忙期，要么位于工作休假狀態(tài)，所以這時建立的QBD過程的位相只取2個不同值.然而，對這樣建立的模型，在分析系統(tǒng)的平穩(wěn)特征時，對服務(wù)臺的具體狀態(tài)，只能得到服務(wù)臺位于工作休假的概率.但對多重工作休假，因服務(wù)臺可以進行多次休假，所以往往還關(guān)心服務(wù)臺具體位于第幾次休假（或已經(jīng)進行了幾次休假）的概率，這一問題用［4］中的模型無法回答.因此，在本文中，對該排隊系統(tǒng)應(yīng)用無限位相GI/M/1型Markov過程重新建模，通過對該過程求解，不但可得該模型的經(jīng)典結(jié)果如平穩(wěn)隊長分布等，還對上述問題作了回答.所得新結(jié)果使得對服務(wù)臺狀態(tài)的刻畫更為具體.

本文的主要貢獻包括兩方面.首先，用新方法對M/M/1多重工作休假建模，且對建立的無限位相GI/M/1型Markov過程，得到了平穩(wěn)分布的解析結(jié)果；其次，得到了所研究排隊系統(tǒng)的一些新結(jié)果，這些結(jié)果用［3］或［4］中的方法不能得到.在以下各節(jié)中，首先在§2給出所研究排隊系統(tǒng)的一個新模型.然后在§3對模型求解，并對本文討論的排隊系統(tǒng)進行了分析.最后，§4是小結(jié)部分.

§2　模型描述

對經(jīng)典的M/M/1多重工作休假排隊系統(tǒng)，假設(shè)其到達率為λ而服務(wù)率為μ.另外，假設(shè)休假時間服從參數(shù)為θ的指數(shù)分布，且在休假期，系統(tǒng)為到達的顧客提供服務(wù)的速率為η，其中η＜μ.

令L（t）表示時刻t時系統(tǒng)中的顧客數(shù)，用J（t）表示時刻t時服務(wù)臺的狀態(tài)，且規(guī)定J（t）= 0表示服務(wù)臺位于正規(guī)忙期，而對k≥1，J（t）= k表示服務(wù)臺位于工作休假狀態(tài)且恰好位于第k次休假.現(xiàn)在考慮二維Markov過程｛J（t），L（t），t≥0｝，其狀態(tài)空間為

其中對l≥1，狀態(tài)（0，l）表示服務(wù)臺位于正規(guī)忙期且這時系統(tǒng)中有l(wèi)個顧客；對j≥1及l(fā)≥0，狀態(tài)（j，l）表示服務(wù)臺位于第j次工作休假且系統(tǒng)中有l(wèi)個顧客.

如果把狀態(tài)按字典規(guī)則排序，則上述Markov過程的無窮小生成元具有如下所示的分塊矩陣形式

其中

因此，所建立過程是一個無限位相GI/M/1型Markov過程［11-12］.

由［3］或［4］，當(dāng)λ＜μ時排隊系統(tǒng)穩(wěn)定，因而這時Markov過程｛J（t），L（t），t≥0｝的平穩(wěn)分布存在.如果把平穩(wěn)分布記為（π0，π1，π2，···，），其中分量π0=（π01，π02，···，）和

都是無窮維向量，則這時由［11-12］知平穩(wěn)分布滿足如下所示的算子幾何解

其中R是一個無窮維矩陣，稱為率算子且對本文所討論的情形，它是下述矩陣方程的最小非負(fù)解

另外，初始向量π0和π1由線性方程組

以及規(guī)一化條件共同確定.

§3　系統(tǒng)穩(wěn)態(tài)特征分析

本小節(jié)對所建立的模型求解，并對排隊系統(tǒng)的穩(wěn)態(tài)特征進行分析.為了求解模型，首先給出率算子R以及初始分量π0和π1，有下述兩個引理:

引理3.1率算子R的具體形式如下所示

其中

是一個常數(shù).

證由率算子的概率解釋［11］可知對本文討論的模型，R除了第一行外其余各行元素皆為0.現(xiàn)在令（r0，r1，···）表示其第一行，則通過簡單的代數(shù)運算可知方程（2）的分量形式為其中方程（7）是一個二階線性齊次差分方程，且特征方程為ηr2-（λ+η+θ）r +λ= 0，從而易得兩個特征根為因此

這里c1和c2都是待定常數(shù).另外，由常規(guī)的代數(shù)運算容易驗證r1∈（0，1），r2＞1，所以為了得到方程（2）的最小非負(fù)解，常數(shù)c2必須為0，因而由（6）可知

其中由r1的定義可以驗證上述最后一個等式成立.最后再把r1記作r即得引理結(jié)論.引理3.2如果λ＜μ，則初始向量π0和π1由以下兩式給出

證前文已經(jīng)指出，π0和π1滿足線性方程組（3）和（4）.現(xiàn)在，由（5）出發(fā)可以驗證

所以有

因而方程（3）的分量形式為

類似地，方程（4）的分量形式為

（是排隊系統(tǒng)的交通強度.

方程（15）是一個2階齊次差分方程，由類似于引理1中的方法可得其收斂解為

因而π11= rπ10，代入（14）可得π10（ηr -λ-θ）+μπ01= 0，再由（8）式又可得

由此即得（10）式.

最后，由π1n的表達式和（13）式可得

這是一個非齊次差分方程，且當(dāng)λ＜μ時，易求得其唯一收斂解為

其中A是一個待定常數(shù)而ρ?λμ.現(xiàn)在，令k = 1則有

所以由（16）可知

代入（17）并經(jīng)過簡單計算即可得（9）式.

在引理1和2的基礎(chǔ)上，現(xiàn)在給出本文的兩個主要結(jié)論如下:

定理3.1令bn表示平穩(wěn)狀態(tài)時服務(wù)臺位于正規(guī)忙期且系統(tǒng)中有n個顧客的概率，令wk表示平穩(wěn)狀態(tài)時服務(wù)臺位于工作休假狀態(tài)且恰好處于第k次休假的概率，則有

其中

是一個常數(shù).

證首先給出所討論Markov過程的平穩(wěn)分布.由算子幾何解（1）和（10），（11）兩式，有

因此由規(guī)一化條件易求得最后，記π10為K，再由bn=π0n和wk=和引理3.2，可得定理的結(jié)論.

注3.1令pB和pW分別表示平穩(wěn)狀態(tài)時服務(wù)臺位于忙期和工作休假狀態(tài)的概率，則由定理3.1可知

通過直接驗證知，這與［4］中所得結(jié)果一致.

定理3.2令L表示平穩(wěn)狀態(tài)時系統(tǒng)中的顧客數(shù)，則有

其中K的定義見定理3.1.

證由顯然的事實

出發(fā)，經(jīng)過計算易得.

注3.2在方程（20）的基礎(chǔ)上，可以進一步討論該排隊模型平穩(wěn)隊長和平穩(wěn)逗留時間的隨機分解結(jié)果.然而這并不是本文的主要目的，相應(yīng)的結(jié)論可以參見［4］.

§4　小結(jié)

本文用一種新方法討論了經(jīng)典的M/M/1多重工作休假排隊，給出了一些新結(jié)論，它們對排隊模型平穩(wěn)狀態(tài)時服務(wù)臺的狀態(tài)進行了更為細致的刻畫，因而具有重要的意義.

另外，應(yīng)用本文方法還可以對其它M/M/1多重工作休假排隊模型進行研究，如顧客成批到達或成批服務(wù)的排隊，到達率或服務(wù)率依賴于當(dāng)前系統(tǒng)中顧客數(shù)排隊等，這些都是有意義的值得進一步研究的問題.

［1］Doshi B. Queueing systems with vacations-a survey［J］. Queueing Systems，1989，1: 29-66.

［2］Tian Naishuo，Zhang Zhe George. Vacation queueing models-theory and applications［M］. New York: Springer，2006.

［3］Servi L，F(xiàn)inn S. M/M/1 queues with working vacations（M/M/1/WV）［J］. Performance Evaluation，2002，50: 41-52.

［4］Liu Wenyuan，Xu Xiuli，Tian Naishuo. Stochastic decompositions in the M/M/1 queue with working vacations［J］. Operations Research Letters，2007，35: 595-600.

［5］Tian Naishuo，Zhao Xinqiu，Wang Kaiyu. The M/M/1 queue with single working vacation［J］. International Journal of Information and Management Sciences，2008，19: 621-634.

［6］Li Jihong，Zhang Zhe George，Tian Naishuo. Analysis for the MX/M/1 working vacation queue［J］. International Journal of Information and Management Sciences，2009，20: 379-394.

［7］Baba Y. The MX/M/1 queue with multiple working vacation［J］. American Journal of Operations Research，2012，2: 217-224.

［8］Baba Y. Analysis of a GI/M/1 queue with multiple working vacations［J］. Operations Research Letters，2005，33: 201-209.

［9］Wu Da，Takagi H. M/G/1 queue with multiple working vacations［J］. Performance Evaluation，2006，63: 654-681.

［10］Tian Naishuo，Li Jihong，Zhang Zhe George. Matrix analytic method and working vacation queues- a survey［J］. International Journal of Information and Management Sciences，2009，20: 603-633.

［11］Miller D R. Computation of steady-state probabilities for M/M/1 priority queue［J］. Operations Research，1981，29: 945-958

［12］Li Quanlin. Constructive computation in stochastic models with applications，the RG-factorizations［M］. Beijing: Tsinghua University Press，2010.

MR Subject Classification: 60K25；90B22

A new approach for analyzing the M/M/1 queue with multiple working vacations

ZHANG Hong-bo1，ZHENG Qun-zhen1，SHI Ding-hua2
（1. School of Mathematics and Statistics，Henan Institute of Education，Zhengzhou 450046，China；
2. College of Sciences，Shanghai University，Shanghai，200444，China）

A new approach to model the M/M/1 queue with multiple working vacations is provided. By the GI/M/1 type Markov process and matrix analytic method，the explicit expression for the stationary queue length distribution is given firstly. Furthermore，the probability of the exact number of vacations that the sever has taken is also obtained. The more accurate descriptions for the status of the server are new results for the queue model.

M/M/1 queue；working vacation；GI/M/1 type Markov process；matrix geometric solution；difference equation

O226

A

1000-4424（2016）01-0050-07

2015-12-06

2016-01-03

國家自然科學(xué)基金（61174160）；河南省高等學(xué)校青年骨干教師（2014GGJS-136）；河南省高等學(xué)校重點科研項目（16A110002）；河南省教育廳教師教育研究課題（2015-JSJYYB-118）；河南省大中專就業(yè)創(chuàng)業(yè)研究課題（JYB2015042）