帶有負顧客的M/M/1/N 多重工作休假排隊在計算機信號傳輸系統(tǒng)的應用

趙曉華 樊劍武

（1.燕山大學 理學院，河北 秦皇島 066004；2.燕山大學里仁學院，河北 秦皇島 066004）

0 引言

休假排隊的研究成果已應用到很多的領(lǐng)域，像計算機系統(tǒng)、通信網(wǎng)絡(luò)、生產(chǎn)制造系統(tǒng)等。 詳細內(nèi)容可以參見Doshi 的綜述，Takagi，Tian和Zhang 的專著。 Servi 和Finn[2]在2002 年引入了一種半休假策略：服務員在假期中并未完全停止工作， 而是以較低的速率為顧客服務，這種休假策略稱為工作休假(working vacation WV )。 近年來工作休假排隊系統(tǒng)[3-6]受到了國內(nèi)外學者的關(guān)注。 同時，人們對帶有負顧客的排隊模型[5,6,7]研究的興趣也正日益高漲，負顧客可以看成服務系統(tǒng)中出現(xiàn)的1 次外來對服務臺的援助，1 次援助帶走1 名正在服務的顧客，當系統(tǒng)中沒有顧客時，外來援助會立即離開系統(tǒng)。 筆者考慮將上述所提及的排隊模型的特點結(jié)合在一起，考慮一個帶有負顧客且系統(tǒng)容量有限的M/M/1/N 多重工作休假排隊系統(tǒng)。

1 模型描述

在M/M/1/N 多重工作休假排隊系統(tǒng)中引入帶RCH(RCH：Removal of Customers at the Head ) 抵消策略的負顧客。 該系統(tǒng)是有正、負兩類顧客的單服務臺系統(tǒng)，每次只能接待一位顧客，系統(tǒng)容量為N，一旦系統(tǒng)中正顧客數(shù)達到N 個，再到達的正顧客就將消失。

1）正顧客和負顧客均泊松到達，到達率分別為λ和ε。

2）每個正顧客所需的服務時間服從負指數(shù)分布。在忙期中服務員的服務率為μb。 相繼兩次假期之間的時間稱為服務期或正規(guī)忙期。 現(xiàn)加入下列多重工作休假規(guī)則： 一旦系統(tǒng)中沒有正顧客即正規(guī)忙期結(jié)束，服務員立即進入一個隨機長度為V 的工作休假中，休假時間V 服從參數(shù)為θ 的負指數(shù)分布。 與通常的休假策略不同，服務員在假期內(nèi)并未完全停止工作，而是以較低的速率μv（μv<μb）為顧客服務。 當一次工作休假結(jié)束時，如果系統(tǒng)中已有正顧客在等待，服務員立即停止工作休假，服務率由μv提高到μb，一個正規(guī)忙期開始；否則服務員進行另一次獨立同分布的工作休假。

3）負顧客抵消隊首正在接受服務的正顧客，抵消原則為一對一抵消隊首的正顧客（若有），若系統(tǒng)中無正顧客，到達的負顧客自動消失，負顧客只起抵消正顧客的作用，負顧客不接受服務。

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

2 穩(wěn)態(tài)概率方程組

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

這里狀態(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)概率滿足的方程組為

3 穩(wěn)態(tài)概率的矩陣解法

令

表示穩(wěn)態(tài)概率向量，則上一節(jié)給出的穩(wěn)態(tài)概率方程組可以寫成矩陣形式如下：

注：B0為 N+1 階方陣；A 為（N+1）×N 階矩陣；C 為 N×（N+1）階矩陣；B 為N 階方陣； O1是元素全為0 的N 維行向量；O2是元素全為 0 的N-1 維列向量；O3是元素全為 0 的（N-1）XN 階矩陣；EN為 N 階單位矩陣.

引理1 設(shè)A=（aij）為一實數(shù)域上的n 階方陣，如果

證明 參見[7,8]。

引理2 將B0寫成如下分塊矩陣

其中：r1=（λ，0，…，0）為 N 維行向量為 N 維列向量；是N 階方陣，則可逆。

證明完畢。

同理可得：

所以B 為可逆矩陣。

證明完畢。

令 εn（1≤n≤N）表示 N 維單位列向量，eN+1和 eN分別表示元素全為 1 的 N+1 維、N 維列向量。

定理：系統(tǒng)的穩(wěn)態(tài)概率為

證明：定義穩(wěn)態(tài)向量

P0=(P0（0），P0（1），…，P0（N）），P1=(P1（1），…，P1（N））

則 P=(P0，P1)

將(12)式展開得

定義向量

則由(14)式可得

由(15)式得

將(20)式展開并將(18)式代入可得：

將(19)式、(21)式代入(13)式可得

將(22)式代入(19)式和(21)式并展開即得系統(tǒng)的穩(wěn)態(tài)概率為

證明完畢。

注：由上述定理可知，要得到系統(tǒng)的穩(wěn)態(tài)概率，須先要計算出向量和從而計算向量可轉(zhuǎn)化為求解三個非齊次線性方程組BZ=εn。

4 系統(tǒng)的性能指標

1）服務員處在正規(guī)忙期的概率

2）服務員工作休假的概率

3）系統(tǒng)的平均等待隊長

4）系統(tǒng)的平均隊長

5）顧客的消失概率

5 實例分析

通過以上的分析獲得了系統(tǒng)的平均等待隊長， 平均隊長以及顧客的消失概率等一些穩(wěn)態(tài)指標。 接下來將其應用到計算機通信系統(tǒng)中，假設(shè)有一臺信號交換機，能接受的信息容量為3，當信號的到達率λ=1、信號排隊過程中被分流走，也即負顧客的到達率ε=0.5、忙期的服務率μb=2 時，交換機休假時的服務率μv、休假率θ 對該信號平均等待隊長和信號消失概率的影響。

下面本文分別給出μv=0.5 E(Lq)時平均等待隊長與信號消失概率PL隨 θ 變化情況圖以及 θ=0.5 時平均等待隊長 E(Lq)與信號消失概率PL隨μv變化情況圖。

觀察圖1 和圖2，不難發(fā)現(xiàn)隨著或者的增大，系統(tǒng)的平均等待隊長E(Lq)以及顧客的消失概率PL均在逐漸減小。 進一步比較兩圖可以看出，當μv和θ 增大到一定程度時，對兩者的影響變得不明顯。

圖1 μv＝0.5 時 E(Lq)和 PL 隨 θ 的變化情況Fig.1 The relation of E(Lq) and PL with θ (μv＝0.5)

通過上面的數(shù)值分析，比較清楚的了解了系統(tǒng)的兩個參數(shù)μv和θ對信號交換系統(tǒng)性能指標的影響。 運用這個結(jié)果，設(shè)計人員就可以設(shè)計合理的休假率θ 和休假期的服務率μv，使信號交換系統(tǒng)盡可能達到最優(yōu)。

圖2 θ＝0.5 時 E(Lq)和 PL 隨 μv 的變化情況Fig.2 The relation of E(Lq) and PL with μv (θ＝0.5)

［1］田乃碩.休假隨機服務系統(tǒng)[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, 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].山東大學學報，2008，43(10)：46-51.

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

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

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

［9］林記.關(guān)于n 階循環(huán)矩陣可逆問題的幾點討論[J].四川理工學院學報，2007，20(2)：21-24.