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

[關(guān)鍵詞]等待時(shí)間 優(yōu)先級(jí) 蒙特卡洛 服務(wù)時(shí)間

一、問(wèn)題提出

(一)問(wèn)題敘述

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

(二)名詞解釋

1.等待服務(wù)時(shí)間(等待時(shí)間):顧客從開始排隊(duì)到進(jìn)入服務(wù)臺(tái)的時(shí)間。

2.最長(zhǎng)等待時(shí)間:等待時(shí)間最長(zhǎng)的顧客需要等待的時(shí)間。

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

二、問(wèn)題研究

(一)基本假設(shè)

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

2.假設(shè)顧客到來(lái)的事件流是一泊松流，且不會(huì)等待不耐煩而離去。

3.各個(gè)服務(wù)臺(tái)功能相同。

(二)符號(hào)說(shuō)明

: 平均等待時(shí)間

: 最長(zhǎng)等待時(shí)間

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

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

:需要第類服務(wù)的顧客在星期到來(lái)需要在服務(wù)系統(tǒng)接受服務(wù)的時(shí)間

: 等待隊(duì)列中 號(hào)顧客已經(jīng)等待的時(shí)間

:星期到來(lái)的號(hào)顧客預(yù)計(jì)要接受服務(wù)的時(shí)間

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

: 編號(hào)為的顧客的優(yōu)先級(jí)

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

:預(yù)測(cè)的第類服務(wù)的顧客需要等待的時(shí)間

:當(dāng)前等待隊(duì)列中的人數(shù)

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

:第類服務(wù)的顧客平均接受服務(wù)時(shí)間

(三)模型的建立

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

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

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

①確定

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

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

設(shè)為參數(shù)負(fù)指數(shù)分布的隨機(jī)數(shù)序列，因?yàn)橛?/p>

因此，將 值按序累加，使得滿足關(guān)系式:

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

②確定

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

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

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

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

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

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

三、Monte Carlo算法設(shè)計(jì)

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

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

Step2: 計(jì)算當(dāng)天要離開的人數(shù)。

Step3: 如有緊急服務(wù)顧客等待接受服務(wù)，則按照FCFS的規(guī)則優(yōu)先安排此類顧客接受服務(wù);如沒(méi)有緊急服務(wù)顧客等待或?qū)⑵浒才磐戤吅笕杂锌臻e服務(wù)臺(tái)，則按照優(yōu)先級(jí)由大到小的順序安排等待隊(duì)列中的顧客進(jìn)入，直到服務(wù)臺(tái)完全利用或等待隊(duì)列為空。

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

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

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

表 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每天入院的患有各類眼疾的病人平均住院時(shí)間

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

1.6393442622.1803278691.0327868852.7868852461.049180328

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

通過(guò)對(duì)表2的分析，得到五種病的平均住院時(shí)間為

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

平均住院時(shí)間5.5683468.97006810.3285712.591686.970635

表 4五種病的平均住院時(shí)間

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

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

FCFS12.95845

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

表 5

立刻可以看出，該算法的安排結(jié)果遠(yuǎn)遠(yuǎn)好于先到先服務(wù)的安排模式。

五、排隊(duì)預(yù)測(cè)模型

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

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

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

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

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

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

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

經(jīng)整理可得:

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

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

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

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

六、小結(jié)

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

參考文獻(xiàn):

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

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

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

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

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

[6] 劉次華，何少鋒.批量到達(dá)的離散時(shí)間排隊(duì)系統(tǒng)[J].華中科技大學(xué)學(xué)報(bào).第33卷第10期.