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

趙曉華 樊劍武

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

0 引言

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

1 模型描述

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

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

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

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

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

2 穩態概率方程組

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

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

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

由馬爾科夫過程理論可得系統穩態概率滿足的方程組為

3 穩態概率的矩陣解法

令

表示穩態概率向量，則上一節給出的穩態概率方程組可以寫成矩陣形式如下：

注：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 設A=（aij）為一實數域上的n 階方陣，如果

證明 參見[7,8]。

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

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

證明完畢。

同理可得：

所以B 為可逆矩陣。

證明完畢。

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

定理：系統的穩態概率為

證明：定義穩態向量

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)式并展開即得系統的穩態概率為

證明完畢。

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

4 系統的性能指標

1）服務員處在正規忙期的概率

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

3）系統的平均等待隊長

4）系統的平均隊長

5）顧客的消失概率

5 實例分析

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

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

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

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

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

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

［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, 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］北京大學數學系幾何與代數教研室代數小組.高等代數[M].2 版.北京：高等教育出版社，12，158.

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