同步多重工作休假排隊(duì)系統(tǒng)分析

苑春薈，徐 劍，朱翼雋

(1.北京郵電大學(xué)經(jīng)濟(jì)管理學(xué)院，北京100876;2.江蘇大學(xué)理學(xué)院，江蘇鎮(zhèn)江212013)

在過去的幾十年里，國(guó)內(nèi)外學(xué)者對(duì)經(jīng)典M/M/1排隊(duì)系統(tǒng)進(jìn)行了廣泛深入地研究，得到了許多有價(jià)值的科研成果［1-4］，而這些科研成果也被應(yīng)用于諸多領(lǐng)域，比如:計(jì)算機(jī)系統(tǒng)、通信網(wǎng)路系統(tǒng)和生產(chǎn)制造系統(tǒng)等.近年來，L.D.Servi等又引入了一種半休假策略:在休假期間服務(wù)臺(tái)并不是完全停止服務(wù)而是以較低的服務(wù)率對(duì)顧客進(jìn)行服務(wù)，這種半休假策略叫作工作休假(working vacation，WV)［5-7］.如果工作休假的服務(wù)率退化為0，那么模型就歸結(jié)為經(jīng)典的休假排隊(duì).但是，在特定的排隊(duì)系統(tǒng)中，例如:通訊網(wǎng)絡(luò)中的數(shù)據(jù)傳輸，由于外來干擾信號(hào)的到達(dá)會(huì)抵消一部分傳輸數(shù)據(jù)，而這種外來干擾信號(hào)可以看作負(fù)顧客，帶有負(fù)顧客的排隊(duì)系統(tǒng)除了應(yīng)用于通信系統(tǒng)外，還可以應(yīng)用于生產(chǎn)制造系統(tǒng)或銷售系統(tǒng)(這時(shí)負(fù)顧客可以看成是操作員的操作或是其他致使顧客離開的原因)，并且顧客到達(dá)可能使服務(wù)員休假或者故障，負(fù)顧客的排隊(duì)理論由此得到推廣［8-10］.結(jié)合實(shí)際應(yīng)用情況，筆者提出另一種策略:休假可中止.例如:銷售系統(tǒng)中，休假期間突然遇到顧客高峰［11］.基于現(xiàn)實(shí)生活中通訊網(wǎng)絡(luò)等各種排隊(duì)系統(tǒng)的復(fù)雜性，提出負(fù)顧客、帶休假可中止的同步多重工作休假排隊(duì)模型.

1 模型描述

模型描述如下:

1)該系統(tǒng)是具有正負(fù)兩類顧客的M/M/1排隊(duì)，正負(fù)顧客均為泊松到達(dá)，到達(dá)率分別為λ和ξ.

2)到達(dá)的負(fù)顧客帶RCE(removal customer at the end)抵消策略，即到達(dá)的負(fù)顧客一對(duì)一抵消隊(duì)尾的正顧客(若有，不管正顧客是在等待還是在被服務(wù))，而若負(fù)顧客到達(dá)時(shí)系統(tǒng)中沒有正顧客，負(fù)顧客就自動(dòng)消失，負(fù)顧客本身并不接受服務(wù).

3)當(dāng)系統(tǒng)變?yōu)榭諘r(shí)，服務(wù)臺(tái)開始一個(gè)隨機(jī)長(zhǎng)度為V的工作休假，休假時(shí)間V服從參數(shù)為θ的指數(shù)分布，在工作休假期，服務(wù)員以較低的速率對(duì)正顧客進(jìn)行服務(wù).

4)服務(wù)臺(tái)對(duì)正顧客在正規(guī)忙期和工作休假期的服務(wù)時(shí)間分別服從參數(shù)為μ1和μ2的負(fù)指數(shù)分布，這里 μ1＞ μ2.

5)有2種可能的方式從工作休假轉(zhuǎn)入正規(guī)忙期:①工作休假期間完成1個(gè)顧客服務(wù)，并且系統(tǒng)中有顧客等待，則中止正在進(jìn)行的工作休假轉(zhuǎn)入正規(guī)忙期，若服務(wù)完成時(shí)，系統(tǒng)中無顧客，則繼續(xù)保持在工作休假狀態(tài)上;② 若某次工作休假結(jié)束時(shí)，系統(tǒng)內(nèi)有顧客在場(chǎng)，正在進(jìn)行的服務(wù)由速率μ2轉(zhuǎn)換到速率μ1，開始1個(gè)正規(guī)忙期.若1次工作休假結(jié)束時(shí)，系統(tǒng)中無顧客，則服務(wù)臺(tái)開始另1次獨(dú)立同分布的工作休假.

6)假定:正負(fù)顧客的到達(dá)間隔，工作休假時(shí)間，正規(guī)忙期和工作休假期的服務(wù)時(shí)間相互獨(dú)立，此外，服務(wù)規(guī)則為先到先服務(wù)(FIFO).

Qv(t)表示t時(shí)刻系統(tǒng)中的顧客數(shù)，J(t)的定義如下:

這樣，{Qv(t)，J(t)}是1個(gè)擬生滅過程(QBD過程)，狀態(tài)空間為 Ω ={0，1}∪{(k，j):k≥1，j=0，1}.過程的狀態(tài)轉(zhuǎn)移機(jī)制如圖1所示.

圖1 狀態(tài)轉(zhuǎn)移機(jī)制

如果將狀態(tài)按字典序排列，其生成元可寫成下列分塊三對(duì)角形式:

其中:A0=-λ;C0=(0，λ);B1=(μ1+ ξ，μ2+ ξ)T;C=λI，I為二階單位矩陣;

的最小非負(fù)解，這個(gè)解稱為率陣，記為R.R在矩陣幾何解中起著關(guān)鍵的作用.先假設(shè)

定理1 當(dāng)ρ＜1時(shí)，方程(2)有最小非負(fù)解:

證明 因?yàn)锳，B，C都是下三角陣，也設(shè)R是

為了得到方程R2B+RA+C=0的最小非負(fù)解，在式(4)第1個(gè)方程中取r11=ρ，而另一根r11=1，由 式(4)中 第 2個(gè) 方 程 給 出r22=，另一根大于1，易證0＜r22＜1.

將r11，r22代入式(4)中的第3個(gè)方程可得

推論1r11，r22滿足下列關(guān)系式:

定理2 擬生滅過程{Qv(t)，J(t)}正常返，當(dāng)且僅當(dāng)

證明 由率陣R的定義可知:SP(R)＜1.當(dāng)且僅當(dāng)ρ＜1，由文獻(xiàn)［12］中定理2.4可證明過程正常返，當(dāng)且僅當(dāng)ρ＜1.

2 隊(duì)長(zhǎng)的穩(wěn)態(tài)分布

當(dāng)ρ＜1時(shí)，擬生滅過程{Qv(t)，J(t)}是正常返的，(Qv，J)表示它的極限分布，將(Qv，J)的分布寫成如下的分段形式 π =(π0，π1，π2，…)，其中π0=(π01);πk=(πk0，πk1)，k≥1，且

定理3 當(dāng)ρ＜1時(shí)，{Qv(t)，J(t)}的穩(wěn)態(tài)極限(Qv，J)的分布為

式中:r21，r22的取值同式(3);K為常數(shù)因子，

證明 下面先求B［R］及正左不變向量(π01，π10，π11)，有

所以，由(π01，π10，π11)B［R］=0，可得方程組:

取 π01=K， 則 (π01，π10，π11)=K(1，，應(yīng)用 M.Neuts［13］的矩陣幾何解法，可得

最后由正規(guī)化條件可求得常數(shù)因子K，即式(8).

3 穩(wěn)態(tài)隊(duì)長(zhǎng)的條件隨機(jī)分解

證明 由定理3可知，Q的概率母函數(shù)為

推論2 系統(tǒng)的平均附加隊(duì)長(zhǎng):

進(jìn)一步得到系統(tǒng)的平均等待隊(duì)長(zhǎng):

4 數(shù)值例子

通過以上分析獲得了系統(tǒng)平均附加隊(duì)長(zhǎng)、平均隊(duì)長(zhǎng)等穩(wěn)態(tài)指標(biāo).但作為管理決策者不僅要知道排隊(duì)系統(tǒng)的穩(wěn)態(tài)指標(biāo)，還要了解系統(tǒng)中的某些參數(shù)對(duì)這些穩(wěn)態(tài)指標(biāo)的影響，從而使排隊(duì)系統(tǒng)盡可能達(dá)到最優(yōu).穩(wěn)態(tài)平均隊(duì)長(zhǎng)E(Q)和負(fù)顧客到達(dá)率ξ之間的關(guān)系如圖 2 所示，當(dāng) λ =0.3，μ1=0.9，μ2=0.7時(shí)，不論休假率如何變化，平均隊(duì)長(zhǎng)也是隨著負(fù)顧客到達(dá)率的增加而逐漸遞減的.

圖2 E(Q)隨ξ的變化趨勢(shì)

5 結(jié)論

各種休假策略的研究為排隊(duì)系統(tǒng)的優(yōu)化設(shè)計(jì)和控制提供了更大的靈活性.考慮了一類帶有負(fù)顧客、休假可中止的同步多重工作休假排隊(duì)模型，通過計(jì)算、分析，給出了系統(tǒng)隊(duì)長(zhǎng)的穩(wěn)態(tài)分布及系統(tǒng)隊(duì)長(zhǎng)隨機(jī)分解結(jié)果.可將此模型應(yīng)用到通訊網(wǎng)絡(luò)系統(tǒng)中，當(dāng)數(shù)據(jù)傳送到服務(wù)臺(tái)時(shí)，數(shù)據(jù)傳送可看成正負(fù)顧客的到達(dá)，外來的干擾信號(hào)可看成負(fù)顧客的到達(dá).考慮到在現(xiàn)實(shí)生活中，通訊網(wǎng)絡(luò)的復(fù)雜性，服務(wù)臺(tái)可能隨時(shí)需要從工作休假轉(zhuǎn)入正規(guī)忙期，于是提出了另一種策略:休假可中止.最后通過對(duì)數(shù)值的分析，更加清楚地了解了負(fù)顧客的到達(dá)對(duì)系統(tǒng)的影響.該模型在現(xiàn)代通訊網(wǎng)絡(luò)中有很好的應(yīng)用價(jià)值.

References)

［1］田乃碩.休假隨機(jī)服務(wù)系統(tǒng)［M］.北京大學(xué)出版社，2001.

［2］Krishna Kumar B，Arivudainambi D.Transient solution of anM/M/1 queue with catastrophes［J］.Computers and Mathematics with Applications，2000，40(10):1233-1240.

［3］Di Crescenzo A，Giorno V，Nobile A G.On theM/M/1 queue with catastrophes and its continuous approximation［J］.Queueing Systems，2003，43:329-347.

［4］Miller D R.Computation of steady-state probability forM/M/1 priority queues ［J］.Operations Research，1981，29(5):945-948.

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

［6］楊順利，田乃碩.N-策略工作休假M(fèi)/M/1排隊(duì)［J］.運(yùn)籌與管理，2007，16(4):50-55.Yang Shunli，Tian Naishuo.TheM/M/1 queue with working vacations andN-policy［J］.Operations Research and Management Science，2007，16(4):50-55.(in Chinese)

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

［8］朱翼雋，顧慶鳳.帶RCE抵消策略的負(fù)顧客GI/M/1工作休假排隊(duì)［J］.江蘇大學(xué)學(xué)報(bào):自然科學(xué)版，2008，29(4):360-364.Zhu Yijun，Gu Qingfeng.GI/M/1 queue with RCE strategy of negative customers and working vacations［J］.Journal of Jiangsu University:Natural Science Edition，2008，29(4):360-364.(in Chinese)

［9］Harrison P G，Pitel E.TheM/G/1 queue with negative customers［J］.Advances of Applied Probability，1996，28(2):540-560.

［10］朱翼雋，劉海燕，王逢佳.帶啟動(dòng)時(shí)間、N策略和負(fù)顧客的M/M/1工作休假排隊(duì)［J］.江蘇大學(xué)學(xué)報(bào):自然科學(xué)版，2012，33(5):616-620.Zhu Yijun，Liu Haiyan，Wang Fengjia.M/M/1 queue of working vacation with set-up timeN-policy and negative customers［J］.Journal of Jiangsu University:Natural Science Edition，2012，33(5):616-620.(in Chinese)

［11］Li Jihong，Tian Naishuo.The discrete-timeGI/Geo/1 queue with working vacations and vacation Interruption［J］.Applied Mathematics and Computation，2007，185(1):1-10.

［12］田乃碩，岳德權(quán).擬生滅過程與矩陣幾何解［M］.北京:科學(xué)出版社，2002.

［13］Neuts M.Matrix-Geometric Solutions in Stochastic Models［M］.Baltimore:The Johns Hopkins University Press，1981.