第八章排队论.ppt

运筹帷幄之中，决胜千里之外,运 筹 学,中原工学院机电学院主讲：丁剑飞,Chapter 8 排队论(Queuing Theory),排队论的基本概念单服务台系统多服务台系统,本章主要内容：,引言,在人们生活和生产的实践活动中，经常会遇到拥挤现象，从而产生排队。为了获取较好的经济效益，有必要研究排队现象的规律性。要求得到服务的对象统称为顾客；顾客不仅可以是人，也可以是物。例如等待加工的零件，出故障等待维修的机器等都是顾客。提供服务的对象称为服务机构。顾客和服务机构形成了一个服务系统。例如到医院就医的患者和医院；出现故障的机器和及机器维修班组等，都是服务系统。顾客到达服务机构，当然是希望立即得到服务。然而服务机构已经占满时，例如理发店的座位已满，维修班组已忙于维修机器，再到的顾客只能排队等候或者消失，这样造成的损失称为排队费用。例如机器的停工损失，在仓库的存储,排队论的基本概念,费用，因等候而降低的价值等，都属于排队费用。排队的时间越长，排队费用越大。另一方面，设立的服务机构越多，服务效率越高，需要支付的费用也越大，然而却可以减少排队时间。如何根据顾客的实际情况，设立适当的服务机构，以使得服务费用和排队费用总和最少，是排队论所要讨论和解决的问题。8.1 排队论的基本概念顾客到达服务机构，依照一定的规律等待，然后接受服务，服务完毕后离去。这个过程称为服务过程。,引言,如果顾客到达和接受服务的时间都具有随机性，那么这个服务系统就称为随机服务系统，又称为排队系统；服务过程称为排队过程。一个排队过程，大体分为三个基本部分：输入过程、排列规则、服务机构。,输入过程,排队规则,服务机构,排队论的基本概念,一、输入过程对于排队系统，顾客是输入。输入过程是指顾客按怎样的规律到达服务机构。顾客来源的总体称为顾客源。例如待修机器和维修班组所形成的排队系统，工厂的全部机器是顾客源；对于到理发店来理发的顾客来说，全体居民是顾客源，等等。顾客源可以是无限集合，也可以是有限集合。顾客可能单个到达，也可能是成批到达，或者是接连不断地到达。本章我们主要讨论称为泊松流或者最简单流的到达方式。1.泊松流（记为M）顾客的输入过程如果具备以下三个特点，则称为泊松流。,排队论的基本概念,（1）平稳性 对于任何t0和非负整数k，在区间(a,a+t内有k个顾客到达系统的概率对任何a0都是相等的。也就是说，这个概率只与t和k有关，而与a有关。我们以vk(t)记这个概率，以x(t)记在长为t的时间段内到达的顾客数，则有（2）无后效性 在时间区间(a,a+t内到达k个顾客的概率与时刻a以前系统的状况无关。就是说，事件(x(t)=k)与a以前系统所发生的事件相互独立。（3）普通性 记 为在时间段t内，到达两个和两个以上顾客的概率，即，则有t0时，。,排队论的基本概念,实际上，许多排队系统的输入过程都近似满足这些特征。可以证明，凡是具备上述3个特征的输入过程，x(t)都是服从泊松分布的随机变量。即x(t)的期望值和方差分别为Ex(t)=t，Varx(t)=t。若取t=1，则Ex(1)=。这即是说，表示单位时间内到达系统顾客数的平均值，称为顾客的到达率或输入率。还可以证明，如果顾客的到达数服从泊松分布，那么它一定满足上述的3个特性。,(8.1),排队论的基本概念,2.定长输入（记为D）流水线上定时送往包装机的成品，其输入过程就是定长输入。如果规定的产品到达的间隔时间为c，则相继到达产品间隔时间t的分布函数为3.k阶爱尔朗分布（记为Ek）设t1,t2,tk是k个相互独立的，且具有相同参数的负指数分布随机变量，则随机变量t=t1+t2+tk服从k阶爱尔朗分布，t的密度函数为,(8.2),排队论的基本概念,随机变量t的期望值和方差分别为：例如，如果顾客连续接受串联的k个服务台的服务，各服务台的服务时间相互独立，且均服从参数为的负指数分布，则顾客接受k个服务台总共所需的时间就服从k阶爱尔朗分布。,(8.3),排队论的基本概念,4.一般独立输入（记为GI)如果各相继到达顾客的间隔时间t1,t2,是相互独立的同分布的随机变量，那么称为一般独立输入。二、排队规则所谓排队规则，就是到达服务机构的顾客，若不能立即得到服务，应按怎样的方式等待接受服务。1.等待制顾客到达后，如果服务机构已经占满，当允许顾客等待时，再到的顾客便排队等待。常见的有以下几种排队方式：,排队论的基本概念,（1）先到先服务 这是最普遍的情形。（2）后到先服务 许多存储系统运用这种规则。（3）随机服务 当一名顾客服务完毕离去时，随机地从等待的顾客中选择一名进行服务。等待中的每位顾客被选中的概率是相等的，例如电话订票服务。（4）优先服务 对于不同的顾客规定不同的优先权，具备较高优先权的顾客优先接受服务。2.消失制当服务机构已经全部占满时，再到的顾客不能进入服务系统，顾客自动消失，也就是不允许排队的情形。对于消失制的情形，不存在排队现象。主要考虑的是顾客消失的概率和服务机构的利用率。,排队论的基本概念,3.混合制等待制的排队方式可以认为排队的队伍长度没有限制。当允许排队、但服务机构的空间和排队时间有限时，队伍长度必然有一定的限制，这种情形称为混合制。（1）等待空间有限 若服务机构最多只能容纳k个顾客，当顾客少于k时，再来者可以排队等待，当顾客等于k时，再来的顾客就自动消失。（2）等待时间有限 若顾客从进入系统开始，到开始接受服务为止，这段等候的时间称为等待时间，也就是顾客在排队系统中排队所占的时间。当顾客的等待时间有限时，到时若不能得到服务，那么顾客就会自动消失。（3）逗留时间优先 顾客从进入系统到接受服务完毕离开,排队论的基本概念,这段时间称为逗留时间。也就是说，逗留时间等于等待时间加接受服务的时间。三、服务机构服务机构中可能是单服务台，也可能是多服务台。当有多个服务台时，排队的顾客可以排成一个队，依次到空出的服务台去接受服务；也可以每个服务台前排成一队，且一旦排好后，不能再更换。,排队论的基本概念,本章首先讨论单服务台的情形。由于顾客的情形不同，服务所需要的时间（称为服务时间）T也不同，因此T是个随机变量。最常见的情形是T服从负指数分布，即T的概率密度函数为,(8.4),排队论的基本概念,其中参数0。T的分布函数为对于服从负指数分布的时间T，有一个特性，就是不论过去已经服务多久，如果到现在仍然没有服务完毕，那么剩余的服务时间仍具有原来的概率分布。即对任何t,0,(8.5),(8.6),排队论的基本概念,这个性质称为无后效性或马尔科夫性。可以证明，凡是具有这个性质的随机变量，必须服从负指数分布。对于负指数分布，其期望和方差分别为：这就是说，表示在单位时间中可以为多少个顾客服务完毕，称为服务率。现举一例。设一个顾客到达服务机构后，有c个服务率都为的服务台同时为其服务，只要有一个服务台完成服务过程，那么整个服务就结束。例如c个命中率相同的射手对一个目标进行射击，只要有一名射手射中，那么目标就被消灭。由于,(8.7),排队论的基本概念,这个结果表明参加工作的服务台越多，平均所需要的服务时间越短。四、排队系统的分类D.G.Kendall 在1953年提出一个分类方法，按照上述各部分特征中最主要的，影响最大的三个，即：（1）相继顾客到达间隔时间的分布；（2）服务时间分布；,排队论的基本概念,（3）服务台个数。按照这三个特征分类，并利用一定符号表示，称为Kendall记号。这只对并列的服务台（如果服务台多于一个的话）的情形，他使用的符号形式是X/Y/Z其中，X处填写表示相继到达的间隔时间分布的记号：Y处填写表示服务时间分布的记号；Z处填写并列的服务台数目。表示相继到达间隔时间和服务时间的各种分布符号是：M负指数分布（M是Markov的字头，因为负指数分布具有无记忆性，即Markov性）；,排队论的基本概念,D确定型（Deterministic）Ekk阶爱尔朗（Erlang）分布；GI一般相互独立（General Independent)的时间间隔的分布；G一般(General)服务时间的分布。后来，在1971年一次关于排队论符号标准化会议上，又将Kendall符号扩充变为 X/Y/Z/A/B/C其中前三项意义不变，而A处填写系统容量限制N，B处填写顾客源数目m，C处填写服务规则，例如先到先服务FCFS，后到先服务LCFS等，并约定，如约去后三项，即指X/Y/Z/FCFS的情形。,排队论的基本概念,五、主要的数量指标经常运用以下几个数量指标来评价一个排队系统。1.队伍长度在排队系统中的平均顾客数，称为队伍长度，简称队长，这是顾客和设计人员都关心的问题。队长的大小直接关系到顾客的利益，也关系到服务机构的利用率。2.逗留时间w和等待时间wq的分布这是顾客最关心的指标，但各个顾客关心的角度不同。例如就诊病人对等待时间比较关心，对诊断时间却不希望太快。3.服务台的利用率服务台工作的时间占总时间的比例，可以衡量服务台的劳动强度及服务成本的大小。这是服务部门所关心的。,排队论的基本概念,4.顾客损失率对于消失制和混合制的排队系统，必须考虑因服务能力不足导致顾客消失的比例，因为这直接关系到经济利益。,单服务台系统,本节将讨论输入过程服从泊松分布过程、服务时间服从负指数分布、单服务台的排队系统。现将其分为：标准的M/M/1模型（M/M/1/FCFS）标准的M/M/1是指符合下列条件的排队系统：（1）输入过程顾客源是无限的，顾客单个到来，相互独立，一定的到达时间服从泊松分布，到达过程平稳。（2）排队规则单队，且队长没有限制，先到先服务。（3）服务机构单服务台，各顾客的服务时间相互独立，服从相同的负指数分布。此外，还假定到达间隔时间和服务时间相互独立。,单服务台系统,在分析标准的M/M/1模型时首先要求出系统在任意时刻t的状态为n（系统中有n个顾客）的概率Pn(t)，它决定了系统运行的特征。因为已知到达规律服从参数为的泊松过程，服务时间服从参数为的负指数分布，所以在t,t+t时间区间内分为：（1）有1个顾客到达的概率为t+(t)；没有顾客到达的概率是1-t+(t)。（2）当顾客在接受服务时，1个顾客被服务完了（离去）的概率是t+(t)，没有离去的概率概率是1-t+o(t)。（3）多于1个顾客到达或离去的概率是o(t)，是可以忽略的。,单服务台系统,在时刻t+t，系统中有n个顾客（n0）存在下列四种情况（到达或离去2个以上的没列入）。,单服务台系统,它们的概率分别是（略去o(t)）：情况（A）Pn(t)(1-t)(1-t)情况（B)Pn+1(t)(1-t)t情况（C)Pn-1(t)t(1-t)情况（D）Pn(t)tt)这四种情况是不相容的，所以Pn(t+t)应是这四项之和，即（将关于t的高阶无穷小合成一项）Pn(t+t)=Pn(t)(1-t-t)+Pn+1(t)t+Pn-1(t)t+o(t),令t0，得关于Pn(t)的微分差分方程,单服务台系统,当n=0，则只有上表中A、B两种情况，即P0(t+t)=P0(t)(1-t)+P1(t)(1-t)t同理求得这样系统状态（n）随时间变化的过程是称为生灭过程的一个特殊情况。解式（8.8）和（8.9）是很麻烦的，求得的解（瞬态解）中因为含有修正的贝塞尔函数，也不便于应用，我们只讨,(8.8),(8.9),单服务台系统,论稳态的情况，这时Pn(t)与t无关，可写成Pn，它的导数为0。由式（8.8）和（8.9）可得这是关于Pn的差分方程。它表明了个状态间的转移关系，用下图表示。,(8.10),(8.11),单服务台系统,由上图可见，状态0转移到状态1的转移率为P0，状态1转移到状态0的转移率为P1。对状态0必须满足以下平衡方程：P0=P1同样，对于任何n1的状态，可得到式（8.11）的平衡方程。求解式（8.10）得：P1=(/)P0将它带入式（8.11），令n=1则有P2=(+)(/)P0-P0,P2=(/)2P0同理依次推得 Pn=(/)nP0今设，又由概率的性质知,单服务台系统,将Pn的关系式带入，有得上式的有其实际意义。根据表达式的不同，可以有不同的解释。当=/表达时，它是平均到达率与平均服务率之比。若表示为=(1/)/(1/)，它是为一个顾客服务时间与到达间隔时间之比；称为服务强度，或称话务强度。,(8.12),单服务台系统,式=1-P0刻画了服务机构的繁忙程度；所以又称为服务机构的利用率。以式（8.12）为基础可以计算出系统的运行指标：（1）在系统中平均顾客数（队长期望值）。,单服务台系统,（2）在队列中等待的平均顾客数（队列长期望值）。关于顾客在系统中逗留的时间W（随机变量），在M/M/1情况下，它服从参数为-的负指数分布，即分布函数F()=1-e-(-)，0概率密度f()=(-)e-(-)（3）在系统中顾客逗留时间的期望值,单服务台系统,（4）在队列中顾客等待时间的期望值。现将以上各式归纳如下：,(8.13),单服务台系统,例8.1 某医院手术室根据病人来诊和完成手术时间的记录，任意抽查100个工作小时，每小时来就诊的病人出现次数见左下表。又任意抽查了100个完成手术的病例，所用时间（小时）的出现次数见右下表。,单服务台系统,（1）计算：每小时病人平均达到率=每次手术平均时间=每小时完成手术人数（平均服务率）=1/0.4=2.5人/小时（2）取=2.1，=2.5，可以通过统计检验的方法（如2检验法），认为病人到达服从参数为2.1的泊松分布，手术时间服从参数为2.5的负指数分布。（3）它说明服务机构（手术室）有84%的时间是繁忙的，平均16%的时间空闲。,单服务台系统,（4）依次带入（8.13），计算出各指标：在病房中病人数（期望值）排队等待病人数（期望值）病人在病房中逗留时间（期望值）病人排队等待时间（期望值）不同的服务规则（先到先服务，后到先服务，随即服务）它们的不同点主要反映在等待时间的分布函数的不同，而一些期望值是相同的。上面讨论的各种指标，因为都是期望值，所以这些指标的计算公式对三种服务规则都适用（但对有优先权的规则不适用）。,单服务台系统,系统容量有限制的情况（M/M/1/N/）如果系统的最大容量为N，对于单服务台的情形，排队等待的顾客最多为N-1，在某时刻一顾客到达时，如果系统中已经有N个顾客，那么这个顾客就被拒绝进入系统。当N=1是为即时服务的情形，当N，为容量无限制的情形。若只考虑稳态的情形，可作各状态间概率强度的转换关系图。,单服务台系统,根据上图，列出状态概率的稳态方程：解这个差分方程与解（8.3）（8.4）很类似，所不同的是P0+P1+PN=1仍令=/，因而得,单服务台系统,在对容量没有限制的情形，我们曾设1时，表示损失率的PN（或表示被拒绝排队的顾客平均数PN）将是很大的。根据式（8.9）我们可以导出系统的各种指标（计算过程略）：（1）队长（期望值）（2）队列长（期望值）,单服务台系统,当研究顾客在系统平均逗留时间Ws和在队列中平均等待时间Wq时，虽然公式（8.7）仍可以利用，但要注意平均到达率是在系统有空时的平均到达率。当系统已满，n=N时，则到达率为0，因此需要求出有效到达率e=(1-PN)。可以验证（3）顾客逗留时间（期望值）。（4）顾客等待时间（期望值）Wq=Ws-1/,单服务台系统,现把M/M/1/N/型的指标归纳如下（1）：例8.2 单人理发馆有6张椅子接待人们排队等待理发。当6个椅子都坐满时，后来到的客人不进店就离开。顾客平均到达率为3人/小时，理发平均15分钟/人。则N=7为系统中最大的顾客数，=3人/小时，=4人/小时。（1）求某顾客一到达就能理发的概率,(8.14),单服务台系统,这种情况相当于理发馆内没有顾客，所求概率（2）求需要等待的顾客数的期望值（3）求有效到达率（4）求一顾客在理发馆内逗留的期望时间,单服务台系统,Ws=Ls/=2.11/2.89=0.73(小时)=43.8(分钟)（5）在可能到来的顾客中，不等就离开的概率这就是求系统中有7个顾客的概率这也是理发馆的损失率。现以本例比较对长为无限和有限两种结果如下：,单服务台系统,顾客源为有限的情形（M/M/1/m）现以常见的机器因故障停机待修的问题来说明。设共有m台机器（顾客总体），机器因故障停机表示“到达”，待修的机器形成队列，修理工人是服务机构，这里只讨论单服务台的情形。类似的例子还有m个打字员共用一台打字机，m个会计共用一个计算机终端等等。顾客总体虽然只有m个，但每个顾客到来并经过服务后，仍然回到原来总体，所以仍然可以到来。在机器故障问题中，同一台机器除了故障（到来）并经修好（服务完了）仍可再出现故障（见下图）。模型中的第四项虽然写了，这表示对系统的容量没有限制，但实际上它永远不会超过m，所以和写成（M/M/1/m/m）的意义相同。,单服务台系统,关于平均达到率，在无限源的情形是按照全体顾客来考虑的；在有限源的情形必须按每个顾客来考虑。为了简单起见，设各个顾客的到达率都是相同的（在这里 的含义是每台机器单位运转时间内发生故障的概率或平均次数），这时在系统外的顾客平均数为m-L，对系统的有效到达率e应是,单服务台系统,对于(M/M/1/m)模型的分析可以用前述的方法。在稳态的情况下，考虑状态间的转移率。当由0状态转移到状态1，每台设备由正常状态转移为故障状态，其转移率为P0，现有m台设备无故障状态转移为有一台设备（不论哪一台）发生故障，其转移率为mP0。至于由状态1转移到状态0，其状态转移率为P1。所以在状态0时有平衡方程mP0=P1。其关系可以由下图表示。由图可得到各状态间的转移差分方程。,单服务台系统,解这些差分方程，用递推方法，并注意到,单服务台系统,得求得系统的各项指标为,(8.15),(8.16),单服务台系统,在机器故障问题中Ls就是平均故障台数，而m-Ls表示正常运转的平均台数。m-Ls=(/)(1-P0)例5 某车间有5台机器，每台机器的连续运转时间服从负指数分布，平均连续运转时间15分钟，有一个修理工，每次修理时间服从负指数分布，平均每次12分钟。求：（1）修理工空闲的概率；（2）五台机器都出故障的概率；（3）出故障的平均台数；（4）等待修理的平均台数；（5）平均停工时间；（6）平均等待修理时间；（7）评价这些结果。,单服务台系统,解 m=5，=1/15，=1/12，/=0.8,多服务台负指数分布的排队系统,现在讨论单队、并列的多服务台（服务台数c）的情形，分以下三种情形：（1）标准的M/M/c模型(M/M/c/)（2）系统容量有限制(M/M/c/N/）（3）有限客源(M/M/c/m)标准的M/M/c模型(M/M/c/)标准M/M/c模型各种特征的规定与标准的M/M/1模型的规定相同。另外规定各服务台是相互独立的，且平均服务效率相同，即1=2=1=。于是整个服务台的平均服务效率为c。令=/c，只有当1才不会排成无限长的的队列，称它为这个系统的服务强度，或称机构的平均利用率。,多服务台负指数分布的排队系统,在分析排队系统时，仍从状态间的转移关系开始（如下图）。如状态1转移到状态0，即系统中有一名顾客服务完了（离去）的转移率为P1，状态2转移到状态1，这就是在两个服务台上被服务的1个被服务完离去，因为不限哪一个，这时的状态转移率便是2P2。同理，再考虑状态n转移到状态n-1的情况。当nc时，状态转移率为nPn；当nc时，因为只有c个服务台，最多有c个顾客在服务，n-c个顾客在等待，因此转移率应为cPn。,多服务台负指数分布的排队系统,由上图可得：这里用递推法解上述差分方程，可求得状态概率。,多服务台负指数分布的排队系统,平均队长,多服务台负指数分布的排队系统,平均等待时间和逗留时间例6 某售票处有三个窗口，顾客的到达服从泊松过程，平均达到率=0.9（人），服务时间服从负指数分布，平均服务率每分钟=0.4人。现设顾客到达后排成一队，依次向空闲的窗口购票就形成一个M/M/c型的系统，其中c=3，/=2.25，=/c=2.25/3(1)符合要求的条件，带入公式得：（1）整个售票处空闲概率,多服务台负指数分布的排队系统,（2）平均队长（3）平均等待时间和逗留时间顾客到达后必须等待（即系统中已有3个人即个服务台都没有空闲）的概率,多服务台负指数分布的排队系统,系统容量为有限的情形M/M/c/N/系统容量最大限制为N(Nc)，当系统中顾客数n已达到N（即队列中顾客人数已达N-c）时，再来的顾客即被拒绝，其他条件与标准M/M/c相同。这时系统的状态概率和运行指标如下：,多服务台负指数分布的排队系统,其中=/c，并且不必限制1。其中，当n=c即关于Pc的公式被称为爱尔朗呼唤损失公式。这时的运行指标如下：,多服务台负指数分布的排队系统,顾客源为有限的情形（M/M/c/m）设顾客源为有限数m，且mc，和单服务台情形一样，顾客到达率是按照每个顾客来考虑的，在机器管理问题中，就是m台机器，有c个修理工人，顾客到达就是机器出了故障，而每个顾客的到达率是指每台机器单位运转时间出故障的期望次数。系统中顾客数n就是出故障的机器,多服务台负指数分布的排队系统,台数，当nc时，所有的故障机器都被在修理，有(c-n)个修理工人在空闲；当cnm时，有(n-c)台机器在停机待修理，而修理工人都在繁忙状态。假定这c个工人修理技术相同，修理时间都服从参数为的负指数分布，并假定故障的修复时间和正在生产的机器是否发生故障是相互独立的。其中,多服务台负指数分布的排队系统,多服务台负指数分布的排队系统,