带优先权的排队论模型

1、带优先权的排队论模型在优先权排队模型中，队中的成员被服务的顺序基于他们被赋予的优先级。相比一般的排队模型，很多真实存在的排队系统实际上更符合带优先权的排 队论模型，比如紧急工作的招聘优先于其他一般的工作；VIP客户较其他一般客 户，在服务上享有优先权等等。因此，带优先权的排队论模型有其实际意义。这里介绍两种最基本的优先权排队模型一一非强占性优先权模型和强占性 优先权模型。两个模型除优先权行使方式之外，其他假设均一致。我们首先描述 这两个模型,之后分别给出其结论，最后通过一个案例来阐述其在实际中的应用。1. 模型公共假设：（1）两个模型都存在N个优先级（1级代表最高）（2）服务顺序首先基于优先级

2、，同一优先级内，依据“先到先服务”（3）对任意优先级，顾客到达服从Poisson分布，服务时间服从负指 数分布（4）对任意优先级顾客的服务时间相同（5）不同优先级顾客的平均到达率可以不同非强占性优先权（Nonpreemptive Priorities）是指，即使一个高优先级的顾客 到达，也不能强制让一个正在接受服务的低优先级顾客返回排队。也就是说，一 旦服务员开始对一个顾客服务，这项服务就不能被打断直至服务结束。强占性优先权（Preemptive Priorities）是指，一日.有高优先级的顾客到达， 服务员即中断对低优先级顾客的服务（这名顾客重新回到排队中），并马上开始 为高优先级顾客服务

3、。结束这项服务后，再按照公共假设中的原则选取下一个被 服务的顾客。（这里由于负指数分布的无记忆性，我们不必关注被中断顾客的服 务进度，因为剩余服务时间的分布与从起点开始的服务时间的分布总是相同的。）对这两个模型来说，如果忽略顾客的优先级，它们是完全等同于一般的M/M/s 排队模型的。因此，当计算整个队列中顾客的总人数（L,Lq）时,M/M/s模型的 结论是适用的：实际上，若随机选择一个顾客，其等待时间（W,%）也可以通 过Little公式计算得出。我们改变的只是顾客们等待时间的分布。在优先权排 队模型下，等待时间的的方差更大，高优先级的顾客缩短了等待时间，而低优先 级的顾客增长了等待时间。为了

4、体现优先权对排队模型的影响，我们需要计算每 一个优先级上顾客的平均等待时间（叫，灯1,2,N）和平均队长（4, k=l,2,N）o2, 结论用以表示稳定状态下k优先级的顾客平均等待时间（包括服务时间），则两 个模型的结论可以表示如下。非抢占性模型（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,（这里假设了立4 < S，从而使第k个优先级能够达到

5、稳定状态。） 1=1Little公式对任意优先级仍然适用，所以扇一一第k个优先级在稳定状态 下的平均队长（包括正在接受服务的顾客）可以表示为：= 4珥，for k = 1, 2,. ., N强占性模型（W1）1/u珥=三-, for k = 1, 2,., N注意到这里的结论适用于仅有一个服务台的情况，但实际上对于S > 1的情 况，必可以通过简单的迭代得出，该方法在案例中会做介绍。同样，应用Little 公式,可得第k个优先级在稳定状态下的平均队长（包括正在接受服务的顾客）：3. 案例市医院急诊中心的问题管理咨询顾问注意到市医院的急诊病人并没有简单地按照达到顺序接受治 疗，实际上病人大

6、致被分为三类：（1）病危型，病情致命，必须马上治疗：（2） 严重型，拖延治疗会使病情加重；（3）平稳型，治疗不及时并没有严重的后果。 病人们按照以上优先级进行排队，每个优先级内部再按照到达顺序排队。预测显示，大约有10%的病危型病人，30%的严重型病人，60%的平稳型病人。 因为严重的疾病在紧急处理后还要进行进一步治疗，所以花在急诊室的时间并不 是很长，进而我们可以认为三种类型的病人接受治疗的时间是相同的。由于病危病人和严重型病人的治疗不能耽误，所以这是一个强占性优先权排 队模型。数据显示|J =3, A =2,因此可求得心=0. 2, A2=0. 6, A3=l. 2o通过对 比s=l和尸2

7、时的情况，说明是否有必要在急诊室增加一个医生。用Excel计算的数据如下表所示。（为了对比，同时给出在非抢占性模型下 的各项数据。）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下面来计算s=2时，强占性模型下的每个优先级病人的平均等待时间。由于第一优先级的病人的等待时间并不受其他优先级的影响，所以对任意的

8、足、义3，必取值相同，当足咆二。时，"1与一般M/M/s模型中当s=2, p =3, A =2i=0. 2时W的取值相同。即 w=W=W+1 = + 1=枷）= ° 00037 小时，1 q /2 /z s!（l-p）-2 /z其中P=, s/zpi（初/汗 i。/ e n! s! l-/（s/z）'故W 4 = 0.00037 小时。下面考虑前两个优先级。同理，这两个优先级的病人也不受第三优先级的影 响。令时2为随机到达的前两个优先级的病人的平均等待时间，则该病人是第一 优先级的扁率为4/（4+人） = 1/4,是第二优先级的概率为人/（4+人） = 3/4。13

9、故 Wi-2 = - + -W>,44另一方面，Wi.2与一般M/M/s模型中当s=2,p =3, A =Ai+A2=0. 8时W的取值相同。即 W1-2 = W =0. 33937 小时,41从而 W= 0.33937-(0.3337) =034126 小时,34故 W,-4 = 0.00793 小时。同理，令Wi为随机到达的病人的平均等待时间，有诃一3 = 0.八可 + 0.3Vy + 0.6%,诃-3与一般M/M/s模型中当s=2, M =3, A =A1+A2+A3=2时W的取值相同。即 W1-3=W=O. 375 小时，从而W = 0.375 一 0.1(0.3337) 一 0

10、3(0.34126) = 0.39875 小时, 0.6故-1 = 0.06542 小时。所以，完整的数据对比表如下：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从中可以看出，强占性模型下，若只有一名医生，在接受治疗前