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

趙曉華　樊劍武

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

【關鍵詞】排隊系統；穩態概率；矩陣解法；負顧客；多重工作休假

【Abstract】An M/M/1/N queuing system was considered with negative and multiple working vacations. 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】Queuing system； Steady-state probability； Matrix solution method； Negative customers； Multiple working vacation

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

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

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

2 穩態概率方程組

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

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和θ增大到一定程度時，對兩者的影響變得不明顯。

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

【參考文獻】

[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.

[責任編輯：程龍]

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

【關鍵詞】排隊系統；穩態概率；矩陣解法；負顧客；多重工作休假

【Abstract】An M/M/1/N queuing system was considered with negative and multiple working vacations. 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】Queuing system； Steady-state probability； Matrix solution method； Negative customers； Multiple working vacation

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

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

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

2 穩態概率方程組

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

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和θ增大到一定程度時，對兩者的影響變得不明顯。

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

【參考文獻】

[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.

[責任編輯：程龍]

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

【關鍵詞】排隊系統；穩態概率；矩陣解法；負顧客；多重工作休假

【Abstract】An M/M/1/N queuing system was considered with negative and multiple working vacations. 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】Queuing system； Steady-state probability； Matrix solution method； Negative customers； Multiple working vacation

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

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

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

2 穩態概率方程組

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

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和θ增大到一定程度時，對兩者的影響變得不明顯。

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

【參考文獻】

[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.

[責任編輯：程龍]