多服務臺混合制排隊模型M/G/s/K的仿真研究

摘 要:為更快、更方便地得到一般服務時間的多服務臺混合制中M/G/s/K排隊系統在達到穩定之后的系統狀態，通過離散化處理仿真時間方法，并借鑒時間步長法的思想，給出一種基于Matlab編程的仿真算法。通過實驗說明了該方法的有效性。對于處理此類排隊問題提供了一個新的方法。

關鍵詞:多服務臺混合制排隊模型; M/G/s/K排隊模型; 時間步長法; Matlab編程

中圖分類號:TN911-34; TP274文獻標識碼:A

文章編號:1004-373X(2010)17-0142-04

Simulation of M/G/s/K Multi-server Mixed Queuing Model

CHEN Shi

(School of Finance and Statistics， East China Normal University， Shanghai 200241， China)

Abstract: On the purpose of obtaining the system state of M/G/s/K multi-server mixed queuing model after arriving at stable state in a faster and convenient manner， through performing the simulated time with discrete method and utilizing the thoughts of fix-time incrementing method， an algorithm based on Matlab programming to implement the simulation of M/G/s/K queuing model is proposed， and the validity of this simulation algorithm is demonstrated. A new method to deal with problems of this category is provided.

Keywords: mixed queuing model of multi servers; M/G/s/K queuing model; fix-time incrementing method; Matlab programming

0 引 言

排隊論是研究隨機服務系統的數學理論和方法。在某些特定情況下排隊隊列達到穩定的時候，排隊系統的各個參數可以通過數學推導得到。但當排隊過程不具備馬爾科夫性時，用數學推導的方式研究排隊系統是異常困難的。然而隨著計算機技術的發展，運用計算機仿真的方法研究排隊模型已成為解決這類排隊問題的有效方法。

排隊系統的仿真問題國內已經有很多人在研究，并且已經取得了一些成果。張建航等用蒙特卡洛模擬的方法初步解決了排隊理論中最為基礎的單服務員排隊模型(M/M/1模型)的仿真模擬問題[1];李鵬和王珊珊在論文中給出了較為詳細的單服務臺排隊模型的仿真方法[2];宋振峰等更進一步研究了M/M/m非混合制排隊模型的仿真方法[3]。國內文獻相對缺乏對M/G/s/K這類更為復雜的多服務臺混合制排隊模型的仿真研究。

本文將以Matlab為編程平臺，研究M/G/s/K模型的仿真算法。

1 M/G/s/K模型介紹

本文根據多服務臺混合排隊模型的特性，繪制了該模型的運行模式，如圖1所示。

圖1 多服務臺混合排隊模型的運行模式

在M/G/s/K排隊模型中，顧客的其到達過程服從參數為λ的Poisson流，等待隊列為容量為K-s，當系統中有新顧客到來時，如果等待隊列中人數已滿，此顧客就會被拒絕在排隊系統外，從而造成了服務系統的顧客損失，如果等待隊列中人數未滿，則此名顧客加入等待隊列，等候接受服務。系統中有多個服務臺，每個顧客接受服務所要花費的時間服從一般分布G。在等待隊列中，顧客接受服務服從先到先服務(FCFS)的原則。

2 M/G/s/K排隊模型的仿真算法

本文運用時間步長法的思想對多服務臺混合制排隊模型M/G/s/K進行仿真，假設所有事件(顧客到達，服務開始，顧客離去)均是在每一個步長結束的瞬間發生的，這樣，就將此問題轉化成為了離散化的問題，從而有利于運用計算機進行仿真。

為了方便排隊系統中所有的顧客信息、顧客排隊等候情況和各服務臺的服務情況更新，本文首先構建3個矩陣:顧客信息矩陣、等待隊列信息矩陣和服務臺狀態矩陣，用來輔助仿真算法的實現。下面介紹這3個矩陣所存儲的信息、矩陣的初始化方法和更新算法。

2.1 顧客信息矩陣

顧客信息矩陣是存儲仿真時段T內到達的所有顧客的信息矩陣。

(1) 矩陣儲存的信息

顧客信息矩陣為一個h×3的矩陣，其中h為仿真時間T內到達顧客的人數，矩陣的每一列存放著一名顧客的信息，顧客信息矩陣每一行所存放的具體信息如表1所示。

表1 顧客信息矩陣

矩陣行矩陣行存放的信息

1顧客到達排隊系統的時刻

2顧客接受服務臺服務所花費的時間

3顧客是否被排隊系統接受的示性指標

其中，第三行中所指的示性指標定義:一名顧客到達排隊系統的時候，若等待隊列已滿，此顧客被排隊系統拒絕，則相應的矩陣列的第三行所記錄的示性指標為0;若顧客到達排隊系統的時候，等待隊列人數未滿，此名顧客被排隊系統接受，相應的矩陣列的第三行所記錄的示性指標為1。

(2) 矩陣的初始化

設所要仿真的時間段的長度為T，用隨機數發生器產生泊松分布Poisson(λt)的隨機數h，作為這段時間內出現的顧客總人數。由于顧客到達間隔服從參數不變的負指數分布，由泊松過程理論可知，在一個固定時間段T內如果給定了乘客到達的人數h，那么每個顧客到達時間獨立地服從這一時間段上均勻分布。獨立地取h個服從(0，T)上的均勻分布的隨機數，精確到秒，作為這h名顧客的到達時刻，并將其輸入顧客信息矩陣的第一行。

根據前面排隊模型所描述的每位顧客的服務時間分布，用隨機數發生器產生h個相互獨立的服從分布G的隨機數，作為每位顧客接受服務臺服務所要花費的時間，精確到秒后，將這h個數據輸入到顧客信息矩陣的第二行。

用數字0初始化顧客信息矩陣的第三行所有元素。

(3) 矩陣的更新算法

顧客信息矩陣的前兩行需在仿真開始之前就先行確定，在仿真過程中不需進行更新，而第三行應隨著仿真時鐘的推進而不斷更新，當仿真時鐘在t時刻，第i名顧客到達排隊系統，且此時等待隊列中人數未滿，則此顧客被等待隊列接受，由2.1節所給出的示性指標定義，更新顧客信息矩陣第三行第i列的元素為1，否則，不對矩陣進行更新。

2.2 等待隊列信息矩陣

等待隊列信息矩陣是存放在等待隊列中等待顧客的信息矩陣。

(1) 矩陣儲存的信息

等待隊列信息矩陣大小為2×(K-s)。其中，K為系統所能容納的最大顧客數;s為系統中的服務臺個數;矩陣的每列代表等待隊列中的一個位置，若第i個座位未被占據，則矩陣第i列元素均為0;若座位被顧客占據，則等待隊列信息矩陣的第i列記錄了這名顧客的相關信息，具體每行所記錄的信息內容如表2所示。

表2 等待隊列信息矩陣

矩陣行矩陣行存放的信息

1顧客進入等待隊列的時刻

2顧客接受服務臺服務所要花費的時間

有一點值得強調的是，假設在隊列中，顧客均趨向于在最前面的等待位置就坐，也就是說，若等待隊列中有a名顧客在等待，則這a名顧客的信息要根據到達時刻的先后順序依次占據等待隊列信息矩陣的前a列，后面的K-s-a列矩陣元素以0填充，矩陣的具體形式如下所示:

c1c2c3…ca0…0

b1b2b3…ba0…02×(K-s)

(2) 矩陣初始化

在仿真開始之前，隊列中無顧客在等候，所以將該矩陣初始化為2×(K-s)的零矩陣。

(3) 矩陣的更新算法

等待隊列信息矩陣中的元素應隨著仿真時鐘的推進而不斷更新，每次仿真時鐘刷新之后，矩陣就應按照如下算法進行更新:

① 若仿真時鐘所指時刻剛好有顧客結束服務離開系統或此時有服務臺處于空閑狀態，如果等待隊列中仍有乘客在等待，則此服務臺接受占據等待矩陣第一列的乘客，并將等待矩陣中所有其他顧客的信息前移一列。用0元素填充不存儲有等待顧客信息的矩陣列。如果等待隊列中沒有顧客在等待，即此時等待隊列信息矩陣為一個零矩陣，則不對等待隊列信息矩陣做任何變換。

② 若仿真時鐘所指時刻有新顧客到達，如果等待隊列不滿，則將新到的顧客的信息置于當前等待隊列中最后一名顧客的信息之后，即用此顧客的信息替代第一個元素全為0的矩陣列，如果等待隊列人數已滿，則等待矩陣不更新，此乘客被拒絕。

③ 若仿真時鐘所指時刻無顧客結束服務，也無新顧客到達，則矩陣不發生更新。

2.3 服務臺狀態矩陣

服務狀態矩陣是存放每個服務臺動態信息的矩陣。

(1) 矩陣儲存的信息

服務臺狀態矩陣為一個4×s的矩陣。其中s為系統中服務臺的個數，矩陣的每一列儲存一個服務臺的信息，若第p個服務臺空閑，則矩陣的第p的各行列元素為0;若此服務臺處于忙碌狀態，則矩陣第p列的各行元素所存放的信息如表3所示。

表3 服務臺狀態矩陣

矩陣行矩陣行存放的信息

1服務臺當前所服務的顧客的開始服務時刻

2服務臺當前所服務的顧客服務結束的時刻

3服務臺當前所服務顧客進入排隊系統的時刻

4服務臺忙閑狀態的示性指標

其中，對第四行中服務臺忙閑狀態的示性指標定義如下:

服務臺忙閑狀態的示性指標=

0，服務臺目前空閑1，服務臺目前忙碌

(2) 矩陣初始化

在仿真開始之前，所有服務臺均處于空閑狀態，所以用4×s的零矩陣作為服務臺狀態矩陣的初始化矩陣。

(3) 矩陣的更新算法

隨著仿真時鐘的推進，服務臺狀態矩陣自身的元素需要不斷進行更新，每次仿真時鐘刷新之后，此矩陣就應按照如下算法進行更新。

① 若在仿真時鐘所指的時刻有服務臺處于空閑狀態，且等待隊列中有顧客在等待，則空閑的服務臺依乘客到達時間的順序接受等待隊列中的顧客，更新接受了新顧客的服務臺所對應的矩陣列元素。

② 若在仿真時鐘所指的時刻，有服務臺在剛好完成了對當前顧客的服務任務，如果此時等待隊列中有顧客在排隊，則服務臺同樣依據乘客到達等待隊列的時間先后，依次接收等待隊列中的顧客，并更新相應的矩陣列元素;否則，等待隊列中沒有顧客在等待，則設置服務臺為空閑狀態，將矩陣相應列的4個數值全部歸零。

③ 若以上所述的情況均不發生，則服務臺狀態矩陣不發生更新。

至此，以上3個矩陣所存放的信息，初始化方法及其更新的算法介紹完畢，在此基礎上，給出了M/G/s/K排隊模型的仿真算法，算法流程如圖2所示。

圖2 多服務臺混合排隊系統M/G/s/K仿真流程圖

其中，流程圖中有兩個更新模塊，每個更新模塊都有各自的更新流程，更新模塊1的流程如圖3所示。

圖3 更新模塊1具體流程

更新模塊2的流程如圖4所示。

以上就是本文所給出的M/G/s/K排隊模型的仿真算法。為說明此算法是有效的，這里還需對其進行有效性檢驗。

圖4 更新模塊2具體流程

3 仿真算法有效性的驗證

前面已經提到，當排隊過程不具備馬爾科夫性時，對排隊模型進行基于排隊理論的分析非常困難，而當M/G/s/K排隊模型中顧客服務時間的分布服從特定分布負指數分布時，模型就轉化成為M/M/s/K排隊，且此模型具備馬爾科夫性，可以較為方便地運用排隊理論對這種排隊模型進行分析，進而可以通過對比運用排隊理論分析和仿真算法模擬所得到的結果是否具有一致性來判斷此仿真算法是否對M/M/s/K排隊模型有效，而M/M/s/K排隊模型與M/G/s/K排隊模型的仿真算法僅在服務時間的隨機數生成方面有所不同，因此，如果此仿真算法通過了其對M/M/s/K排隊模型仿真的有效性檢驗，就可以認為此算法對M/G/s/K排隊模型的仿真也是有效的。

下面運用一個汽車加油站的排隊案例[7]來驗證此算法對于M/M/s/K排隊模型的有效性。

某汽車加油站有2臺加油機，汽車按照Poisson流到達，每分鐘到達率為2輛，且汽車加油的時間服從均值為2 min的負指數分布，該加油站的空間有限，最多同時只能容納3輛汽車排隊，若某輛汽車到達時，加油站中已經存在2+3=5輛汽車在系統中，則其不得不開到另外的加油站進行加油。

此系統可以看成一個M/M/2/5排隊系統，此類排隊模型可以直接通過排隊理論的分析得到此排隊系統達到穩定狀態之后的狀況，參考文獻[7]中所給出的M/M/s/K排隊模型的求解方法。此系統中汽車每分鐘到達率為λ=2，加油機每分鐘服務率為μ=0.5，加油機服務強度為ρ=λ/μ=4，服務臺個數為s=2，系統能容納的最大汽車數為K=5，則有:

系統空閑概率為:

p0=∑s-1n=0ρnn!+ρs(1-ρK-s+1s)s!(1-ρs)-1=

1+4+42[1-(4/2)5-2+1]2!(1-4/2)-1=0.008

顧客損失率為:

p=ρKs!sK-sp0=45×0.0082!×25-2=0.512

加油站內在等待的汽車數平均值為:

Lq=p0ρsρss!(1-ρs)2[1-ρK-s+1s-(1-ρs)(K-s+1)ρK-ss]

=0.008×42×(4/2)2!(1-4/2)2[1-(4/2)5-2+1-(1-4/2)#8226;

(5-2+1)×(4/2)5-2]=2.18

加油站內汽車的平均數目為:

L=Lq+s+p0∑s-1n=0(n-1)ρnn!=

2.18+4(1-0.512)=4.13

汽車在加油站內排隊等待的平均時間為:

Wq=Lλ(1-p)-1μ=4.132(1-0.512)-2

=2.23 min=133.8 s

由大數定律可知，若一個仿真算法有效，當仿真次數趨于無窮大的時候，仿真結果的均值應依概率1收斂于排隊理論計算得到的結果。

用上文給出的方法對該汽車加油站排隊案例進行仿真，取1 s為一個步長，汽車每秒鐘的到達率為λs=2/60，汽車接受加油服務中以秒計算的服務率為μs=1/120，取仿真運行的總時間為10 h，即36 000 s，運行已經編輯好的Matlab程序100次，求出所得結果的均值。將得到的仿真結果與理論結果進行比較，如表4所示。

表4 理論結果與仿真結果的比較

分析方式

/指標種類平均等待隊長平均在隊列中的等待時長 /s顧客損失率 /%

排隊論分析結果2.18133.851.20

仿真100次結果均值2.10133.551.21

對比理論計算結果和仿真結果發現，兩者非常接近，從而可以認為本文所給出的仿真算法對于M/M/s/K排隊模型是有效的，進而認為該仿真算法對于M/G/s/K排隊模型是有效的。

4 結 語

運用時間步長法，設計了一種M/G/s/K排隊模型的仿真算法，并驗證了該算法的有效性。

本文所給出的算法流程具有廣泛的適應性，只要通過一些必要的修改，就能勝任其他種類排隊模型仿真任務。相對于以往文獻中所給出的排隊模型的仿真方法，該算法可以滿足更多情況下對于排隊模型仿真的需要。

參考文獻

[1]張建航，李宗成，宋曉峰.單服務員排隊模型及其蒙特卡洛模擬[J].現代電子技術，2006，29(24):44-46.

[2]李鵬，王珊珊.用Matlab實現排隊過程的仿真[J].電腦編程技巧與維護，2009(15):15-17.

[3]宋振峰，席志紅，劉飛.基于Matlab的M/M/m排隊模型的仿真[J].現代電子技術，2005，28(6):29-31.

[4]顏薇娜.基于蒙特卡洛模擬的商業銀行排隊問題研究[J].技術經濟與管理研究，2009(1):20-22.

[5]吳可嘉.蒙特卡洛法在解決食堂窗口排隊問題上的應用[J].大連海事大學學報，2007，33(S1):149-152.

[6]高靜濤，史百戰.基于Matlab的排隊問題仿真[J].武漢工業學院學報，2007，26(2):89-91.

[7]胡運權，郭耀煌.運籌學教程[M].北京:清華大學出版社，2007.

[8]蘇金明，阮沈勇.Matlab實用教程[M].北京:電子工業出版社，2008.

[9]Sheldon M Ross.隨機過程[M].北京:中國統計出版社，1997.

[10]范影樂，楊勝天，李軼.Matlab仿真應用詳解[M].北京:人民郵電出版社，2001.