运筹学-排队论课件

1、第十二章排队论(Queuing Theory),排队论的基本概念 到达间隔的分布和服务时间的分布 排队系统的分析,排队论(Queuing Theory)，又称随机服务系统理论(Random Service System Theory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。 排队论是1909年由丹麦工程师爱尔朗(A.KErlang)在研究电话系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。,第一节

2、 基本概念,一、排队系统的一般表示,例1、各个顾客由顾客源出发，到达服务机构前排队等候 服务，服务完了后就离开。,排队结构指队列的数目和排列方式,排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。,排队规则,排队系统,排队是我们在日常生活和生产中经常遇到的现象: 上、下班搭乘公共汽车； 顾客到商店购买物品； 病员到医院看病； 旅客到售票处购买车票； 学生去食堂就餐等就常常出现排队和等待现象。 排队的不一定是人，也可以是物： 通讯卫星与地面若干待传递的信息； 生产线上的原料、半成品等待加工； 因故障停止运转的机器等待工人修理； 码头的船只等待装卸货物； 要降落的飞机因跑道不空

3、而在空中盘旋等等。,一般排队的过程,二、排队系统的组成和特征,输入即指顾客到达排队系统，可能有以下不同情况。,1、输入过程,（1）顾客源的组成,有限的,无限的,（2）顾客到来的方式,一个一个的,成批的,（3）顾客相继到达的间隔时间,确定型的,随机型的,（4）顾客的到来,相互独立的,关联的,（5）输入过程,平稳的，或称对时间是齐次的,非平稳的,2、排队规则,顾客在排队系统中按怎样的规则、次序接受服务的。,（1）顾客到达时，所有服务台被占用,随即离去的 称为即时制（损失制）,排队等候称为等待制,先到先服务,后到先服务,随机服务,有优先权,（2）从队列占用空间,有限的,无限的,（3）从队列的数量,单

4、列,多列,3、服务机构,（1）服务员数量,没有,一个或多个,（2）多服务台时,单队单服务台,单队多服务台（并列）,多队多服务台（并列）,多服务台（串列）,（3）服务方式,对单个顾客进行,对成批顾客进行,（4）服务时间,确定型,随机型,（5）服务时间的分布我们总假定是平稳的，即 分布的期望值、方差等参数都不受时间的影响,多服务台混合,一个排队系统的特征可以用六个参数表示，形式为： X/Y/Z /A/B/C 其中 X 顾客到达的概率分布，可取M、D、Ek等； Y 服务时间的概率分布，可取M、D、Ek等； Z 服务台个数，取正整数； A 排队系统的最大容量，可取正整数或； B 顾客源的最大容量，可取

5、正整数或； C 排队规则，可取FCFS、LCFS等。,三、排队模型的分类(条件参数),表示相继到达间隔时间和服务时间的各种分布的符号:,M负指数分布,D 确定型,Ekk阶爱尔朗分布,GI 一般相互独立的时间间隔的分布,G 一般服务时间的分布,例如：某排队问题为 M / M / s / / /FCFS 则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。 可简记为： M / M / s,四、排队系统的参数(分析结果),1、队长（Ls） 指在系统中的顾客数,期望值,2、排队长（Lq） 指系统中排队

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

7、n(t)：指时刻t、系统状态为n的概率。一般为关于t的微分方程、关于n的差分方程。,9、其他常用数量指标 s 系统中并联服务台的数目； 平均到达率； 1/ 平均到达间隔。 平均服务率； 1/ 平均服务时间。 服务强度， 每个服务台单位时间内的平均服务时间； 一般有 s ；当s=1时： ,对于损失制和混合制的排队系统，顾客在到达服务系统时，若系统容量已满，则自行消失。这就是说，到达的顾客不一定全部进入系统，为此引入： e 有效平均到达率, 即每单位时间实际进入系统的平均顾客数（期望值），不同于. 对于等待制的排队系统， e ,一、经验分布,例2 某服务机构单服务台，先到先服务，对41顾客记录到达

8、时刻和服务时间s（单位：分钟）如下表，表中第1号顾客到达时刻为0。全部服务时间为127（分钟）。,第二节 到达间隔的分布和服务时间的分布,各栏意义： （1）i，顾客编号；（2）i：顾客i到达的时刻；（3）si：服务时间；以上三栏是原始数据；（4） ti ：到达间隔；（5）wi：排队等待时间；这俩栏是可以通过计算得到的,到达间隔分布表,服务时间分布表,平均间隔时间=142/40=3.55(分钟/人),平均到达率=41/142=0.28(人/分钟),平均服务率=41/127=0.32(人/分钟),平均服务时间=127/41=3.12(分钟/人),输入过程是描述各种类型的顾客以怎样的规律到达系统，一

9、般用相继两顾客到达时间间隔来描述系统输入特征。主要输入过程有：定长输入，泊松输入 1定长输入 是指顾客有规则地等距到达，每隔时间到达一个顾客。这时相继顾客到达间隔的分布函数F(t)为,定长输入,例如，生产自动线上产品从传送带上进入包装箱就是这种情况,二、泊松(Poisson)输入,泊松(Poisson)输入，即泊松流，又称最简单流。 设随机变量X服从Poisson分布，则概率密度,如果一个随机变量，概率分布与时间t有关，则称这个随机变量为一随机过程，排队系统中顾客到达的个数就是一个随机过程。 (1) Poisson流的定义 满足以下四个条件的输入流称为Poisson流(Poisson过程),平

10、稳性：增量与时间起点无关 在时间区间t, t+t)内到达k个顾客的概率与t无关，只与t有关。记为pk(t）。 无后效性 不相交的时间区间内到达的顾客数互相独立。 稀有性：瞬时内只可能有1个顾客到达 设在t, t+t）内到达多于一个顾客的概率为q(t），则 q(t)=o(t). 即 有限性 任意有限个区间内到达有限个顾客的概率等于1。即,简记 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个顾客应是

11、表中三种互不相容的情况之一，所以概率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,令t0,求出,整理后得：,由此可见，泊松输入，即在 t 时段内到达n个顾客的概率服从参数为的泊松分布。,注意：我们要把泊松输入同前面提到的系统状态Pn区分开,参数的实际意义 设N(t)表示在0，t）内到达的顾客数的期望值 由此得到 即的实际意义为单位时间内到达的顾客数的期望值，或称平均到达速率。,泊松分布,由概率论可知，如果随机变量X服从参数为泊松分布，则

12、其分布函数为（注：不是很重要） 密度函数为 X的期望值为 X的方差为,由概率论可知，如果随机变量T服从负指数分布，则其分布函数为 密度函数为 T的期望值为 T的方差为,三、负指数分布（指数分布）,Poisson流与负指数分布之间的关系 定理 在排队系统中，如果到达的顾客数服从以为参数的Poisson分布，则顾客相继到达的时间间隔服从以为参数的负指数分布。 证明：设Poisson流中顾客相继到达的时间间隔为随机变量T，并且在时刻0有一个顾客到达，则下一个顾客将在时刻T到达。T的分布函数为 其中pTt表示在0，t）内没有顾客到达的概率，因此 所以，T的分布函数为,T的密度函数为 因此，顾客相继到达

13、的时间间隔服从以为参数的负指数分布。 可以看出，“到达的顾客数是一个以为参数的Poisson流”与“顾客相继到达的时间间隔服从以为参数的负指数分布”两个事实是等价的。,顾客相继到达的时间间隔服从以为参数的负指数分布,服务时间 服从负指数分布，概率密度为,参数同样具有两层含义：单位时间内服务的顾客人数的期望值，或称平均服务率。,由于的均值为1/ ，即平均对每位顾客的服务时间 为1/ .,服务时间服从以为参数的负指数分布,负指数分布具有无记忆性 定理 设对顾客的服务时间X服从参数为的负指数分布。在对某一个顾客的服务已经进行了一定时间的条件下，这个顾客的剩余的服务时间仍服从以为参数的负指数分布。 证

14、明：设服务已经进行的时间为，则剩余时间不少于t的条件概率为 由此看出，服务剩余时间的分布独立与已经服务过的时间，并且与原来的服务时间的分布相同。,设v1，v2，vk是k个互相独立的，具有相同参数的负指数分布随机变量，则随机变量 服从k阶Erlang分布，S的密度函数为,四、k阶爱尔朗(Erlang)分布,期望值为 方差为,注意：当k=1时，爱尔朗分布就是负指数分布，是完全随机的；当k=30时，近似于正态分布；一般k阶爱尔朗分布可看成是完全随机与完全确定的中间型，有更广泛的适应性。,一、M/M/1模型,1、假设,第三节 单服务台负指数分布排队系统的分析,求：（1）系统状态概率Pn； （2）系统运

15、行指标Ls，Lq，Ws，Wq。,2、Pn的计算,注：表示发生（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，

16、则Pn关于t的导数为0。,这时(1)式和(2)式可得,状态转移图 以系统中的顾客数0，1，2，n-1，n，n+1，作为系统的状态， (3)和(4)表示系统位于某一状态的概率仅与其相邻状态的概率以及从相邻状态转移到该状态的概率有关。 系统状态（n）随时间变化的过程是生灭过程的一个特殊情况， (3)和(4)关于Pn的差分方程，可以用状态转移图来表示各状态间的转移关系，并能求解。,由(3)和(4)可以递推求解P1，P2，Pn，。 由(3)得到 (5) 由(4)得到 (6) 将(5)代入(6) 用递推方法可以得到 (7),由 得到 令 称为服务强度，则 当 时，级数收敛，这时有 (8),代入(7)，得

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

18、的概率为： 系统中有2辆车的概率为： 系统中有3辆车的概率为：,3、M/M/1 参数计算,（1）系统中平均顾客数队长（Ls）,（2）队列中等待的平均顾客数（Lq）,即Lq=Ls,（3）顾客逗留时间（Ws）,（4）队列中顾客等待时间（Wq）,将以上结果总结如下： 对于M/M/1/FCFS系统， 系统中由k个顾客的概率为： 系统中的平均顾客数为： 队列的平均长度为： 顾客在系统中的平均逗留时间为： 顾客在队列中的平均等待时间为：,Little公式 一般化 Little公式的条件: 排队系统能够进入统计平衡状态； 服务台的忙期与闲期交替出现； 系统中任一顾客不会永远等待，系统也不会永远无顾客到达。,

19、例3 100个工作小时内每小时来就诊的病人数n出现次数如下,100个完成手术的病例所用时间v（小时）出现的次数如下,假定系统最大容量为N，单服务台情形，排队等待的顾客最多为N-1，下面只考虑稳态情形：,二、M/M/1/N/模型,顾客到达,因队列满而离去,进入队列,接受服务,服务完毕后离去,根据上式我们可以推导出系统的各项指标：,有效到达率：,例4 单人理发馆有六个椅子接待客人。当6个椅子都坐满时，后来的顾客不进店就离开。顾客平均到达率为3人/小时，理发需时平均15分钟。则：,N=7为系统中最大的顾客数，=3人/小时，=4人/小时,（1）求某顾客一到达就能理发的概率。,（2）求需要等待的顾客数的

20、期望值。,（3）求有效到达率。,（4）求一顾客在理发馆内逗留的时间。,（5）在可能到达的顾客中有百分之几不等待就离开。,机器故障问题：设共有m台机器，机器故障停机表示到达，待修机器形成队列，修理工是服务员。,顾客总体虽然只有m个，但每个顾客服务后仍回到总体，仍然可以到来。,三、顾客源有限的情形(M/M/1/m),的含义发生改变,表示全体顾客的平均到达率,表示每个顾客的平均到达率,说明：进入率与状态有关 若m=5,n=3; 如下图所示：,系统中已经有两人丁和戊 进入的为甲、乙或丙，所以为： e=3,由此列出平衡方程：,状态概率,根据上式我们可以推导出系统的各项指标：,在机器故障问题中Ls就是平均

21、故障台数，而,例 5 某车间有5台机器，每台机器的连续运转时间服从负指数分布，平均连续运转时间15分钟，有一个修理工，每次修理时间服从负指数分布，平均每次12分钟。,求 （1）修理工空闲的概率；,（2）五台机器都出故障的概率；,（3）出故障的平均台数；,（4）等待修理的台数；,（5）平均停工时间；,（6）平均等待时间；,（7）评价这些结果。,（7） 机器停工时间过长，修理工几乎没有空闲时间，应当提高服务率减少修理时间或增加修理工人。,第四节 多服务台指数分布排队系统的分析,一、M/M/c,用递推法解上述差分方程，可求得状态概率。,根据上式我们可以推导出系统的各项指标：,例6 某售票所有三个窗口

22、，顾客到达服从Passion过程，平均到达率每分钟=0.9(人),服务(售票)时间服从负指数分布,平均服务率每分钟=0.4(人).,（1）整个售票所空闲的概率,（2）平均队长,（3）平均等待时间和逗留时间,（4）顾客到达后必须等待（即系统中顾客数已有3人）的概率,二、M/M/c型系统和c个M/M/1系统的比较,上例中，排队方式不变，但顾客到达后在每个窗口前各排一队，且进入队列后坚持不换，这就形成3个队列，如下图二每个队列平均到达率为=0.9/3=0.3（每分钟），这样原来的系统就变成3个M/M/1型的子系统。,现按M/M/1型解决这个问题，并与上表比较：,从表中各指标的对比可以看出单队比三队有

23、显著的优越性,三、系统容量有限定的M/M/c/N/模型,因队列满而离去,系统的状态概率和运行指标如下:,四、顾客源为有限的M/M/c/m模型,稳态概率方程,求得,其中：,例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,即：=ET,Pollaczek-Khinchine 公式,注：服务时间是任意分布，上述PK公式仍然成立的；所以只要知道，E(T)，Var(T);不管T是何种分布，都可以求出Ls，Lq，Ws，Wq,例8 有一售票口,已知顾客按平均为2分30秒的时间间隔的负指数分布到达.顾客在售票口前服务时间平均为2分钟.(1)若服务时间也服从负指数分布,求顾客为购票所需的平均逗留时间和等待时间;(2)若经过调查,顾客在售票口前至少要占用1分钟,且认