运筹学-排队论课件

第十二章

排队论(QueuingTheory)排队论的基本概念到达间隔的分布和服务时间的分布排队系统的分析排队论(QueuingTheory)，又称随机服务系统理论(RandomServiceSystemTheory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。排队论是1909年由丹麦工程师爱尔朗(A.K．Erlang)在研究电话系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。第一节基本概念一、排队系统的一般表示例1、各个顾客由顾客源出发，到达服务机构前排队等候服务，服务完了后就离开。排队结构指队列的数目和排列方式排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。顾客源排队结构排队规则服务规则服务机构离去顾客到来排队系统排队是我们在日常生活和生产中经常遇到的现象:上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。排队的不一定是人，也可以是物：通讯卫星与地面若干待传递的信息；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。一般排队的过程

顾客到达队列（排队规则）服务台（接受服务）顾客离去二、排队系统的组成和特征输入即指顾客到达排队系统，可能有以下不同情况。1、输入过程

（1）顾客源的组成有限的无限的（2）顾客到来的方式

一个一个的成批的（3）顾客相继到达的间隔时间确定型的随机型的（4）顾客的到来相互独立的关联的（5）输入过程平稳的，或称对时间是齐次的非平稳的2、排队规则顾客在排队系统中按怎样的规则、次序接受服务的。（1）顾客到达时，所有服务台被占用随即离去的称为即时制（损失制）排队等候称为等待制先到先服务后到先服务随机服务有优先权（2）从队列占用空间有限的无限的（3）从队列的数量单列多列3、服务机构（1）服务员数量没有一个或多个（2）多服务台时单队—单服务台单队—多服务台（并列）多队—多服务台（并列）多服务台（串列）（3）服务方式对单个顾客进行对成批顾客进行（4）服务时间确定型随机型（5）服务时间的分布我们总假定是平稳的，即分布的期望值、方差等参数都不受时间的影响12312多服务台混合一个排队系统的特征可以用六个参数表示，形式为：

[X/Y/Z]/[A/B/C]其中X––顾客到达的概率分布，可取M、D、Ek等；Y––服务时间的概率分布，可取M、D、Ek等；Z––服务台个数，取正整数；A––排队系统的最大容量，可取正整数或；B––顾客源的最大容量，可取正整数或；C––排队规则，可取FCFS、LCFS等。三、排队模型的分类(条件参数)表示相继到达间隔时间和服务时间的各种分布的符号:M—负指数分布D—确定型Ek—k阶爱尔朗分布GI—一般相互独立的时间间隔的分布G—一般服务时间的分布例如：某排队问题为

M/M/s/∞/∞/FCFS

则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s＞1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。可简记为： M/M/s

四、排队系统的参数(分析结果)1、队长（Ls）指在系统中的顾客数,期望值2、排队长（Lq）指系统中排队等候服务的顾客数3、逗留时间（Ws）指一个顾客在系统中的停留时间4、等待时间（Wq）指一个顾客在系统中排队等待的时间Ls=Lq+正被服务的顾客数Ws=Wq+服务时间这四项主要性能指标(又称主要工作指标)的值越小，说明系统排队越少，等待时间越少，因而系统性能越好。显然，它们是顾客与服务系统的管理者都很关注的。5、忙期指从顾客到达空闲服务机构起到服务机构再次空闲止这段时间长度，即服务机构连续繁忙的时间长度。6、系统的状态n：指系统中的顾客数。8、稳定状态：t→时，t=0时的系统不稳定状态将消失，系统的状态概率分布不再随时间变化，即

limPn(t)→Pn。7、系统状态的概率Pn(t)：指时刻t、系统状态为n的概率。一般为关于t的微分方程、关于n的差分方程。9、其他常用数量指标s ——系统中并联服务台的数目； ——平均到达率；1/ ——平均到达间隔。 ——平均服务率；1/ ——平均服务时间。 ——服务强度，每个服务台单位时间内的平均服务时间；一般有s

；当s=1时：对于损失制和混合制的排队系统，顾客在到达服务系统时，若系统容量已满，则自行消失。这就是说，到达的顾客不一定全部进入系统，为此引入：e——有效平均到达率,即每单位时间实际进入系统的平均顾客数（期望值），不同于.

对于等待制的排队系统，

e

＝一、经验分布例2某服务机构单服务台，先到先服务，对41顾客记录到达时刻和服务时间s（单位：分钟）如下表，表中第1号顾客到达时刻为0。全部服务时间为127（分钟）。第二节到达间隔的分布和服务时间的分布(1)i(2)τi(3)si(4)ti(5)wi(1)i(2)τi(3)si(4)ti(5)wi(1)i(2)τi(3)si(4)ti(5)wi10520512271093612022743619435103827036156722346114552041191282631051247423(1)i(2)

τi(3)si(4)ti(5)wi(1)i(2)

τi(3)si(4)ti(5)wi(1)i(2)

τi(3)si(4)ti(5)wi134913523866223311744714522932488546341212671561110259213735127123166223026953653612961217651502710124237130337187032028105210381335271972481291061313913524102080310301092504013943821812223111412041142119228333232116810各栏意义：（1）i，顾客编号；（2）τi：顾客i到达的时刻；（3）si：服务时间；以上三栏是原始数据；（4）ti

：到达间隔；（5）wi：排队等待时间；这俩栏是可以通过计算得到的到达间隔分布表服务时间分布表到达间隔（分钟）次数12345678910以上11122368106合计40服务时间（分钟）次数123456789以上11214571010合计41平均间隔时间=142/40=3.55(分钟/人)平均到达率=41/142=0.28(人/分钟)平均服务率=41/127=0.32(人/分钟)平均服务时间=127/41=3.12(分钟/人)输入过程是描述各种类型的顾客以怎样的规律到达系统，一般用相继两顾客到达时间间隔来描述系统输入特征。主要输入过程有：定长输入，泊松输入…1．定长输入是指顾客有规则地等距到达，每隔时间到达一个顾客。这时相继顾客到达间隔的分布函数F(t)为定长输入例如，生产自动线上产品从传送带上进入包装箱就是这种情况．二、泊松(Poisson)输入泊松(Poisson)输入，即泊松流，又称最简单流。设随机变量X服从Poisson分布，则概率密度如果一个随机变量，概率分布与时间t有关，则称这个随机变量为一随机过程，排队系统中顾客到达的个数就是一个随机过程。

(1)Poisson流的定义满足以下四个条件的输入流称为Poisson流(Poisson过程)①平稳性：增量与时间起点无关在时间区间[t,t+t)内到达k个顾客的概率与t无关，只与t有关。记为pk(t）。②无后效性不相交的时间区间内到达的顾客数互相独立。③稀有性：瞬时内只可能有1个顾客到达设在[t,t+t）内到达多于一个顾客的概率为q(t），则q(t)=o(t).即④有限性任意有限个区间内到达有限个顾客的概率等于1。即区间情况[0,t)[t,t+Δt)[0,t+Δt)个数概率个数概率个数概率(A)nPn(t)01-λΔt+o(Δt)nPn(t)(1-λΔt+o(Δt))(B)n-1Pn-1(t)1λΔt+o(Δt)nPn-1(t)(λΔt+o(Δt))(C)n-2Pn-2(t)2o(Δt)no(Δt)n-3Pn-3(t)3n0P0(t)nn简记Pn(0,t)=Pn(t)。表示[0,t)时间内到达n个顾客的概率，即输入。对于区间[0,t+Δt)，可分成两个互不重叠的区间[0,t)和[t,t+Δt)。设在区间[0,t+Δt)上，到达总数为n，会出现A,B,C三种情况：区间[0,t+Δt)内到达n个顾客应是表中三种互不相容的情况之一，所以概率Pn(t+Δt)应是三个概率之和，即：

Pn（t+Δt）=Pn（t）（1-λΔt

）+Pn-1（t）λΔt+o（Δt）[Pn（t+Δt）-Pn（t）]/Δt=－λPn（t）+λPn-1（t）+[o（Δt）]/Δt

令Δt0dPn（t）/dt=-λPn（t）+λPn-1（t）Pn（0）=0（n1）dP0（t）/dt=-λP0（t）P0（0）=1（n=0）求出

整理后得：由此可见，泊松输入，即在t时段内到达n个顾客的概率服从参数为λ的泊松分布。注意：我们要把泊松输入同前面提到的系统状态Pn区分开参数的实际意义

设N(t)表示在[0，t）内到达的顾客数的期望值由此得到即的实际意义为单位时间内到达的顾客数的期望值，或称平均到达速率。泊松分布由概率论可知，如果随机变量X服从参数为λ泊松分布，则其分布函数为（注：不是很重要）

密度函数为

X的期望值为

X的方差为由概率论可知，如果随机变量T服从负指数分布，则其分布函数为

密度函数为

T的期望值为

T的方差为三、负指数分布（指数分布）Poisson流与负指数分布之间的关系定理在排队系统中，如果到达的顾客数服从以为参数的Poisson分布，则顾客相继到达的时间间隔服从以为参数的负指数分布。证明：设Poisson流中顾客相继到达的时间间隔为随机变量T，并且在时刻0有一个顾客到达，则下一个顾客将在时刻T到达。T的分布函数为其中p[T>t]表示在[0，t）内没有顾客到达的概率，因此

所以，T的分布函数为

T的密度函数为

因此，顾客相继到达的时间间隔服从以为参数的负指数分布。可以看出，“到达的顾客数是一个以为参数的Poisson流”与“顾客相继到达的时间间隔服从以为参数的负指数分布”两个事实是等价的。顾客相继到达的时间间隔服从以为参数的负指数分布服务时间服从负指数分布，概率密度为参数同样具有两层含义：单位时间内服务的顾客人数的期望值，或称平均服务率。

由于的均值为1/

，即平均对每位顾客的服务时间为1/

.服务时间服从以为参数的负指数分布负指数分布具有无记忆性定理设对顾客的服务时间X服从参数为的负指数分布。在对某一个顾客的服务已经进行了一定时间的条件下，这个顾客的剩余的服务时间仍服从以为参数的负指数分布。证明：设服务已经进行的时间为，则剩余时间不少于t的条件概率为

由此看出，服务剩余时间的分布独立与已经服务过的时间，并且与原来的服务时间的分布相同。设v1，v2，…，vk是k个互相独立的，具有相同参数的负指数分布随机变量，则随机变量

服从k阶Erlang分布，S的密度函数为四、k阶爱尔朗(Erlang)分布期望值为 方差为注意：①当k=1时，爱尔朗分布就是负指数分布，是完全随机的；②当k>=30时，近似于正态分布；③一般k阶爱尔朗分布可看成是完全随机与完全确定的中间型，有更广泛的适应性。一、M/M/1模型1、假设（1）顾客到达的间隔时间满足参数为λ的负指数分布（2）服务时间满足参数为µ的负指数分布（λ<µ）（3）服务机构是单服务台（4）顾客源是无限的，顾客到来相互独立（5）单队排列，且对队长没有限制第三节单服务台负指数分布排队系统的分析求： （1）系统状态概率Pn； （2）系统运行指标Ls，Lq，Ws，Wq。2、Pn的计算情况在时刻t顾客数在区间（t，t+Δt）到达离去在时刻t+Δt顾客数ABCDnn+1n-1nnnnn注：表示发生（1个），表示没有发生。整理后得：将Pn(t)移到左边，两边同除以t，得到令t0时，得到关于Pn(t)的微分方程：当n=0，则只有表中A，B两种情况，即同理，求得：Pn(t)的稳态解Pn如果能够求解由无限个方程组成的差分微分方程组，就可以得到Pn(t)的瞬态解，即系统中有n个顾客的概率随时间变化的解析表达式，但这是十分困难的。如果假定当时间足够长，系统有n个顾客的概率Pn(t)会趋于某个稳定值，即当t时系统趋于概率稳态，这个稳态解是可以求出来的。设当t时，Pn(t)趋于一个常数，这时Pn(t)与t无关，可记为Pn，则Pn关于t的导数为0。这时(1)式和(2)式可得状态转移图以系统中的顾客数0，1，2，…，n-1，n，n+1，…作为系统的状态，(3)和(4)表示系统位于某一状态的概率仅与其相邻状态的概率以及从相邻状态转移到该状态的概率有关。系统状态（n）随时间变化的过程是生灭过程的一个特殊情况，(3)和(4)关于Pn的差分方程，可以用状态转移图来表示各状态间的转移关系，并能求解。0n123λλλλλμμμμμ由(3)和(4)可以递推求解P1，P2，…，Pn，…。由(3)得到

(5)由(4)得到

(6)将(5)代入(6)

用递推方法可以得到

(7)由得到令称为服务强度，则当时，级数收敛，这时有

(8)代入(7)，得到

(9)(8)和(9)可以统一表示为

(10)当1时，级数发散，不存在稳态解(队列将会排至无限远），因此，排队系统处于概率稳态的条件是注：是系统的服务强度，即是忙期，(1-)=P0就是系统空闲时间。例1 高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为100辆／小时，收费时间服从负指数分布，平均收费时间为15秒／辆。求1、收费处空闲的概率；2、收费处忙的概率；3、系统中分别有1，2，3辆车的概率。解：根据题意,=100辆/小时，=15秒=240（小时/辆）,即＝240（辆/小时）。因此系统空闲的概率为：系统忙的概率为：系统中有1辆车的概率为：系统中有2辆车的概率为：系统中有3辆车的概率为：

3、M/M/1参数计算（1）系统中平均顾客数队长（Ls）（2）队列中等待的平均顾客数（Lq）即 Lq=Ls（3）顾客逗留时间（Ws）（4）队列中顾客等待时间（Wq）将以上结果总结如下：对于M/M/1///FCFS系统，系统中由k个顾客的概率为：

系统中的平均顾客数为：队列的平均长度为：顾客在系统中的平均逗留时间为：顾客在队列中的平均等待时间为： Little公式一般化

Little公式的条件:排队系统能够进入统计平衡状态；服务台的忙期与闲期交替出现；系统中任一顾客不会永远等待，系统也不会永远无顾客到达。例3100个工作小时内每小时来就诊的病人数n出现次数如下100个完成手术的病例所用时间v（小时）出现的次数如下到达的病人数n出现次数fn0123456以上102829161061合计1002517965为病人完成手术时间v（小时）出现次数fv0.0-0.20.2-0.40.4-0.60.6-0.80.8-1.01.0-1.21.2以上380合计100假定系统最大容量为N，单服务台情形，排队等待的顾客最多为N-1，下面只考虑稳态情形：二、M/M/1/N/模型顾客到达因队列满而离去进入队列接受服务服务完毕后离去0N-112N-2λλλλμμμμN0N-112N-2λλλλμμμμN根据上式我们可以推导出系统的各项指标：有效到达率：例4单人理发馆有六个椅子接待客人。当6个椅子都坐满时，后来的顾客不进店就离开。顾客平均到达率为3人/小时，理发需时平均15分钟。则：

N=7为系统中最大的顾客数，λ=3人/小时，μ=4人/小时（1）求某顾客一到达就能理发的概率。（2）求需要等待的顾客数的期望值。（3）求有效到达率。（4）求一顾客在理发馆内逗留的时间。（5）在可能到达的顾客中有百分之几不等待就离开。机器故障问题：设共有m台机器，机器故障停机表示到达，待修机器形成队列，修理工是服务员。顾客总体虽然只有m个，但每个顾客服务后仍回到总体，仍然可以到来。三、顾客源有限的情形(M/M/1//m)λ的含义发生改变表示全体顾客的平均到达率表示每个顾客的平均到达率服务台需要服务服务完毕队列系统外的平均顾客数说明：进入率与状态有关若m=5,n=3;如下图所示：系统中已经有两人丁和戊进入的为甲、乙或丙，所以为：λ

e=3λ由此列出平衡方程：状态概率0m-112m-2mλ(m-1)λ2λλμμμμmμμ(m-2)λ3λ根据上式我们可以推导出系统的各项指标：在机器故障问题中Ls就是平均故障台数，而例5某车间有5台机器，每台机器的连续运转时间服从负指数分布，平均连续运转时间15分钟，有一个修理工，每次修理时间服从负指数分布，平均每次12分钟。求（1）修理工空闲的概率；（2）五台机器都出故障的概率；（3）出故障的平均台数；（4）等待修理的台数；（5）平均停工时间；（6）平均等待时间；（7）评价这些结果。（7）机器停工时间过长，修理工几乎没有空闲时间，应当提高服务率减少修理时间或增加修理工人。第四节多服务台指数分布排队系统的分析一、M/M/c0N12N-1λλλλμcμ2μcμcc-1λλcμcμc+13μλ(c-1)μλcμcμλλ用递推法解上述差分方程，可求得状态概率。根据上式我们可以推导出系统的各项指标：例6某售票所有三个窗口，顾客到达服从Passion过程，平均到达率每分钟λ=0.9(人),服务(售票)时间服从负指数分布,平均服务率每分钟μ=0.4(人).窗口(1)μ=0.4窗口(2)μ=0.4窗口(3)μ=0.4λ=0.9（1）整个售票所空闲的概率（2）平均队长（3）平均等待时间和逗留时间（4）顾客到达后必须等待（即系统中顾客数已有3人）的概率二、M/M/c型系统和c个M/M/1系统的比较上例中，排队方式不变，但顾客到达后在每个窗口前各排一队，且进入队列后坚持不换，这就形成3个队列，如下图二每个队列平均到达率为λ=λ=λ=0.9/3=0.3（每分钟），这样原来的系统就变成3个M/M/1型的子系统。窗口(1)μ=0.4窗口(2)μ=0.4窗口(3)μ=0.4λ=0.9λ=0.3λ=0.3λ=0.3现按M/M/1型解决这个问题，并与上表比较：模型指标服务台空闲的概率顾客必须等待的概率平均队列平均队长平均逗留时间平均等待时间（1）M/M/3型（2）M/M/1型0.0748P(n3)=0.571.703.954.39(分钟)1.89(分钟)0.25(每个子系统)0.752.25(每个子系统)9.00(整个系统)10(分钟)7.5(分钟)从表中各指标的对比可以看出单队比三队有显著的优越性三、系统容量有限定的M/M/c/N/模型因队列满而离去0N-112N-2λλλλμcμ2μcμNcc-1λλcμcμc+13μλ(c-1)μλcμcμλλ系统的状态概率和运行指标如下:四、顾客源为有限的M/M/c//m模型顾客到达修理速率μ发生故障等待修理的机器修理速率μ修理速率μ正在修理的机器到达速率(m-n)λ修理速率sμ运行的机器数m-n0m-112m-2mλ(m-1)λ2λλμcμ2μcμmcc-1(m-c+1)λcμ稳态概率方程求得其中：例7设有两个修理工人，负责5台机器的正常运行，每台机器平均损坏的概率为每运转一小时1次，两个工人能以相同的平均修复率4（次/小时）修好机器。求（1）等待修理的机器平均数（2）需要修理的机器平均数（3）有效损坏数（4）等待修理时间（5）停工时间(1)Lq=P3+2P4+3P5=0.118(3)λe=1×(5-1.094)=3.906(4)Wq=0.118/3.906=0.03小时

(5)Ws=1.094/3.906=0.28小时第五节一般服务时间M/G/1模型一、M/G/1即：ρ=λE[T]Pollaczek-K