帶優(yōu)先權的排隊論模型

1、帶優(yōu)先權的排隊論模型在優(yōu)先權排隊模型中，隊中的成員被服務的順序基于他們被賦予的優(yōu)先級。相比一般的排隊模型，很多真實存在的排隊系統(tǒng)實際上更符合帶優(yōu)先權的排隊論模型，比如緊急工作的招聘優(yōu)先于其他一般的工作；VIP客戶較其他一般客戶，在服務上享有優(yōu)先權等等。因此，帶優(yōu)先權的排隊論模型有其實際意義。這里介紹兩種最基本的優(yōu)先權排隊模型一一非強占性優(yōu)先權模型和強占性優(yōu)先權模型。兩個模型除優(yōu)先權行使方式之外，其他假設均一致。我們首先描述這兩個模型,之后分別給出其結論，最后通過一個案例來闡述其在實際中的應用。1.模型公共假設：（1）兩個模型都存在N個優(yōu)先級（1級代表最高）（2）服務順序首先基于優(yōu)先級，同一優(yōu)先

2、級內(nèi)，依據(jù)“先到先服務”（3）對任意優(yōu)先級，顧客到達服從Poisson分布，服務時間服從負指數(shù)分布（4）對任意優(yōu)先級顧客的服務時間相同（5）不同優(yōu)先級顧客的平均到達率可以不同非強占性優(yōu)先權（NonpreemptivePriorities）是指，即使一個高優(yōu)先級的顧客到達，也不能強制讓一個正在接受服務的低優(yōu)先級顧客返回排隊。也就是說，一旦服務員開始對一個顧客服務，這項服務就不能被打斷直至服務結束。強占性優(yōu)先權（PreemptivePriorities）是指，一旦有高優(yōu)先級的顧客到達，服務員即中斷對低優(yōu)先級顧客的服務（這名顧客重新回到排隊中），并馬上開始為高優(yōu)先級顧客服務。結束這項服務后，再按照公

3、共假設中的原則選取下一個被服務的顧客。（這里由于負指數(shù)分布的無記憶性，我們不必關注被中斷顧客的服務進度，因為剩余服務時間的分布與從起點開始的服務時間的分布總是相同的。）對這兩個模型來說，如果忽略顧客的優(yōu)先級，它們是完全等同于一般的M/M/s排隊模型的。因此，當計算整個隊列中顧客的總人數(shù)（L4）時，M/M/s模型的結論是適用的：實際上，若隨機選擇一個顧客，其等待時間（W,%）也可以通過Little公式計算得出。我們改變的只是顧客們等待時間的分布。在優(yōu)先權排隊模型下，等待時間的的方差更大，高優(yōu)先級的顧客縮短了等待時間，而低優(yōu)先級的顧客增長了等待時間。為了體現(xiàn)優(yōu)先權對排隊模型的影響，我們需要計算每一

4、個優(yōu)先級上顧客的平均等待時間（%,k=l,2,N）和平均隊長（Lk,k=l,2,N）o2 .結論用做表示穩(wěn)定狀態(tài)下k優(yōu)先級的顧客平均等待時間（包括服務時間），則兩個模型的結論可以表示如下。非搶占性模型（M/M/s）fork=1,2，N,s/z-2rirJwhereA=s!-“ISAs=lumiberofservers,/=meanservicerateperbusyserveizA=meanarrivialrateforpriorityi,4（這里假設了玄4<S4,從而使第k個優(yōu)先級能夠達到穩(wěn)定狀態(tài)。）1=1Little公式對任意優(yōu)先級仍然適用，所以L*一一第k個優(yōu)先級在穩(wěn)定狀態(tài)下的平均

5、隊長（包括正在接受服務的顧客）可以表示為：二4叫，fork=1,2,.,N強占性模型（WM/1）1/Z叫fork=1,2,.,N注意到這里的結論適用于僅有一個服務臺的情況，但實際上對于s>1的情況，以可以通過簡單的迭代得出，該方法在案例中會做介紹。同樣，應用Little公式,可得第k個優(yōu)先級在穩(wěn)定狀態(tài)下的平均隊長（包括正在接受服務的顧客）：3 .案例市醫(yī)院急診中心的問題管理咨詢顧問注意到市醫(yī)院的急診病人并沒有簡單地按照達到順序接受治療，實際上病人大致被分為三類：（1）病危型，病情致命，必須馬上治療：（2）嚴重型，拖延治療會使病情加重；（3）平穩(wěn)型，治療不及時并沒有嚴重的后果。病人們按照以

6、上優(yōu)先級進行排隊，每個優(yōu)先級內(nèi)部再按照到達順序排隊。預測顯示，大約有10%的病危型病人，30%的嚴重型病人，60%的平穩(wěn)型病人。因為嚴重的疾病在緊急處理后還要進行進一步治療，所以花在急診室的時間并不是很長，進而我們可以認為三種類型的病人接受治療的時間是相同的。由于病危病人和嚴重型病人的治療不能耽誤，所以這是一個強占性優(yōu)先權排隊模型。數(shù)據(jù)顯示|J=3,A=2,因此可求得ai=0.2,A2=0.6,A3=l.2o通過對比s=l和s=2時的情況，說明是否有必要在急診室增加一個醫(yī)生。用Excel計算的數(shù)據(jù)如下表所示。（為了對比，同時給出在非搶占性模型下的各項數(shù)據(jù)。）Wl-1/pW2-1/|JW3-1/

7、PPreemptivePrioritiesNonpreemptivePrioritiess=1s=2s=1s=20.024hour0.154hour1.033hour0.238hour0.029hour0.325hour0.033hour0.889hour0.048hour下面來計算s二2時，強占性模型下的每個優(yōu)先級病人的平均等待時間。由于第一優(yōu)先級的病人的等待時間并不受其他優(yōu)先級的影響，所以對任意的即、入3，跖取值相同，當乙二加二0時，電與一般M/M/s模型中當s=2,=3,A二；11=0.2時W的取值相同。即W=W=鞏+工=%+=此=0.00037小時，其中p=w_,s"p/1”

8、/）"（切江一。/Jn!s!l-/（s/z）故列一L=0.00037小時。下面考慮前兩個優(yōu)先級。同理，這兩個優(yōu)先級的病人也不受第三優(yōu)先級的影響。令斯2為隨機到達的前兩個優(yōu)先級的病人的平均等待時間，則該病人是第一優(yōu)先級的屆率為4/（4+4）=1/4,是第二優(yōu)先級的概率為4/（4+4）=3/4。13故Wi_2=T+_W）,44另一方面,Wi.2與一般M/M/s模型中當s=2,|J=3,A=21+22=08時W的取值相同。即而1-2=W=O.33937小時,從而=0.34126小時,4 1zWj=-033937-(0.3337)故W,-L=0.00793小時。-4同理，令W”為隨機到達的病

9、人的平均等待時間，有可卜3=0.叫+。型+06%,而1_3與一般M/M/s模型中當s=2,p=3,A=Ai+A2+A3=2時W的取值相同。即Wi-3=W=0.375小時，從而叱=0.375-0.1(0.3337)-03(0.34126)=0.39875小時,0.6故閃一2_=0.06542小時。所以，完整的數(shù)據(jù)對比表如下：PreemptivePrioritiesNonpreemptivePrioritiesS=1s=2S=1s=2Wl-1/p0.024hour0.00037hour0.238hour0.029hourW2-l/p0.154hour0.00793hour0.325hour0.033hourW3-1/JJ1.033hour0.06542hour0.889hour0.048hour從中可以看出，強占性模型下，若只有一名醫(yī)生，在接受治療前，病危型病人