多服務臺等待制排隊模型M／G／c／∞的蒙特卡洛模擬

王培勛 王志芳

（西安財經(jīng)學院 統(tǒng)計學院，陜西 西安 710100）

多服務臺等待制排隊模型M／G／c／∞的蒙特卡洛模擬

＊王培勛 王志芳

（西安財經(jīng)學院 統(tǒng)計學院，陜西 西安 710100）

文章以排隊論為基礎，用蒙特卡洛在Matlab上對多服務臺等待制排隊模型M／G／c／∞進行了模擬，得到了系統(tǒng)的一些指標，如系統(tǒng)隊長，顧客逗留時間等，并通過兩個實例說明了該方法的可行性，為處理此類排隊問題提供了一個新的方法.

多服臺等待制模型；蒙特卡洛模擬；排隊論；動態(tài)模擬

0 引言

排隊論，或稱隨機服務系統(tǒng)理論，是通過對服務對象到來及服務時間的統(tǒng)計研究，得出諸如等待時間排隊長度，忙期長短等這些數(shù)量指標的統(tǒng)計規(guī)律，然后根據(jù)這些規(guī)律來改進服務系統(tǒng)的結(jié)構(gòu)或重新組織被服務對象，使得服務系統(tǒng)能滿足服務對象的需求，又能使機構(gòu)的費用最經(jīng)濟或某些指標最優(yōu)，這些指標一般可以通過數(shù)學推導得到.但是在實際問題中所碰到的排隊問題往往不具有馬爾科夫性，這時用數(shù)學推導就比較困難.隨著計算機技術的發(fā)展，運用計算機仿真的方法來研究排隊模型已成為解決這類排隊問題的有效方法.國內(nèi)外學者在研究這類問題已經(jīng)取得了一些成果，如張建航等在論文中給出了單服務臺排隊模型M／M／1／∞的蒙特卡洛模擬，得到了顧客的等待時間和系統(tǒng)隊長［1］，李鵬等通過Matlab平臺對單服務臺有限隊長的排隊系統(tǒng)進行了仿真，仿真出各個顧客到達時刻與離開時刻曲線，等待時間與停留時間曲線［2］，吳可嘉在Excel上實現(xiàn)了對單對多服務臺的模擬，得出了學校食堂應該再增加一個窗口可以滿足服務需求的結(jié)論［3］.但是目前對多服務臺等待制排隊模型M／G／c／∞的模擬還是比較少的，本文運用蒙特卡洛模擬方法，研究M／G／c／∞模型的仿真算法.

1 排隊論及M／G／c／∞模型介紹

排隊論是研究系統(tǒng)隨機聚散現(xiàn)象和隨機服務系統(tǒng)工作過程的數(shù)學理論和方法，排隊論的排隊規(guī)則分為3類：損失制、等待制和混合制.其中，損失制是指顧客到達時，如果所有服務臺都沒有空閑，該顧客不愿等待，就隨即從系統(tǒng)消失；等待制是指顧客到達時，如果所有服務臺都沒有空閑，他們就排隊等待；混合制是指既有等待又有損失的情況，如顧客等待時考慮排隊的隊長、等待時間的長短等因素而決定去留.

本文所模擬的是多服務臺等待制排隊模型M／G／c／∞，系統(tǒng)空間是無限的，顧客來源也是無限的，即設系統(tǒng)有c個服務窗口并聯(lián)排列，各服務窗口獨立工作，又各窗口的服務時間服從一般分布G，假設顧客按參數(shù)為λ的泊松分布到達，即顧客到達的間隔服從指數(shù)分布，如果顧客到達系統(tǒng)時c個服務窗都忙著，則顧客排隊等待，并且假設各個服務窗口工作時相互獨立的遵循先到先服務原則，允許永遠排隊.

2 隨機數(shù)的產(chǎn)生

1）在各種統(tǒng)計計算中常需要產(chǎn)生各種概率分布的隨機數(shù)，而大多數(shù)概率分布的隨機數(shù)的產(chǎn)生均基于均勻分布U（0，1）的隨機數(shù)，產(chǎn)生隨機數(shù)的基本方法有三種，逆變換法，合成方法，篩選方法.這里我們用擬變換法來產(chǎn)生分布函數(shù)的隨機數(shù).首先介紹逆變換法.設隨機變量X的分布函數(shù)為F（X），定義F－1（y）＝infx：F（x）≥ ｝｛y，0≤y≤1，有如下定理：

定理設隨機變量U～U（0，1），則X＝F－1（U）的分布函數(shù)為F（x）［4］.

由此定理我們可以知道要產(chǎn)生來自F（x）的隨機數(shù)，只要先產(chǎn)生來自U（0，1）的隨機數(shù)u，然后計算F－1（u）即可，具體步驟是首先由U（0，1）抽取u，然后計算x＝F－1（u），其中F－1如上訴中定義.當我們得到了分布函數(shù)的隨機數(shù)的產(chǎn)生方法以后，我們就可以進行隨機模擬了，隨機模擬方法也稱為蒙特卡洛模擬方法，它是以概率統(tǒng)計理論為基礎，利用電子計算機數(shù)字模擬技術，解決一些很難直接用數(shù)學求解或用其他方法不能解決的問題，它的實質(zhì)是運用一連串的隨機數(shù)來模擬可能出現(xiàn)的隨機現(xiàn)象.

2）仿真系統(tǒng)模擬，設T為模擬系統(tǒng)的總服務時間，t為時間變量，t1為顧客的到達系統(tǒng)的時間，d為1×c矩陣，第j列記錄第j個服務臺上顧客的離開的時間，t2＝min（d），即顧客最早離開服務臺的時間，n為在t時刻當前到達系統(tǒng)中的顧客數(shù)，A為在t時刻到達系統(tǒng)中的所有顧客總數(shù).設循環(huán)變量為i，g（i）記錄在一次循環(huán)中不同事件發(fā)生的時間間隔，h（i）記錄在一次循環(huán)中系統(tǒng)中的顧客數(shù)，c為1×c矩陣，記錄c個服務臺的工作狀態(tài)，其中元素為1表示該服務臺正忙，元素為0表示該服務臺處于空閑狀態(tài)，設變量b為系統(tǒng)當前的顧客數(shù).

模擬算法；

Step1 初始化，輸入模擬系統(tǒng)的總服務時間T，設t＝0，n＝0，A＝0此時系統(tǒng)中沒有顧客，所有服務臺都空閑，c矩陣各列元素都為0，d矩陣各列元素都是∞，b＝0.

Step2 產(chǎn)生第一個顧客進入系統(tǒng)的時間t1，這時循環(huán)變量i＝0.

Step3 進入循環(huán)，i＝i＋1，h（i）＝b，如果t1＜T，則有g（i）＝min（t1－t2）－t，否則結(jié)束.

Step4 如果t1＜t2，說明顧客進入系統(tǒng)的時間小于服務臺上顧客的離開時間，使t＝t1，產(chǎn)生下一顧客進入系統(tǒng)的時間t1，這時總顧客數(shù)多了一個，A＝A＋1，n＝n＋1，b＝n，即系統(tǒng)中的顧客數(shù)也加1，如果有c（j）＝0，說明第j個服務臺空閑，將系統(tǒng)中的顧客分配給第j個服務臺，同時產(chǎn)生第j個服務臺上顧客的離開時間.

Step5 如果t1≥t2，說明有顧客離開服務臺，使t＝t2，系統(tǒng)中的顧客減少了一個，n＝n－1，b＝n，此時如果系統(tǒng)中還有顧客，就上前服務，同時產(chǎn)生其離開時間，然后轉(zhuǎn)Step3，直至t1＞T.

3 實例分析

實例1 設有3個打字員，平均打印文件的速度為μ＝6份／小時，文件到達率為15份／小時，試求1）在打字室內(nèi)現(xiàn)在有的平均文件數(shù)；2）每份文件在打字室平均停留時間；3）3個打字員均不空閑的概率.

我們可以看到這是M／M／c／∞模型，運用排隊論的數(shù)學計算公式有：

如果用上文給出的方法進行仿真，題中顧客的到達時間和接受服務的時間都服從泊松過程，由概率知識可知，當隨機過程是強度為λ的泊松過程時，其點間間距是相互獨立的隨機變量，且服從參數(shù)為λ的指數(shù)分布，即

表1 模擬結(jié)果與理論值對比

對比理論計算結(jié)果和仿真結(jié)果發(fā)現(xiàn)，兩者非常接近，說明本文提出仿真方法有效可行，我們可以通過增加模擬次數(shù)來提高模擬精度.

實例2 某高校工商銀行設有三個服務臺，營業(yè)時間為早上8時到下午16時，新來的顧客到達后，若已有顧客正在接受服務，則需要排隊等待.假設顧客流為負指數(shù)分布，且顧客到來的平均時間間隔為2.5 min，窗口的服務時間服從U（2，4）分布，求系統(tǒng)隊長，顧客的逗留時間和顧客的等待概率.由題可知，為M／G／c／∞模型，其中G～U（2，4），該模型不具有馬爾可夫性，用數(shù)學推導的方式比較困難的，這時可以用計算機進行模擬，首先產(chǎn)生窗口服務時間U（a，b）的隨機數(shù)，其密度函數(shù)如下：

由逆變換法，有ti＝a＋（b－a）ui，i＝1，2，…，ui～U（0，1）.此題中，a＝2，b＝4，由U（0，1）抽得u，則t＝2＋2u是來自u（2，4）的一個隨機數(shù)，有了窗口服務時間的隨機數(shù)，我們就可以根據(jù)前面介紹的算法編寫Matlab程序，模擬100次，結(jié)果如表2.

表2 模擬結(jié)果

4 結(jié)語

本文用蒙特卡羅的思想，涉及了排隊模型的仿真算法，并驗證了該算法的有效性，蒙特卡洛模擬法在求解排隊系統(tǒng)參數(shù)中，有一定的優(yōu)越性和實用性，并且在其他排隊系統(tǒng)的模擬中均有指導意義，由于隨機服務系統(tǒng)本身的概率規(guī)律性，要用解析的方法來處理一個復雜的隨機服務系統(tǒng)有時候比較困難，而模擬自身的特點成為解決這一問題很好的方法.本文介紹的仿真方法具有一定的普遍性，可以運用于商場，銀行和醫(yī)院等系統(tǒng)，如可以針對不同時段的顧客流量和服務水平的變化進行仿真，得到不同狀況下商場應該設置多少個收款臺，多少個服務員，才能適合變化的顧客流，提高顧客流服務量，實現(xiàn)自身系統(tǒng)的優(yōu)化，對于指導生產(chǎn)生活有比較重要的現(xiàn)實意義.

［1］張建航，李宗成，宋曉峰.單服務員排隊模型及其蒙特卡洛模擬［J］.現(xiàn)代電子技術，2006，29（24）：44-46

［2］李 鵬，王珊珊.用 Matlab實現(xiàn)排隊過程的仿真［J］.電腦編程技巧與維護，2009，15：15-17

［3］吳可嘉.蒙特卡洛法在解決食堂窗口排隊問題上的應用［J］.大連海事大學學報，2007（33）：149-152

［4］茆詩松，王靜龍.高等數(shù)理統(tǒng)計［M］.北京：高等教育出版社，2006：401-404

［5］顏薇娜.基于蒙特卡洛模擬的商業(yè)銀行排隊問題研究［J］.技術經(jīng)濟與管理研究，2009（1）：20-22

［6］高靜濤.基于 Matlab的排隊問題仿真［J］.武漢工業(yè)學院學報，2007，26（2）：89-91

Monte Carlo Simulation ofM／G／c／∞ Multi Servers Queuing Model

Wang Peixun Wang Zhifang
（School of Statistics，Xi’an University of Finance and Economics，Xi’an 710100，China）

Based on queuing theory for the theoretical basis，Monte Carlo simulation in Matlab to simulation on the queuing model of multi severs is used，and after analying the model same indicators are got such as mean sojourn time of a served customer，average queue length.The validity of this simulation algorithm is demonstrated and a new method to deal with problems of this category is provided.

queuing model of multi servers；Monte Carlo simulation；queuing theory；dynamic simulation

王映苗】

1672-2027（2012）01-0095-04

TP311.1

A

2011-12-24

王培勛（1956-），男，甘肅岷縣人，碩士，西安財經(jīng)學院統(tǒng)計學院教授，主要從事統(tǒng)計建模研究.