【文档说明】第十二章排队论(运筹学-上海电力学院,施泉生.pptx，共(61)页，179.016 KB，由精品优选上传

转载请保留链接：https://www.ichengzhen.cn/view-285426.html

以下为本文档部分文字说明：

第十二章排队论1引言2排队论是研究排队系统（又称随机服务系统）的数学理论和方法，是运筹学的一个重要分支。3有形排队现象：进餐馆就餐，到图书馆借书，车站等车，去医院看病，售票处售票，到工具房领物品等现象。4无形排队现象：如几个旅客同时打电话订车票

；如果有一人正在通话，其他人只得在各自的电话机前等待，他们分散在不同的地方，形成一个无形的队列在等待通电话。排队的不一定是人，也可以是物。如生产线上的原材料，半成品等待加工；因故障而停止运行的机器设备在等待修理；码头上的

船只等待装货或卸货；要下降的飞机因跑道不空而在空中盘旋等。当然，进行服务的也不一定是人，可以是跑道，自动售货机，公共汽车等。顾客——要求服务的对象。服务员——提供服务的服务者（也称服务机构）。顾客、服务员的含义是广义的。排队系统类型：服务台

顾客到达服务完成后离开单服务台排队系统排队系统类型：服务台2顾客到达服务完成后离开S个服务台，一个队列的排队系统服务台s服务台1排队系统类型：服务台2顾客到达服务完成后离开S个服务台，S个队列的排队系统服务台s服务台1服务完成后离开服务完成后离开排队系统类型：服务台1顾客到达离开多服务台串联

排队系统服务台s排队系统类型：服务机构聚散随机聚散服务系统（输入）（输出）随机性——顾客到达情况与顾客接受服务的时间是随机的。一般来说，排队论所研究的排队系统中，顾客相继到达时间间隔和服务时间这两个量中至少有一个是随机的，因此，排队论又称随机服

务理论。排队系统的描述实际中的排队系统各不相同，但概括起来都由三个基本部分组成：输入过程，排队及排队规则和服务机构。❖输入过程➢顾客总体（顾客源）数：可能是有限，也可能是无限。河流上游流入水库的水量可认为是无限的；车间内停机待修的机器显然是有限的。➢到达方式：是单个到达还是成

批到达。库存问题中，若把进来的货看成顾客，则为成批到达的例子。➢顾客（单个或成批）相继到达的时间间隔分布：这是刻划输入过程的最重要内容。令T0=0，Tn表示第n顾客到达的时刻，则有T0T1T2…..Tn……记Xn=Tn–Tn-1n=1,2,…,则Xn是第n顾客与第n-1顾客到

达的时间间隔。一般假定{Xn}是独立同分布，并记分布函数为A(t)。{Xn}的分布A(t)常见的有：o定常分布（D）：顾客相继到达的时间间隔为确定的。如产品通过传送带进入包装箱就是定常分布。o最简流（或称Poisson)（M）：顾客相继到达的时间

间隔{Xn}为独立的，同为负指数分布，其密度函数为：a(t)=e-tt00t<0❖排队及排队规则➢排队o有限排队——排队系统中顾客数是有限的。o无限排队——顾客数是无限，队列可以排到无限长（等待制排队系统）。有限排队还可以分成：▪损失制排队系统：排队空间为零的

系统，即不允许排队。（顾客到达时，服务台占满，顾客自动离开，不再回来）（电话系统）▪混合制排队系统：是等待制与损失制结合，即允许排队，但不允许队列无限长。混合制排队系统：•队长有限。即系统等待空间是有限的。例：最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数（又称为队

长）小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床位是有限的。混合制排队系统：•等待时间有限。即顾客在系统中等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离开，不再回来。如易损失的电子元件的库存问题，超过一定

存储时间的元器件被自动认为失效。混合制排队系统：•逗留时间（等待时间与服务时间之和）有限。例：用高射炮射击飞机，当敌机飞越射击有效区域的时间为t时，若这个时间内未被击落，也就不可能再被击落了。损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台个数，

则当k=s时，混合制即为损失制；当k=时，即成为等待制。➢排队规则当顾客到达时，若所有服务台都被占有且又允许排队，则该顾客将进入队列等待。服务台对顾客进行服务所遵循的规则通常有：o先来先服务（FCFS）o

后来先服务（LCFS）。在许多库存系统中就会出现这种情况，如钢板存入仓库后，需要时总是从最上面取出；又如在情报系统中，后来到达的信息往往更重要，首先要加以分析和利用。o具有优先权的服务（PS）。服务台根据顾客的优先权的不同

进行服务。如病危的病人应优先治疗；重要的信息应优先处理；出价高的顾客应优先考虑。❖服务机制包括：服务员的数量及其连接方式（串联还是并联）；顾客是单个还是成批接受服务；服务时间的分布。记某服务台的服务时间为V，其分布函数为B(t),密度函数为b(t),则常见的分布有

：➢定长分布（D）：每个顾客接受的服务时间是一个确定的常数。➢负指数分布（M）：每个顾客接受的服务时间相互独立，具有相同的负指数分布：b(t)=e-tt00t<0其中>0为一常数。➢K阶爱尔朗分布（En）：b(t)=k(kt)k-1(K-1)

!=e-kt当k=1时即为负指数分布；k30,近似于正态分布。当k→时，方差→0即为完全非随机的。排队系统的符号表示：“Kendall”记号：X/Y/Z/W其中：X表示顾客相继到达的时间间隔分布

；Y表示服务时间的分布；Z表示服务台个数；W表示系统的容量，即可容纳的最多顾客数。例12-1M/M/1/M表示顾客相继到达的时间间隔服从负指数分布；M表示服务时间为负指数分布；单个服务台；系统容量为无限（等待制

）的排队模型。例12-2M/M/S/K表示顾客到达的时间间隔服从负指数分布；服务时间为负指数分布；S个服务台；系统容量为K的排队模型。当K=S时为损失制排队模型；当K=时为等待制排队模型。排队系统的主要数量指标：➢系统状态：也称为队长，指排队系统中的顾客数（排队等待的顾客数与正在接受服务的

顾客数之和）。➢排队长：系统中正在排队等待服务的顾客数。记N(t)：时刻t(t0)的系统状态；pn(t)：时刻t系统处于状态n的概率；S：排队系统中并行的服务台数；n：当系统处于状态n时，新来的顾客的平均到达率（单位时间内到达的平均顾客数）；n：当系统处于状态n时，整个系统的平均服务率（单

位时间内可以服务完的平均顾客数）；当n为常数时记为；当每个服务台的平均服务率为常数时，记每个服务台的服务率为，则当ns时，有n=s。因此，顾客相继到达的平均时间间隔为1/，平均服务时间为1/，令=/s，则为系统的服务强度。pn(

t)称为系统在时刻t的瞬间分布，一般不容易求得，同时，由于排队系统运行一段时间后，其状态和分布都呈现出与初始状态或分布无关的性质，称具有这种性质的状态或分布为平稳状态或平稳分布，排队论一般更注意研究系统在平稳状态

下的性质。排队系统在平稳状态时一些基本指标有：Pn:系统中恰有n个顾客的概率；L：系统中顾客数的平均值，又称为平均队长；Lq：系统中正在排队的顾客数的平均值，又称为平均排队长；T：顾客在系统中的逗留时间；W=E(T)：顾客在系统中的平均逗留时间；Tq：顾客在系统中

的排队等待时间；Wq=E(Tq)：顾客在系统中的平均排队等待时间。排队论研究的基本问题：➢通过研究主要数量指标在瞬时或平稳状态下的概率分布及数字特征，了解系统运行的基本特征。➢统计推断问题：建立适当的排队模型是排队论研究的第一步，建立模型过程中，系统是否达到平稳状态的检验；

顾客相继到达时间间隔相互独立性的检验，服务时间的分布及有关参数的确定等。排队研究的基本问题：➢系统优化问题：又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优的或最合理的状态。包括：最优设计问题和最优运营问题。M/M/S等待制排队模

型➢单服务台问题，又表示为M/M/1/：顾客相继到达时间服从参数为的负指数分布；服务台数为1；服务时间服从参数为的负指数分布；系统的空间为无限，允许永远排队。✓队长的分布记Pn=p{N=n},n=0,1,2….为系统达到平衡

状态后队长的概率分布，则n=；n=，=/<1，有Pn=(1-)nn=0,1,2….✓几个数量指标o平均队长：L=nPn=n(1-)n=/(1-)=/(-)o平均排队长：Lq=(n-1

)Pn=2/(1-)=2/(-)✓几个数量指标o平均逗留时间：W=E(T)=1/(-)o平均等待时间：Wq=/(-)它们之间有关系：L=WLq=WqLittle公式。例12-3：考虑一个铁路列

车编组站。设待编列车到达时间间隔服从负指数分布，平均每小时到达2列；服务台是编组站，编组时间服从负指数分布，平均每20分钟可编一组。已知编组站上共有2股道，当均被占用时，不能接车，再来的列车只能停在站外或前方站。求在平衡状态下系统中列车的平均数；每

一列车的平均逗留时间；等待编组的列车平均数。如果列车因站中2股道均被占用而停在站外或前方站时，每列车每小时费用为a元，求每天由于列车在站外等待而造成的损失。解：本例可看成一个M/M/1/排队问题，其中=2，=3，=/=2/3<1▪

系统中列车的平均数L=/(1-)=(2/3)/(1-2/3)=2（列）▪列车在系统中的平均停留时间W=L/=2/2=1（小时）▪系统中等待编组的列车平均数Lq=L-=2-2/3=4/3（列）▪列

车在系统中的平均等待编组时间Wq=Lq/=(4/3)/(1/2)=2/3（小时）▪记列车平均延误（由于站内2股道均被占用而不能进站）时间为W0则W0=WP{N>2}=W{1-P0-P1-P2}=W{1-(l-)-(l-)1-(l-)2}=1*3=3=(2/3)3=0.296（

小时）故每天列车由于等待而支出的平均费用E=24W0a=24*2*0.296*a=14.2a元例12-4：某修理店只有一位修理工，来修理的顾客到达过程为Poisson流，平均每小时4人；修理时间服从负指数分布，平均需要6分钟。试求：修

理店空闲的概率；店内恰有3位顾客的概率；店内至少有一位顾客的概率；在店内平均顾客数；每位在店内平均逗留时间；等待服务的平均顾客数；每位顾客平均等待服务时间；顾客在店内等待时间超过10分钟的概率。解：本例可看成一个M/M/1/排队

问题，其中=4，=1/0.1=10(人/小时），=/=2/5<1▪修理店内空闲的概率P0=1-=(1-2/5)=0.6▪店内恰有3个顾客的概率P3=3(1-)=(2/5)3(1-2/5)=0.038▪店内至少有1位顾

客的概率P{N1}=1-P0=1-(1-)==2/5=0.4▪在店内平均顾客数L=/(1-)=(2/5)/(1-2/5)=0.67(人）▪每位顾客在店内平均逗留时间W=L/=0.67/4=10

分钟▪等待服务的平均顾客数Lq=L-=0.67-2/5=0.27(人)▪每个顾客平均等待服务时间Wq=Lq/=0.27/4=0.0675小时=4分钟▪顾客在店内等待时间超过10分钟的概率P{T>10}=e-10(1/6-1/15)=e-1=0.3677P{T>t}=e-(

-)tt=10分钟,=10人/小时=10/60=1/6=4人/小时=4/60=1/15M/M/S等待制排队模型➢多服务台问题，又表示为M/M/S/：顾客相继到达时间服从参数为的负指数分布；服务台数为S；每个服务台的服务时间相互独立，且服从参数为的负指数分布。

当顾客到达时，若有空闲服务台马上被进行服务，否则便排成一队列等待，等待空间为无限。✓队长的分布记Pn=p{N=n},n=0,1,2….为系统达到平衡状态后队长N的概率分布，对多服务台有n=；n=0,1,2….n=nn=0,1,2….sn=sn=s,s+1,s+2….s=/s=

/s,当s<1时，有Cn=(/)nn!(/)ss!(/s)n-s=(/)ns!sn-sn=1,2,…..snspn=(p)nn!n=1,2,…..sns!sn-snsp0p0其中：p0=[0s-1pn/n!+s/s!(1-s

)]-1当ns时，顾客必须等待，记C(s,)=spn=s/s!(1-s)p0称为Erlang等待公式，它给出了顾客到达系统时，需要等待的概率。平均排队长：Lq=s(n-s)pn=p0ss/s!(1-s)2或Lq=C(s,)s/(1

-s)记系统中正在接受服务的顾客平均数s,显然s也是正在忙的服务台平均数。S=0s-1npn+s*spn=平均队长：L=平均排队长+正在接受服务的顾客的平均数=Lq+对多服务台，Little公式依然成立：W=L/Wq=Lq/=W-(1/)例12-5：考虑一

个医院急诊室的管理问题，根据资料统计，急诊病人相继到达的时间间隔服从负指数分布，平均每半小时来一个；医生处理一个病人的时间也服从负指数分布，平均需要20分钟。急诊室已有一个医生，管理人员考虑是否需要再

增加一个医生。解：本问题可看成M/M/S/排队问题，其中（时间为小时）=2，=3，=2/3，s=1,2,…..计算结果如下表：S=1S=2空闲概率p00.3330.5有一个病人概率p10.2220.333有二个病人概率p20.1480.111平均病人数L20.75平均等待病人数Lq1.3

330.083病人平均逗留时间W(小时)10.375病人平均等待时间Wq(小时)0.6670.042病人需要等待概率p{Tq>0}0.6670.167等待时间超过半小时的概率p{Tq>0.5}0.4040.022等待时间超过一小时的概率p{Tq>1}0.2450.003习题12.212.3