張宏波，鄭群珍，史定華

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

?

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

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

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

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

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

§1　引　言

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

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

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

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

§2　模型描述

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

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

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

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

其中

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

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

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

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

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

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

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

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

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

其中

是一個(gè)常數(shù).

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

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

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

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

所以有

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

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

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

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

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

由此即得（10）式.

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

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

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

所以由（16）可知

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

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

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

其中

是一個(gè)常數(shù).

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

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

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

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

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

其中K的定義見定理3.1.

證由顯然的事實(shí)

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

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

§4　小結(jié)

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

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

［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

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