帶優(yōu)先級的多服務臺排隊系統(tǒng)Monte Carlo模擬

[摘 要]本文研究帶優(yōu)先級的多服務臺的隨機模擬排隊系統(tǒng)中的排隊次序問題，為各個排隊顧客引入服務優(yōu)先級，利用Monte Carlo算法對服務系統(tǒng)進行仿真計算，預測其大致接受服務時間區(qū)間。在醫(yī)院病床安排的實例中，借助于計算機操作系統(tǒng)中的動態(tài)優(yōu)先級調(diào)度算法，可減少患者平均等待入院時間，從而提高服務臺的利用率，同時減小了顧客最長等待時間。該方法有較強應用價值。

[關鍵詞]等待時間 優(yōu)先級 蒙特卡洛 服務時間

一、問題提出

(一)問題敘述

現(xiàn)實中的很多服務，等待時間超過一天，比較典型的是醫(yī)院住院及手術安排的問題。盡管隨機服務與排隊論問題早已得到深入研究，但某服務系統(tǒng)共有服務臺M個，其服務分四大類:每種服務目前的規(guī)則是:每周一、三處理 ;而是緊急服務，處理中心有空閑時立即安排處理，其他服務可根據(jù)需要安排，但是不安排在周一、周三。系統(tǒng)的示意圖見圖1。本文要研究的問題是如何建立數(shù)學模型，實現(xiàn)對服務臺的合理安排，根據(jù)目前接受服務顧客及等待接受服務顧客的統(tǒng)計情況，在開始排隊時預測其大致接受服務時間區(qū)間。

(二)名詞解釋

1.等待服務時間(等待時間):顧客從開始排隊到進入服務臺的時間。

2.最長等待時間:等待時間最長的顧客需要等待的時間。

3.動態(tài)優(yōu)先級調(diào)度算法:Monte Carlo算法的一種，計算機操作系統(tǒng)中CPU調(diào)度的經(jīng)典算法之一，利用動態(tài)優(yōu)先級實現(xiàn)對就緒進程的調(diào)度。就緒進程占用CPU時間愈長，該進程優(yōu)先級越低，反之，優(yōu)先級越高;就緒進程等待CPU時間越長，優(yōu)先級越高，反之越低。在該模型中引入此算法，相當于降低用戶平均等待時間和最長等待時間，從而提高顧客的滿意程度和服務系統(tǒng)服務臺利用率。

二、問題研究

(一)基本假設

1.服務系統(tǒng)條件充分，而且預測的時間范圍內(nèi)，顧客到來情況是平穩(wěn)的，且顧客按正常時間離開，無長時間占用服務臺的現(xiàn)象。

2.假設顧客到來的事件流是一泊松流，且不會等待不耐煩而離去。

3.各個服務臺功能相同。

(二)符號說明

: 平均等待時間

: 最長等待時間

: 第i類服務平均每天到來人數(shù)

: 在預測時間范圍內(nèi)第i類服務每天到來人數(shù)的模擬值

:需要第類服務的顧客在星期到來需要在服務系統(tǒng)接受服務的時間

: 等待隊列中 號顧客已經(jīng)等待的時間

:星期到來的號顧客預計要接受服務的時間

( =1，2，3，4，5，6，7)

: 編號為的顧客的優(yōu)先級

:每天平均離開的人數(shù)

:預測的第類服務的顧客需要等待的時間

:當前等待隊列中的人數(shù)

:每天到來的第類服務的人數(shù)

:第類服務的顧客平均接受服務時間

(三)模型的建立

本模型要實現(xiàn)的目標是即提高服務系統(tǒng)接受服務部的吞吐量，進而降低顧客等待時間，實現(xiàn)服務系統(tǒng)與顧客的互利。基于該目標，本文引入經(jīng)典的動態(tài)優(yōu)先級調(diào)度算法，初始時給予需要接受服務時間較短的顧客更高的優(yōu)先級(計算機模擬結果顯示，此項做法可縮短顧客平均等待時間)。隨著等待時間的延長，逐步提高顧客的優(yōu)先級，因而可將顧客最長等待時間縮短。

根據(jù)上述思路，本文建立一個基于顧客優(yōu)先級的調(diào)度模型，并引入Monte Carlo算法。

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

①確定

由于在不重疊時間區(qū)間內(nèi)到服務系統(tǒng)到來的不同服務顧客是相互獨立的，故可以假設顧客到來的事件流是一泊松流，并滿足如下表達式:

如果相繼兩個時間出現(xiàn)的間隔時間為負指數(shù)分布，則在某一時間間隔內(nèi)時間出現(xiàn)的次數(shù)滿足泊松分布，于是可以用負指數(shù)分布的隨機變量來組合產(chǎn)生泊松分布的隨機數(shù)列。

設為參數(shù)負指數(shù)分布的隨機數(shù)序列，因為有

因此，將 值按序累加，使得滿足關系式:

則求得的就是參數(shù)的泊松分布的隨機數(shù)。

②確定

在假設條件下，可認為近似等于各類顧客平均接受服務時間，進而根據(jù)號顧客的服務類型和 的值確定 。

3.2優(yōu)先級模型的建立

首先，在到來時為每個顧客依次編號并分配初始優(yōu)先級，緊急服務顧客的優(yōu)先級最大，可近似于無窮大，即該優(yōu)先級高于其它任何服務顧客在任何情況下的優(yōu)先級，從而保證緊急服務顧客盡快接受服務。其它服務中編號為的顧客的優(yōu)先級可按下列關系式確定:

其中為比例系數(shù)。根據(jù)的變化實時調(diào)整號顧客的優(yōu)先級。每天按照新的優(yōu)先級次序把顧客排成新的等待隊列，優(yōu)先級高的顧客排在隊列前面，反之，優(yōu)先級低的排在后面。只要有可利用服務臺，先安排緊急服務顧客進入，在還有剩余服務臺的情況下，根據(jù)等待隊列的順序安排需要有其它類型服務的顧客接受服務。當不同顧客的優(yōu)先級相同時，按照FCFS的規(guī)則安排接受服務。

在算法設計中，初始時賦予需要接受服務時間較短的顧客更高的優(yōu)先級，從而使減小;同時隨著的增長，顧客優(yōu)先級提高，避免了顧客長時間等待的情況。這樣既保證了需要接受服務時間較短的顧客優(yōu)先接受以獲取較高的服務臺利用率，又避免了某些顧客需要長時間等待。

比例系數(shù)用于調(diào)整兩個因素(和)在不同條件、前提和要求下的權重，在該模型中，不妨取 ，可通過模擬結果驗證取值的合理性。

三、Monte Carlo算法設計

根據(jù)上述模型，設計算法如下:

Step1:在泊松流假設下生成一天內(nèi)各類顧客到來的隨機數(shù)，并將這些不同服務的顧客按到來時間隨機排序，到來時對其編號(根據(jù)服務類型)賦予每個顧客一個初始優(yōu)先級(此時 )，并將其加入等待隊列。

Step2: 計算當天要離開的人數(shù)。

Step3: 如有緊急服務顧客等待接受服務，則按照FCFS的規(guī)則優(yōu)先安排此類顧客接受服務;如沒有緊急服務顧客等待或將其安排完畢后仍有空閑服務臺，則按照優(yōu)先級由大到小的順序安排等待隊列中的顧客進入，直到服務臺完全利用或等待隊列為空。

Step4: 第二天調(diào)整等待隊列中顧客的使得 ，帶入 調(diào)整優(yōu)先級，轉入Step1循環(huán)執(zhí)行。

四、醫(yī)院病床安排的實例分析

下面是某眼科診所2008-7-13到2008-9-11的病人信息分別是各類病人每天的平均就診人數(shù)、一周中每天入院的不同類型病人平均住院時間、當前醫(yī)院病床利用情況等相關數(shù)據(jù)。其中，白內(nèi)障相當于，外傷對應于 。

表 1星期一星期二星期三星期四星期五星期六星期日

白內(nèi)障5.44.47.57.3755.69230853.611111

白內(nèi)障(雙眼)12.2510.62510.133339.1257.86.8571436

青光眼11101010.810.8333311.333338.333333

視網(wǎng)膜疾病13.51311.213.1538511.4210513.3214312.54545

外傷7.16.7777785.757.5777.666667

表 2每天入院的患有各類眼疾的病人平均住院時間

白內(nèi)障白內(nèi)障(雙眼)青光眼視網(wǎng)膜疾病外傷

1.6393442622.1803278691.0327868852.7868852461.049180328

表 3各類眼疾平均日就診人數(shù)

通過對表2的分析，得到五種病的平均住院時間為

白內(nèi)障白內(nèi)障(雙眼)青光眼視網(wǎng)膜疾病外傷

平均住院時間5.5683468.97006810.3285712.591686.970635

表 4五種病的平均住院時間

將以上數(shù)據(jù)輸入Monte Carlo算法，經(jīng)計算，得到結果:

平均等待時間(單位:天)

FCFS12.95845

基于優(yōu)先級的病床安排模型8.91789

表 5

立刻可以看出，該算法的安排結果遠遠好于先到先服務的安排模式。

五、排隊預測模型

在(預測的第種病的患者需要等待的天數(shù))天內(nèi)，出院人數(shù)為 ，即共有個床位可接納新的病人，利用出院人數(shù)等于入院人數(shù)，可建立等式進而求解 的值。

以預測一名視網(wǎng)膜疾病患者的入院時間為例進行說明:因為視網(wǎng)膜疾病患者平均住院時最長，故其初始優(yōu)先級最低。經(jīng)分析，在 天內(nèi)，排在這名患者前面進入醫(yī)院接受治療的患者可分為以下幾類:

①在該患者門診就診時已經(jīng)進入等待住院隊列中的所有患者。此類患者人數(shù)為 ，是已知數(shù)據(jù)。

②天內(nèi)所有的急癥患者，可近似等于 。

③天內(nèi)就診的患有其它幾類疾病(白內(nèi)障、雙眼白內(nèi)障、青光眼)的患者在該患者入院之前的時間內(nèi)，優(yōu)先級超過該患者的。分析此情況時，需利用上文建立的基于患者優(yōu)先級的病床分配模型，計算優(yōu)先級的表達式為:，可將其簡化為基于優(yōu)先級的病床安排的簡化模型，具體做法為:將比例系數(shù)設定為1，將一周中每天入院的同類病人住院時間近似為相等的，即利用代替。經(jīng)分析比較，在該患者就診后的天內(nèi)就診的青光眼患者具有更高的優(yōu)先級，同理，在該患者就診后天內(nèi)就診的雙眼白內(nèi)障患者、天內(nèi)就診的單眼白內(nèi)障患者也具有更高的優(yōu)先級。綜上所述，此類患者總數(shù)為: 。

根據(jù)以上分析可得到等式:

對于其他幾類疾病患者，預測入院時間的情況類似該視網(wǎng)膜疾病患者，經(jīng)歸納總結，得到預測患者入院時間的通式:

經(jīng)整理可得:

利用計算機模擬運用優(yōu)先級模型進行病床安排的實際情況，運用MATLAB軟件統(tǒng)計整理每天出院人數(shù)的數(shù)據(jù)，通過最小二乘估計，得到

當置信度為0.95時，置信區(qū)間為 ，則近似將每天平均出院人數(shù)的上界定為10.4188，下界定為8.1582，將其帶入上式得到

這就是利用該模型預測出的病人入住時間區(qū)間。

經(jīng)過代入數(shù)據(jù)計算，當下一位病人患病類型依次為白內(nèi)障、雙眼白內(nèi)障、青光眼、視網(wǎng)膜疾病時，預測該病人入住時間區(qū)間分別是[7.5754，9.98638]、[10.3804，13.6841]、[11.4277，15.0648]、[13.3683，17.623];通過計算機模擬得到該病人的等待時間，經(jīng)多次仿真計算，得到的以上區(qū)間的置信度分別為99.48%、80.43%、89.92%、99.32%，進一步證明了該預測方法的準確性與可靠性。

六、小結

用動態(tài)優(yōu)先級調(diào)度算法隨機模擬是本文模型的核心，利用計算機編程進行模型得出了令人滿意的結果，可以滿足實用的需要。排隊預測模型中又推導出了接受服務時間的預測公式，具有廣大的推廣空間。

參考文獻:

[1] 刁在筠，劉桂真，宿潔，馬建華.運籌學[M].北京:高等教育出版社.2007年.

[2] 肖立順，石玉文，黃勇博.銀行排隊系統(tǒng)的隨機分析.信息與電腦[J].2009年第8期.

[3] 黃水松，黃干平等.計算機操作系統(tǒng)[M].武漢:武漢大學出版社.2003年.

[4] 趙靜，但奇.數(shù)學建模與數(shù)學實驗[M].北京:高等教育出版社.2003年.

[5] 李驥昭，劉義山.成批到達多服務臺排隊系統(tǒng)模型分析[J].機電產(chǎn)品開發(fā)與創(chuàng)新.第22卷第3期.

[6] 劉次華，何少鋒.批量到達的離散時間排隊系統(tǒng)[J].華中科技大學學報.第33卷第10期.