趙曉華 樊劍武
【摘 要】研究了一個帶有中途退出的M/M/1/N單重工作休假排隊系統(tǒng)。服務(wù)員在假期中以較低的速率服務(wù)顧客而非停止工作。利用馬爾科夫過程理論和矩陣解法求出了穩(wěn)態(tài)概率的矩陣解,并得到了系統(tǒng)的平均隊長、平均等待隊長以及顧客的消失概率等性能指標(biāo)。
【關(guān)鍵詞】單重工作休假;止步;穩(wěn)態(tài)概率;矩陣解法;性能指標(biāo)
【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]已經(jīng)得到了廣泛、深入的研究并形成了理論框架。在各種各樣的休假排隊模型中,服務(wù)員在假期中完全停止服務(wù),但是他可以從事輔助工作。休假排隊的研究成果已應(yīng)用到很多的領(lǐng)域,像計算機(jī)系統(tǒng)、通信網(wǎng)絡(luò)、生產(chǎn)制造系統(tǒng)等。詳細(xì)內(nèi)容可以參見Doshi的綜述,Takagi,Tian和Zhang的專著。Servi和Finn[2]在2002年引入了一種半休假策略:服務(wù)員在假期中并未完全停止工作,而是以較低的速率為顧客服務(wù),這種休假策略稱為工作休假(working vacation WV )。如果讓服務(wù)員在工作休假中服務(wù)率減小為零,則工作休假排隊就成為了一個經(jīng)典休假排隊模型,因此工作休假排隊是經(jīng)典休假排隊的一個擴(kuò)展。近年來工作休假排隊系統(tǒng)[3-6]受到了國內(nèi)外學(xué)者的關(guān)注。但對有限等待場所研究的還不多,因此本文考慮一個等待場所有限的M/M/1/N單重工作休假排隊系統(tǒng)。
本文結(jié)構(gòu)安排如下:第二節(jié)描述了系統(tǒng)模型;第三節(jié)利用馬爾科夫過程理論建立了系統(tǒng)穩(wěn)態(tài)概率滿足的方程組;第四節(jié)將轉(zhuǎn)移率矩陣寫成了分塊矩陣的形式,并證明了相關(guān)矩陣的可逆性。在此基礎(chǔ)上,利用分塊矩陣解法求出了穩(wěn)態(tài)概率的矩陣解;第五節(jié)利用穩(wěn)態(tài)概率的矩陣解,得到了系統(tǒng)的平均隊長、平均等待隊長及顧客的消失概率等性能指標(biāo)。
1 模型描述
考慮一個M/M/1/N排隊系統(tǒng),系統(tǒng)中只有一個服務(wù)臺,每次只能接待一位顧客,系統(tǒng)容量為N,一旦系統(tǒng)中顧客數(shù)達(dá)到N個,再到達(dá)的顧客就將消失。因此這也是一個消失系統(tǒng)。顧客按照參數(shù)為λ的Poisson流到達(dá)。每個顧客所需的服務(wù)時間服從負(fù)指數(shù)分布。在忙期中服務(wù)員的服務(wù)率為μb。相繼兩次假期之間的時間稱為服務(wù)期或正規(guī)忙期?,F(xiàn)加入下列單重工作休假規(guī)則:一旦系統(tǒng)中沒有顧客即正規(guī)忙期結(jié)束,服務(wù)員立即進(jìn)入一個隨機(jī)長度為V的工作休假中,休假時間V服從參數(shù)為θ的負(fù)指數(shù)分布。與通常的休假策略不同,服務(wù)員在假期內(nèi)并未完全停止工作,而是以較低的速率μv(μv<μb)為顧客服務(wù)。當(dāng)一次工作休假結(jié)束時,如果系統(tǒng)中已有顧客在等待,服務(wù)員立即停止工作休假,服務(wù)率由μv提高到μb,一個正規(guī)忙期開始;否則就進(jìn)入閑期,直到有顧客到達(dá),正規(guī)的忙期才開始。令n表示系統(tǒng)中的顧客數(shù)。若n≤1,則系統(tǒng)中的顧客立即可以得到服務(wù),此時不會發(fā)生中途退出的情況;反之n>1,若,則一個顧客在接受服務(wù),其余n-1個顧客在隊列中等待服務(wù),這時顧客可能因為等待的不耐煩而在沒有接受服務(wù)的情況下離開系統(tǒng)(中途退出)。假設(shè)顧客在進(jìn)入系統(tǒng)后直到中途退出的這段等待時間服從參數(shù)為α的負(fù)指數(shù)分布,由于每個顧客的到達(dá)和離去都是獨立的,則可得顧客的中途退出率:
r(n)=(n-1)α, 2≤n≤N
假定到達(dá)間隔T,工作休假時間V,正規(guī)忙期中的服務(wù)時間Sb和工作休假的服務(wù)時間Sv均相互獨立,服務(wù)規(guī)則為先到先服務(wù)(FCFS)。
2 穩(wěn)態(tài)概率方程組
令L(t)表示時刻t系統(tǒng)中的顧客數(shù)即時刻t系統(tǒng)的隊長,t≥0。令J(t)表示時刻t服務(wù)員的工作狀態(tài),定義如下:
J(t)=0,時刻t服務(wù)員處于工作休假狀態(tài)1,時刻t服務(wù)員處于非工作休假狀態(tài)
則{L(t),J(t),t≥}為一馬爾科夫過程, 其狀態(tài)空間為:
Ω={(n,0)∶0≤n≤N}∪{(n,1)∶0≤n≤N}
這里狀態(tài)(0,1)表示系統(tǒng)處在閑期;狀態(tài)n,1,1≤n≤N表示系統(tǒng)處在正規(guī)忙期;狀態(tài)n,0,0≤n≤N表示系統(tǒng)處在工作休假期,其中n表示系統(tǒng)中的顧客數(shù)。
系統(tǒng)的穩(wěn)態(tài)概率定義如下:
給出了排隊系統(tǒng)的穩(wěn)態(tài)指標(biāo),我們就可以通過數(shù)值分析,了解系統(tǒng)中的某些參數(shù)對這些穩(wěn)態(tài)指標(biāo)的影響,從而使排隊系統(tǒng)盡可能達(dá)到最優(yōu)。
【參考文獻(xiàn)】
[1]田乃碩. 休假隨機(jī)服務(wù)系統(tǒng)[M]. 北京:北京大學(xué)出版社,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多重工作休假排隊系統(tǒng)[J].山東大學(xué)學(xué)報,2008,43(10):46-51.
[6]趙曉華,樊劍武,田乃碩. 帶有止步的成批到達(dá)MX/M/1/N多重工作休假排隊系統(tǒng)[J].燕山大學(xué)學(xué)報,2009,33(2):178-183.
[7]樊劍武,趙曉華,李旭紅,李秀菊.M/M/1/N單重工作休假排隊系統(tǒng)的性能分析[J].四川理工學(xué)院學(xué)報,2009,22(3):113-116.
[8]北京大學(xué)數(shù)學(xué)系幾何與代數(shù)教研室代數(shù)小組.高等代數(shù).2版[M].北京:高等教育出版社,12,158.
[9]林記.關(guān)于n階循環(huán)矩陣可逆問題的幾點討論[J].四川理工學(xué)院學(xué)報,2007,20(2):21-24.
[責(zé)任編輯:曹明明]