帶有中途退出的M/M/1/N單重工作休假排隊系統

趙曉華　樊劍武

【摘 要】研究了一個帶有中途退出的M/M/1/N單重工作休假排隊系統。服務員在假期中以較低的速率服務顧客而非停止工作。利用馬爾科夫過程理論和矩陣解法求出了穩態概率的矩陣解，并得到了系統的平均隊長、平均等待隊長以及顧客的消失概率等性能指標。

【關鍵詞】單重工作休假；止步；穩態概率；矩陣解法；性能指標

【Abstract】An M/M/1/N queuing system was considered with reneging and single working vacation. The server works at a lower rate rather than completely stops service during the vacation period. First， the matrix form solution of the steady-state probability was derived by the Markfov process method and the matrix solution method. Some performance measures of the system such as the expected number of customers in the system or in the queue and the loss probability of the customer were also presented.

【Key words】Single working vacation；Reneging；Teady-state probability；Matrix solution method；Performance measures

0 引言

在過去的20年里，休假排隊[1]已經得到了廣泛、深入的研究并形成了理論框架。在各種各樣的休假排隊模型中，服務員在假期中完全停止服務，但是他可以從事輔助工作。休假排隊的研究成果已應用到很多的領域，像計算機系統、通信網絡、生產制造系統等。詳細內容可以參見Doshi的綜述，Takagi，Tian和Zhang的專著。Servi和Finn[2]在2002年引入了一種半休假策略：服務員在假期中并未完全停止工作，而是以較低的速率為顧客服務，這種休假策略稱為工作休假（working vacation WV ）。如果讓服務員在工作休假中服務率減小為零，則工作休假排隊就成為了一個經典休假排隊模型，因此工作休假排隊是經典休假排隊的一個擴展。近年來工作休假排隊系統[3-6]受到了國內外學者的關注。但對有限等待場所研究的還不多，因此本文考慮一個等待場所有限的M/M/1/N單重工作休假排隊系統。

本文結構安排如下：第二節描述了系統模型；第三節利用馬爾科夫過程理論建立了系統穩態概率滿足的方程組；第四節將轉移率矩陣寫成了分塊矩陣的形式，并證明了相關矩陣的可逆性。在此基礎上，利用分塊矩陣解法求出了穩態概率的矩陣解；第五節利用穩態概率的矩陣解，得到了系統的平均隊長、平均等待隊長及顧客的消失概率等性能指標。

1 模型描述

考慮一個M/M/1/N排隊系統，系統中只有一個服務臺，每次只能接待一位顧客，系統容量為N，一旦系統中顧客數達到N個，再到達的顧客就將消失。因此這也是一個消失系統。顧客按照參數為λ的Poisson流到達。每個顧客所需的服務時間服從負指數分布。在忙期中服務員的服務率為μb。相繼兩次假期之間的時間稱為服務期或正規忙期。現加入下列單重工作休假規則：一旦系統中沒有顧客即正規忙期結束，服務員立即進入一個隨機長度為V的工作休假中，休假時間V服從參數為θ的負指數分布。與通常的休假策略不同，服務員在假期內并未完全停止工作，而是以較低的速率μv（μv<μb）為顧客服務。當一次工作休假結束時，如果系統中已有顧客在等待，服務員立即停止工作休假，服務率由μv提高到μb，一個正規忙期開始；否則就進入閑期，直到有顧客到達，正規的忙期才開始。令n表示系統中的顧客數。若n≤1，則系統中的顧客立即可以得到服務，此時不會發生中途退出的情況；反之n>1，若，則一個顧客在接受服務，其余n-1個顧客在隊列中等待服務，這時顧客可能因為等待的不耐煩而在沒有接受服務的情況下離開系統（中途退出）。假設顧客在進入系統后直到中途退出的這段等待時間服從參數為α的負指數分布，由于每個顧客的到達和離去都是獨立的，則可得顧客的中途退出率：

r（n）=（n-1）α， 2≤n≤N

假定到達間隔T，工作休假時間V，正規忙期中的服務時間Sb和工作休假的服務時間Sv均相互獨立，服務規則為先到先服務（FCFS）。

2 穩態概率方程組

令L（t）表示時刻t系統中的顧客數即時刻t系統的隊長，t≥0。令J（t）表示時刻t服務員的工作狀態，定義如下：

J（t）=0，時刻t服務員處于工作休假狀態1，時刻t服務員處于非工作休假狀態

則{L（t），J（t），t≥}為一馬爾科夫過程， 其狀態空間為：

Ω={（n，0）∶0≤n≤N}∪{（n，1）∶0≤n≤N}

這里狀態（0，1）表示系統處在閑期；狀態n，1，1≤n≤N表示系統處在正規忙期；狀態n，0，0≤n≤N表示系統處在工作休假期，其中n表示系統中的顧客數。

系統的穩態概率定義如下：

給出了排隊系統的穩態指標，我們就可以通過數值分析，了解系統中的某些參數對這些穩態指標的影響，從而使排隊系統盡可能達到最優。

【參考文獻】

[1]田乃碩. 休假隨機服務系統[M]. 北京：北京大學出版社，2001.

[2]Servi L D， Finn S G. M/M/1 queue with working vacations（M/M/1/WV）[J]. Perform. Evaluation， 2002， 50： 41-52.

[3]Liu W Y， Xu X L， Tian N S. Stochastic decompositions in the M/M/1 queue with working vacations[J]. Operation Research Letters， 2007，35（5）：595-600.

[4]Li J， Tian N. Analysis of the discrete time Geo/Geo/1 queue with single working vacation[J]. Quality Technology and Quantitative Management， 2008，5（1）：77-89.

[5]趙曉華，樊劍武，田乃碩，田瑞玲.帶有止步和中途退出的M/M/1/N多重工作休假排隊系統[J].山東大學學報，2008，43（10）：46-51.

[6]趙曉華，樊劍武，田乃碩. 帶有止步的成批到達MX/M/1/N多重工作休假排隊系統[J].燕山大學學報，2009，33（2）：178-183.

[7]樊劍武，趙曉華，李旭紅，李秀菊.M/M/1/N單重工作休假排隊系統的性能分析[J].四川理工學院學報，2009，22（3）：113-116.

[8]北京大學數學系幾何與代數教研室代數小組.高等代數.2版[M].北京：高等教育出版社，12，158.

[9]林記.關于n階循環矩陣可逆問題的幾點討論[J].四川理工學院學報，2007，20（2）：21-24.

[責任編輯：曹明明]