帶優(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í)

2、，同一優(yōu)先級(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)（Nonpreemptive Priorities）是指，即使一個(gè)高優(yōu)先級(jí)的顧客 到達(dá)，也不能強(qiáng)制讓一個(gè)正在接受服務(wù)的低優(yōu)先級(jí)顧客返回排隊(duì)。也就是說(shuō)，一 旦服務(wù)員開始對(duì)一個(gè)顧客服務(wù)，這項(xiàng)服務(wù)就不能被打斷直至服務(wù)結(jié)束。強(qiáng)占性優(yōu)先權(quán)（Preemptive Priorities）是指，一日.有高優(yōu)先級(jí)的顧客到達(dá)， 服務(wù)員即中斷對(duì)低優(yōu)先級(jí)顧客的服務(wù)（這名顧客重新回到排隊(duì)中），并馬上開始 為高優(yōu)先級(jí)顧客服務(wù)

3、。結(jié)束這項(xiàng)服務(wù)后，再按照公共假設(shè)中的原則選取下一個(gè)被 服務(wù)的顧客。（這里由于負(fù)指數(shù)分布的無(wú)記憶性，我們不必關(guān)注被中斷顧客的服 務(wù)進(jìn)度，因?yàn)槭Ｓ喾?wù)時(shí)間的分布與從起點(diǎn)開始的服務(wù)時(shí)間的分布總是相同的。）對(duì)這兩個(gè)模型來(lái)說(shuō)，如果忽略顧客的優(yōu)先級(jí)，它們是完全等同于一般的M/M/s 排隊(duì)模型的。因此，當(dāng)計(jì)算整個(gè)隊(duì)列中顧客的總?cè)藬?shù)（L,Lq）時(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í)間。為了

4、體現(xiàn)優(yōu)先權(quán)對(duì)排隊(duì)模型的影響，我們需要計(jì)算每 一個(gè)優(yōu)先級(jí)上顧客的平均等待時(shí)間（叫，燈1,2,N）和平均隊(duì)長(zhǎng)（4, k=l,2,N）o2, 結(jié)論用以表示穩(wěn)定狀態(tài)下k優(yōu)先級(jí)的顧客平均等待時(shí)間（包括服務(wù)時(shí)間），則兩 個(gè)模型的結(jié)論可以表示如下。非搶占性模型（M/Ws）寸盡+ 土fork =s/z-2rirJ where A= s! F餌J!烏二1,s = lumiber of servers, / = mean service rate per busy servei ,A = mean arrivial rate for priority i,（這里假設(shè)了立4 < S，從而使第k個(gè)優(yōu)先級(jí)能夠達(dá)到

5、穩(wěn)定狀態(tài)。） 1=1Little公式對(duì)任意優(yōu)先級(jí)仍然適用，所以扇一一第k個(gè)優(yōu)先級(jí)在穩(wěn)定狀態(tài) 下的平均隊(duì)長(zhǎng)（包括正在接受服務(wù)的顧客）可以表示為：= 4珥，for k = 1, 2,. ., N強(qiáng)占性模型（W1）1/u珥=三-, for k = 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ī)院的急診病人并沒有簡(jiǎn)單地按照達(dá)到順序接受治 療，實(shí)際上病人大

6、致被分為三類：（1）病危型，病情致命，必須馬上治療：（2） 嚴(yán)重型，拖延治療會(huì)使病情加重；（3）平穩(wěn)型，治療不及時(shí)并沒有嚴(yán)重的后果。 病人們按照以上優(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,因此可求得心=0. 2, A2=0. 6, A3=l. 2o通過(guò)對(duì) 比s=l和尸2

7、時(shí)的情況，說(shuō)明是否有必要在急診室增加一個(gè)醫(yī)生。用Excel計(jì)算的數(shù)據(jù)如下表所示。（為了對(duì)比，同時(shí)給出在非搶占性模型下 的各項(xiàng)數(shù)據(jù)。）Wl-l/pW2-l/pW3-l/pPreemptive PrioritiesNonpreemptive Prioritiess=1s=2s=1s=20. 024 hour0. 154 hour1. 033 hour0. 238 hour0.029hour0. 325 hour0.033hour0. 889 hour0.048hour下面來(lái)計(jì)算s=2時(shí)，強(qiáng)占性模型下的每個(gè)優(yōu)先級(jí)病人的平均等待時(shí)間。由于第一優(yōu)先級(jí)的病人的等待時(shí)間并不受其他優(yōu)先級(jí)的影響，所以對(duì)任意的

8、足、義3，必取值相同，當(dāng)足咆二。時(shí)，"1與一般M/M/s模型中當(dāng)s=2, p =3, A =2i=0. 2時(shí)W的取值相同。即 w=W=W+1 = + 1=枷）= ° 00037 小時(shí)，1 q /2 /z s!（l-p）-2 /z其中P=, s/zpi（初/汗 i。/ e n! s! l-/（s/z）'故W 4 = 0.00037 小時(shí)。下面考慮前兩個(gè)優(yōu)先級(jí)。同理，這兩個(gè)優(yōu)先級(jí)的病人也不受第三優(yōu)先級(jí)的影 響。令時(shí)2為隨機(jī)到達(dá)的前兩個(gè)優(yōu)先級(jí)的病人的平均等待時(shí)間，則該病人是第一 優(yōu)先級(jí)的扁率為4/（4+人） = 1/4,是第二優(yōu)先級(jí)的概率為人/（4+人） = 3/4。13

9、故 Wi-2 = - + -W>,44另一方面，Wi.2與一般M/M/s模型中當(dāng)s=2,p =3, A =Ai+A2=0. 8時(shí)W的取值相同。即 W1-2 = W =0. 33937 小時(shí),41從而 W= 0.33937-(0.3337) =034126 小時(shí),34故 W,-4 = 0.00793 小時(shí)。同理，令Wi為隨機(jī)到達(dá)的病人的平均等待時(shí)間，有訶一3 = 0.八可 + 0.3Vy + 0.6%,訶-3與一般M/M/s模型中當(dāng)s=2, M =3, A =A1+A2+A3=2時(shí)W的取值相同。即 W1-3=W=O. 375 小時(shí)，從而W = 0.375 一 0.1(0.3337) 一 0

10、3(0.34126) = 0.39875 小時(shí), 0.6故-1 = 0.06542 小時(shí)。所以，完整的數(shù)據(jù)對(duì)比表如下：Preemptive PrioritiesNonpreemptive PrioritiesS=1s=2S=1s=2Wl-1/p0. 024 hour0. 00037 hour0. 238 hour0. 029 hourW2-1/|J0. 154 hour0. 00793 hour0. 325 hour0. 033 hourW3-1/JJ1. 033 hour0. 06542 hour0. 889 hour0. 048 hour從中可以看出，強(qiáng)占性模型下，若只有一名醫(yī)生，在接受治療前