帶優(yōu)先權(quán)的排隊(duì)論模型

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

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

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

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

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

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

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

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

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