运筹学排队论新精选课件.ppt

关于运筹学排队论新第一页，本课件共有131页第十二章第十二章 排队论排队论 到达间隔的分布和服务时间的分布到达间隔的分布和服务时间的分布本章内容本章内容基本概念基本概念单服务台负指数分布排队系统的分析单服务台负指数分布排队系统的分析多服务台负指数分布排队系统的分析多服务台负指数分布排队系统的分析一般服务时间一般服务时间M/G/1模型模型第二页，本课件共有131页 排排队队论论(Queuing Theory)，又又称称随随机机服服务务系系统统理理论论(Random Service System Theory)。1909年年由由丹丹麦麦工工程程师师爱爱尔尔朗朗(A.KErlang)在在研研究究电电话话系系统统时时创创立立的的。具具体体地地说说，它它是是在在研研究究各各种种排排队队系系统统概概率率规规律律性性的的基基础础上上，解解决决相相应应排排队队系系统统的的最最优优设设计计和和最最优优控控制制问问题题。特特别别是是自自二二十十世世纪纪60年年代代以以来来，由由于于计计算算机机的的飞飞速速发发展展，使使排排队论的应用有了更广阔的前景。队论的应用有了更广阔的前景。第三页，本课件共有131页Where the Time Goes?美国人一生中平均要花费美国人一生中平均要花费-6年年 饮食饮食5年年 排队等待排队等待4年年 做家务做家务2年年 回电话不成功回电话不成功 1年年 寻找放置不当的物品寻找放置不当的物品8个月个月 打开邮寄广告打开邮寄广告6个月个月 停在红灯前停在红灯前第四页，本课件共有131页商业服务系统商业服务系统系统类型系统类型顾客顾客服务台服务台理发店理发店人人理发师理发师银行出纳服务银行出纳服务人人出纳出纳ATMATM机服务机服务人人ATMATM机机商店收银台商店收银台人人收银员收银员管道服务管道服务阻塞的管道阻塞的管道管道工管道工电影院售票窗口电影院售票窗口人人售票员售票员机场检票处机场检票处人人航空公司代理人航空公司代理人经纪人服务经纪人服务人人股票经纪人股票经纪人第五页，本课件共有131页运输服务系统运输服务系统系统类型系统类型顾客顾客服务台服务台公路收费站公路收费站汽车汽车收费员收费员卡车装货地卡车装货地卡车卡车装货工人装货工人港口卸货区港口卸货区轮船轮船卸货工人卸货工人等待起飞的飞机等待起飞的飞机飞机飞机跑道跑道航班服务航班服务人人飞机飞机出租车服务出租车服务人人出租车出租车电梯服务电梯服务人人电梯电梯消防部门消防部门火灾火灾消防车消防车停车场停车场汽车汽车停车空间停车空间急救车服务急救车服务人人急救车急救车第六页，本课件共有131页 面面对对拥拥挤挤现现象象，如如何何做做到到既既保保证证一一定定的的服服务务质质量量指指标标，又又使使服服务务设设施施费费用用经经济济合合理理，恰恰当当地地解解决决顾顾客客排排队队时时间间与与服服务务设设施施费费用用大大小小这这对对矛矛盾盾，这这就就是是排排队队论论所所要要研研究究解解决决的的问题之一。问题之一。第七页，本课件共有131页第一节第一节 基本概念基本概念第八页，本课件共有131页（一）排队系统的特征及组成（一）排队系统的特征及组成排队系统的共同特征排队系统的共同特征:有有要要求求得得到到某某种种服服务务的的人人或或物物。排排队队论里把要求服务的对象统称为论里把要求服务的对象统称为“顾客顾客”有有提提供供服服务务的的人人或或机机构构。把把提提供供服服务务的的人或机构称为人或机构称为“服务台服务台”或或“服务员服务员”顾顾客客的的到到达达、服服务务的的时时间间至至少少有有一一个是个是随机的随机的，服从某种分布。，服从某种分布。第九页，本课件共有131页一般的排队系统，都可由一般的排队系统，都可由图图12-112-1加以描述。加以描述。顾客源顾客源排队结构排队结构服服务务机机构构排队规则排队规则顾客到来顾客到来服务规则服务规则离去离去图图12-1排队系统排队系统第十页，本课件共有131页 排队系统都有输入过程、排队规则和服务排队系统都有输入过程、排队规则和服务台等台等3个组成部分：个组成部分：1、输入过程输入过程 这是指要求服务的顾客是按怎样这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为的规律到达排队系统的过程，有时也把它称为顾客流一般可以从顾客流一般可以从3个方面来描述输入过程。个方面来描述输入过程。排队系统的组成排队系统的组成第十一页，本课件共有131页(1)顾客总体数组成顾客总体数组成(又称顾客源又称顾客源)是是有限有限的，也的，也可以是可以是无限无限的。例如，到售票处购票的顾客总的。例如，到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。的机床则是有限的。(2)顾客到达方式。描述顾客是怎样来到系统的，顾客到达方式。描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。客则是成批到达的。第十二页，本课件共有131页(3)顾客流的概率分布，或称顾客相继到达顾客流的概率分布，或称顾客相继到达时间间隔的分布。这是求解排队系统有关运时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。行指标问题时，首先需要确定的指标。顾客流的概率分布一般有定长分布、顾客流的概率分布一般有定长分布、二项分布、泊松流二项分布、泊松流(最简单流最简单流)、爱尔朗分布、爱尔朗分布等若干种。等若干种。第十三页，本课件共有131页2、排队规则排队规则 这是指服务台从队列中选取顾这是指服务台从队列中选取顾客进行服务的顺序。客进行服务的顺序。损失制损失制混合制混合制队长有限队长有限等待时间有限等待时间有限逗留时间有限逗留时间有限排队规则排队规则等待制等待制先到先服务先到先服务后到先服务后到先服务随机服务随机服务优先权服务优先权服务第十四页，本课件共有131页3服务台情况服务台情况。服务台可以从。服务台可以从3方面来描述：方面来描述：(1)服务台数量及构成形式服务台数量及构成形式图图12-2 单队列单队列-单服务台排队系统单服务台排队系统第十五页，本课件共有131页图图12-3 单队列单队列S个服务台并联的排队系统个服务台并联的排队系统图图12-4 S个队列个队列S个服务台的并联排队系统个服务台的并联排队系统第十六页，本课件共有131页图图12-5 单队单队多个服务台的串联排队系统多个服务台的串联排队系统图图12-6 多队多队多服务台混联、网络系统多服务台混联、网络系统第十七页，本课件共有131页(2)服务方式服务方式。这是指在某一时刻接。这是指在某一时刻接受服务的顾客数，它有单个服务和成批受服务的顾客数，它有单个服务和成批服务两种。服务两种。(3)服务时间的分布服务时间的分布。在多数情况下，。在多数情况下，对每一个顾客的服务时间是一随机变量，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、其概率分布有定长分布、负指数分布、K级爱尔朗分布、一般分布级爱尔朗分布、一般分布(所有顾客的所有顾客的服务时间都是独立同分布的服务时间都是独立同分布的)等等。等等。第十八页，本课件共有131页 为了区别各种排队系统，根据输入过程、为了区别各种排队系统，根据输入过程、排队规则和服务机制的不同，对排队模型进排队规则和服务机制的不同，对排队模型进行分类。行分类。DGKendall在在1953年提出了模型年提出了模型分类方法，分类方法，1971年在年在排队论符号标准化会议排队论符号标准化会议上，将上，将Kendall符号扩充为如下固定格式：符号扩充为如下固定格式：X/Y/Z/A/B/C各符号的意义为：各符号的意义为：（二）排队模型的分类（二）排队模型的分类第十九页，本课件共有131页X表示顾客相继到达间隔时间分布，常用下表示顾客相继到达间隔时间分布，常用下列符号：列符号：X/Y/Z/A/B/CM表示到达过程为泊松过程或负指数分布；表示到达过程为泊松过程或负指数分布；D表示定长输入；表示定长输入；Ek表示表示k阶爱尔朗分布；阶爱尔朗分布；GI表示一般相互独立的时间间隔分布；表示一般相互独立的时间间隔分布；G表示一般服务时间的分布。表示一般服务时间的分布。第二十页，本课件共有131页Y表示服务时间分布，常用下列符号：表示服务时间分布，常用下列符号：X/Y/Z/A/B/CM表示服务过程为泊松过程或负指数分布；表示服务过程为泊松过程或负指数分布；D表示定长分布；表示定长分布；Ek表示表示k阶爱尔朗分布；阶爱尔朗分布；G表示一般相互独立的随机分布。表示一般相互独立的随机分布。第二十一页，本课件共有131页Z表示服务台表示服务台(员员)个数：个数：“1”则表示单个服务台，则表示单个服务台，“s”(s1)表示表示多个服务台。多个服务台。X/Y/Z/A/B/CA表示系统中顾客容量限额，或称等待空间表示系统中顾客容量限额，或称等待空间容量：容量：时为等待制系统，此时时为等待制系统，此时一般省略不写；一般省略不写；若为有限整数时，为混合制系统。若为有限整数时，为混合制系统。第二十二页，本课件共有131页B表示顾客源限额。表示顾客源限额。分有限与无限两种，分有限与无限两种，表示顾客源无限，表示顾客源无限，此时一般此时一般也可省略不写。也可省略不写。X/Y/Z/A/B/CC表示服务规则，常用下列符号：表示服务规则，常用下列符号：FCFS：表示先到先服务；：表示先到先服务；LCFS：表示后到先服务；：表示后到先服务；PR：表示优先权服务。：表示优先权服务。第二十三页，本课件共有131页例如：某排队问题为例如：某排队问题为 MMSFCFS则表示顾客到达间隔时间为负指数分则表示顾客到达间隔时间为负指数分布布(泊松流泊松流)；服务时间为负指数分布；服务时间为负指数分布；有有s(s1)个服务台；个服务台；系统等待空间容量无限系统等待空间容量无限(等待制等待制)；顾客源无限，采用先到先服务规则。顾客源无限，采用先到先服务规则。可简记为：可简记为：M/M/s 第二十四页，本课件共有131页 某些情况下，排队问题仅用上某些情况下，排队问题仅用上述表达形式中的前述表达形式中的前3个、个、4个、个、5个个符号。如不特别说明均理解为系统符号。如不特别说明均理解为系统等待空间容量无限；顾客源无限，等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系先到先服务，单个服务的等待制系统统。第二十五页，本课件共有131页（三）排队系统的主要数量指标（三）排队系统的主要数量指标1.队长和排队长队长和排队长队长队长是指系统中的顾客数是指系统中的顾客数(排队等待的顾排队等待的顾 客客数与正在接受服务的顾客数之和数与正在接受服务的顾客数之和)。排队长排队长是指系统中正在排队等待服务的顾客数。是指系统中正在排队等待服务的顾客数。第二十六页，本课件共有131页2等待时间和逗留时间等待时间和逗留时间 从顾客到达时刻起到他开始接受服务止从顾客到达时刻起到他开始接受服务止这段时间称为这段时间称为等待时间等待时间，是随机变量。，是随机变量。从顾客到达时刻起到他接受服务完成止这段从顾客到达时刻起到他接受服务完成止这段时间称为时间称为逗留时间逗留时间，也是随机变量。，也是随机变量。第二十七页，本课件共有131页3忙期和闲期忙期和闲期忙期忙期是指从顾客到达空闲着的服务机是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段构起，到服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间。这是个时间，即服务机构连续忙的时间。这是个随机变量，它关系到服务员的服务强度。随机变量，它关系到服务员的服务强度。与忙期相对的是与忙期相对的是闲期闲期，即服务机构连续，即服务机构连续保持空闲的时间。在排队系统中，忙期和闲保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。期总是交替出现的。第二十八页，本课件共有131页 除了上述几个基本数量指标外，还除了上述几个基本数量指标外，还会用到其他一些重要的指标：会用到其他一些重要的指标：损失制或系统容量有限的情况下，损失制或系统容量有限的情况下，由于顾客被拒绝，而使服务系统受到损由于顾客被拒绝，而使服务系统受到损失的失的顾客损失率顾客损失率及及服务强度服务强度等，也都是等，也都是十分重要的数量指标。十分重要的数量指标。第二十九页，本课件共有131页 4.一些数量指标的常用记号一些数量指标的常用记号 (1)主要数量指标主要数量指标 N(t)：时刻：时刻t系统中的顾客数系统中的顾客数(又称为系统又称为系统的状态的状态)，即队长；，即队长；Nq(t)：时刻：时刻t系统中排队的顾客数，即排队长；系统中排队的顾客数，即排队长；T(t)：时刻：时刻t到达系统的顾客在系统中的逗留到达系统的顾客在系统中的逗留时间；时间；Tq(t)：时刻：时刻t到达系统的顾客在系统中的等到达系统的顾客在系统中的等待时间。待时间。第三十页，本课件共有131页 上面数量指标一般都是和系统运行上面数量指标一般都是和系统运行的时间有关的随机变量，求它们的瞬时的时间有关的随机变量，求它们的瞬时分布一般很困难。注意到相当一部分排分布一般很困难。注意到相当一部分排队系统在运行了一定时间后，都会趋于队系统在运行了一定时间后，都会趋于一个平衡状态一个平衡状态(或称平稳状态或称平稳状态)。在平衡状态下，这些量与系统所处的在平衡状态下，这些量与系统所处的时刻无关，而且系统的初始状态的影响也时刻无关，而且系统的初始状态的影响也会消失。因此，我们会消失。因此，我们在本章中将主要讨论在本章中将主要讨论与系统所处时刻无关的性质，即统计平衡与系统所处时刻无关的性质，即统计平衡性质。性质。第三十一页，本课件共有131页L L或或L Ls s平均队长平均队长稳态系统任一时刻的顾客数的期望值；稳态系统任一时刻的顾客数的期望值；L Lq q平均等待队长或队列长平均等待队长或队列长稳态系统任一时刻等待服务的顾客数期望值；稳态系统任一时刻等待服务的顾客数期望值；W W或或W Ws s 平均逗留时间平均逗留时间 进入稳态系统的顾客逗留时间期望值；进入稳态系统的顾客逗留时间期望值；W Wq q平均等待时间平均等待时间 进入稳态系统的顾客等待时间期望值。进入稳态系统的顾客等待时间期望值。第三十二页，本课件共有131页P Pn n 系统的状态系统的状态P Pn n=P P N N=n n：稳态系统任一时刻状态为：稳态系统任一时刻状态为n n的概率。的概率。当当 n=0 时，时，Pn即即P0为稳态系统所有服务台全部空闲的概率。为稳态系统所有服务台全部空闲的概率。第三十三页，本课件共有131页(2)其他常用数量指标其他常用数量指标s系统中并联服务台的数目系统中并联服务台的数目 平平均均到到达达率率（单单位位时时间间内内到到达达的的平均顾客数）平均顾客数）1/平均到达间隔平均到达间隔 平平均均服服务务率率（单单位位时时间间内内可可以以服服务务完的平均顾客数）完的平均顾客数）1/平均服务时间平均服务时间第三十四页，本课件共有131页 对于损失制和混合制的排队系统，顾对于损失制和混合制的排队系统，顾客在到达服务系统时，若系统容量已满，客在到达服务系统时，若系统容量已满，则自行消失。这就是说，到达的顾客不一则自行消失。这就是说，到达的顾客不一定全部进入系统，为此引入：定全部进入系统，为此引入：e 有效有效平均到达率平均到达率，即每单位时间实际进入系统的，即每单位时间实际进入系统的平均顾客数（期望值），不同于平均顾客数（期望值），不同于 。对于等待制的排队系统，有：对于等待制的排队系统，有：e 第三十五页，本课件共有131页第二节第二节 到达间隔的分布和服务时间的分布到达间隔的分布和服务时间的分布第三十六页，本课件共有131页 一、一、Poisson流流（Poisson过程过程）定义定义 满足以下三个条件的输入流称为满足以下三个条件的输入流称为PoissonPoisson流流1 1、无后效性无后效性：不相交的时间区间内到达的顾客数互：不相交的时间区间内到达的顾客数互相独立。相独立。2 2、平稳性平稳性：在时间区间在时间区间t,t+t,t+t)t)内到达内到达1 1个顾客个顾客的概率只与的概率只与 t t有关。即有关。即 表示单位时间内有一个顾客到达的概率。表示单位时间内有一个顾客到达的概率。3 3、普通性普通性：设在设在t,t+t,t+t t）内到达多于一个顾客）内到达多于一个顾客的概率极小，即的概率极小，即第三十七页，本课件共有131页Poisson流与流与Poisson分布分布定定理理1 对对于于一一个个参参数数为为 的的Poisson流流，在在0，t内到达内到达n个顾客的概率为个顾客的概率为 即服从以即服从以 为参数的为参数的Poisson分布。分布。定理定理1说明说明 如果顾客的到达为如果顾客的到达为Poisson流的话，则到流的话，则到达顾客数的分布恰好为达顾客数的分布恰好为Poisson分布。分布。第三十八页，本课件共有131页 二、负指数分布二、负指数分布 在实际的排队系统中服务时间的概率分布可以是各在实际的排队系统中服务时间的概率分布可以是各种形式，但在排队论中，最容易进行数学处理、最常用种形式，但在排队论中，最容易进行数学处理、最常用的一种重要分布是负指数分布。的一种重要分布是负指数分布。设随机变量设随机变量T服从以服从以 为参数的负指数分布，它的为参数的负指数分布，它的分布函数为：分布函数为：第三十九页，本课件共有131页负指数分布的性质：负指数分布的性质：性质性质1 1 由条件概率公式容易证明由条件概率公式容易证明 性质性质2 2 当单位时间内的顾客到达数服从以当单位时间内的顾客到达数服从以 为平均数的为平均数的泊松分布时，则顾客相继到达的间隔时间泊松分布时，则顾客相继到达的间隔时间T T服从负指数分服从负指数分布。布。这性质称为这性质称为无记忆性无记忆性。若。若T T表示排队系统中顾客到达的时表示排队系统中顾客到达的时间间隔，那么这个性质说明一个顾客到来所需要的时间与间间隔，那么这个性质说明一个顾客到来所需要的时间与过去一个顾客到来所需要的时间过去一个顾客到来所需要的时间s s无关，所以说在这种情形无关，所以说在这种情形下的顾客到达是纯随机的。下的顾客到达是纯随机的。第四十页，本课件共有131页由性质由性质2 2可知：可知：相继到达的间隔时间是独立且为相同参相继到达的间隔时间是独立且为相同参数的负指数分布，与输入过程为泊松流（参数为数的负指数分布，与输入过程为泊松流（参数为 ）是）是等价的。等价的。根据负指数分布与泊松流的关系可以推导出，当根据负指数分布与泊松流的关系可以推导出，当服务机构对顾客的服务时间服从参数为服务机构对顾客的服务时间服从参数为 的负指数分的负指数分布，如果服务机构处于忙期，则该服务机构的输出，布，如果服务机构处于忙期，则该服务机构的输出，即服务完毕离开服务机构的顾客数将是服从泊松分布即服务完毕离开服务机构的顾客数将是服从泊松分布的泊松流。其中的泊松流。其中 为每个顾客的平均服务时间，也是为每个顾客的平均服务时间，也是顾客相继离开的间隔顾客相继离开的间隔。第四十一页，本课件共有131页三、三、k阶爱尔朗分布阶爱尔朗分布定定理理 设设v1，v2，vk是是k个个互互相相独独立立的的随随机机变变量量，服服从相同参数从相同参数k 的负指数分布，那么的负指数分布，那么S=v1+v2+vk服从服从k阶阶Erlang分布，分布，S的密度函数为的密度函数为第四十二页，本课件共有131页K K=1=1时爱尔朗分布化归为负指数分布，当时爱尔朗分布化归为负指数分布，当K K时，得到长度为时，得到长度为1/1/的定长服务。的定长服务。m=1k=1k=2k=4k=8第四十三页，本课件共有131页第三节第三节 单服务台负指数分布排队系统的分析单服务台负指数分布排队系统的分析第四十四页，本课件共有131页标准排队模型标准排队模型 M/M/1:/FCFS顾客到达的时间间隔是负指数分布，顾客到达的时间间隔是负指数分布，即输入流是参数为即输入流是参数为 的的Poisson流流服从参数为服从参数为的负指数分布的负指数分布一个服务台一个服务台排队系统的容量无限排队系统的容量无限顾客源的容量无限顾客源的容量无限实行先到先服务的一个服务系统实行先到先服务的一个服务系统第四十五页，本课件共有131页一、系统稳态概率一、系统稳态概率p pn n的计算的计算 假设在假设在t+t+t t时刻系统中顾客数为时刻系统中顾客数为n n的概率的概率P Pn n(t+(t+t)t)Pn(t)Pn-1(t)Pn+1(t)Pn(t)Snt+t时刻时刻SnSnSn+1Sn-1t时刻时刻无到达，无离开无到达，无离开无到达，离开一个无到达，离开一个到达一个，无离开到达一个，无离开到达一个，离开一个到达一个，离开一个第四十六页，本课件共有131页由于这四种方式互不相容，故由概率的加法定理得：由于这四种方式互不相容，故由概率的加法定理得：该差分方程组为该差分方程组为瞬态解瞬态解，需求稳态解。，需求稳态解。第四十七页，本课件共有131页M/M/1:/FCFS稳态时状态转移图稳态时状态转移图012n-1nn+1稳态情况下，系统状态已不随时间发生变化：稳态情况下，系统状态已不随时间发生变化：第四十八页，本课件共有131页稳态情况下，系统状态已不随时间发生变化：稳态情况下，系统状态已不随时间发生变化：第四十九页，本课件共有131页得到得到 令令称称 为服务强度，则为服务强度，则得得第五十页，本课件共有131页系统的过渡状态与稳定状态系统的过渡状态与稳定状态过渡过渡稳定稳定第五十一页，本课件共有131页二、二、系统的数量指标系统的数量指标1 1、服务台空闲的概率和忙的概率：、服务台空闲的概率和忙的概率：空闲的概率：空闲的概率：P P0 0=1-=1-忙的概率：忙的概率：1-P0 0=2 2、系统中平均顾客数（队长期望值、系统中平均顾客数（队长期望值LsLs）：）：第五十二页，本课件共有131页3 3、系统中等待的平均顾客数（队长期望值、系统中等待的平均顾客数（队长期望值LqLq）：）：4 4、系统中顾客逗留时间的期望值：、系统中顾客逗留时间的期望值：第五十三页，本课件共有131页5 5、队列中顾客逗留时间的期望值：、队列中顾客逗留时间的期望值：现将以上公式归纳如下：现将以上公式归纳如下：它们相互关系如下：它们相互关系如下：第五十四页，本课件共有131页Little公式公式下列公式对任何服务系统均成立下列公式对任何服务系统均成立第五十五页，本课件共有131页例例1 高高速速公公路路入入口口收收费费处处设设有有一一个个收收费费通通道道，汽汽车车到到达达服服从从Poisson分分布布，平平均均到到达达速速率率为为100辆辆小小时时，收收费费时时间间服服从从负负指指数分布，平均收费时间为数分布，平均收费时间为15秒辆。求秒辆。求1、收费处空闲的概率；、收费处空闲的概率；2、收费处忙的概率；、收费处忙的概率；3、系统中分别有、系统中分别有1，2，3辆车的概率。辆车的概率。第五十六页，本课件共有131页解解：根根据据题题意意,=100辆辆/小小时时,1/=15（秒秒/辆辆）=1/240（小时（小时/辆）辆）,即即 240（辆（辆/小时）。小时）。因此，因此，=/=100/240=5/12。系统空闲的概率为：系统空闲的概率为：P0=1-=1-(5/12)=7/12=0.583系统忙的概率为：系统忙的概率为：1-P0=1-(1-)=5/12=0.417第五十七页，本课件共有131页系统中有系统中有1辆车的概率为：辆车的概率为：P1=(1-)=0.4170.583=0.243系统中有系统中有2辆车的概率为：辆车的概率为：P2=2(1-)=0.417 20.583=0.101系统中有系统中有3辆车的概率为：辆车的概率为：P3=3(1-)=0.417 30.583=0.0421第五十八页，本课件共有131页例例2 高高速速公公路路入入口口收收费费处处设设有有一一个个收收费费通通道道，汽汽车车到到达达服服从从Poisson分分布布，平平均均到到达达速速率率为为200辆辆小小时时，收收费费时时间间服服从从负负指指数数分分布布，平平均均收收费费时时间间为为15秒秒辆辆。求求Ls、Lq、Ws和和Wq。第五十九页，本课件共有131页解：根据题意，解：根据题意，=200辆辆/小时，小时，=240辆辆/小小时，时，=/=5/6。第六十页，本课件共有131页有限队列模型有限队列模型 M/M/1:N/FCFS 如果系统的最大容量为如果系统的最大容量为N时，排队等待的顾客最多为时，排队等待的顾客最多为N-1，在某时刻一顾客到达时，如系统中已有，在某时刻一顾客到达时，如系统中已有N个顾客，个顾客，那么这个顾客就被拒绝进入系统。那么这个顾客就被拒绝进入系统。第六十一页，本课件共有131页系统的状态概率平衡方程系统的状态概率平衡方程对于状态对于状态0：P1=P0对于状态对于状态k：Pk-1+Pk+1=(+)Pk 0k3)=0.57P(N3)=0.570.750.75排队长排队长1.71.7（人）（人）2.252.25（人）（人）（各子系统）（各子系统）平均队长平均队长3.953.95（人）（人）9 9（人）（人）（整个系统）（整个系统）平均逗留时间平均逗留时间4.394.39（分钟）（分钟）1010（分钟）（分钟）平均等待时间平均等待时间1.891.89（分钟）（分钟）7.57.5（分钟）（分钟）第八十九页，本课件共有131页M/M/c:N/FCFS模型模型 离开离开服务台服务台服务台服务台服务台服务台顾客到达顾客到达顾客离去顾客离去顾客离去顾客离去顾客离去顾客离去队列队列设系统容量为设系统容量为N(Nc)。设顾客到达的速率为。设顾客到达的速率为，每，每个服务台服务的速率为个服务台服务的速率为，=/c。由于系统不会无限止。由于系统不会无限止地接纳顾客，对地接纳顾客，对不必加以限制。不必加以限制。第九十页，本课件共有131页状态转移图与状态转移方程状态转移图与状态转移方程对状态对状态0:P0=P1对状态对状态1:P0+2P2=(+)P1对状态对状态 c：Pc-1+cPc+1=(+c)Pc对状态对状态N PN-1=cPN 01cN第九十一页，本课件共有131页状态概率状态概率第九十二页，本课件共有131页运行指标运行指标 第九十三页，本课件共有131页例例6 某某旅旅馆馆有有8个个单单人人房房间间，旅旅客客到到达达服服从从Poisson流流，平平均均速速率率为为6人人天天，旅旅客客平均逗留时间为平均逗留时间为2天，求：天，求：(1)每天客房平均占用数；每天客房平均占用数；(2)旅馆客满的概率。旅馆客满的概率。第九十四页，本课件共有131页解：解：旅馆旅馆8个房间全满的概率为个房间全满的概率为0.423 平均占用客房数为平均占用客房数为6.9间。间。第九十五页，本课件共有131页M/M/c:/m/FCFS模型模型 顾客到达顾客到达修理速率修理速率发生故障等待修理的机器发生故障等待修理的机器修理速率修理速率修理速率修理速率正在修理的机器正在修理的机器到达速率到达速率 (m-n)(m-n)修理速率修理速率cc运行的机器数运行的机器数 m-nm-n第九十六页，本课件共有131页状态概率状态概率 其中其中 第九十七页，本课件共有131页运行指标运行指标有有效效到到达达速速率率e为为单单位位时时间间内内出出现现故故障的机器数，有障的机器数，有e=(m-Ls)第九十八页，本课件共有131页例例7 7 车车间间有有5 5台台机机器器，每每台台机机器器的的故故障障率率为为1 1次次小小时时，有有2 2个个修修理理工工负负责责修修理理这这5 5台台机机器器，工作效率相同，为工作效率相同，为4 4台小时。求：台小时。求：(1)(1)等待修理的平均机器数；等待修理的平均机器数；(2)(2)正在修理的平均机器数；正在修理的平均机器数；(3)(3)每小时发生故障的平均机器数；每小时发生故障的平均机器数；(4)(4)平均等待修理的时间；平均等待修理的时间；(5)(5)平均停工时间。平均停工时间。第九十九页，本课件共有131页解解 可以计算得到（算式略）：可以计算得到（算式略）：P1=0.394，P2=0.197，P3=0.074，P4=0.018，P5=0.002 第一百页，本课件共有131页由此，计算系统的各项运行指标如下：由此，计算系统的各项运行指标如下：第一百零一页，本课件共有131页第第5 5节节 一般服务时间一般服务时间M/G/1M/G/1模型模型第一百零二页，本课件共有131页服务时间一般分布时，需要知道服务时服务时间一般分布时，需要知道服务时间的均值间的均值 和方差和方差 。当。当 时，排队系统时，排队系统可以达到平稳状态。可以达到平稳状态。PK公式公式第一百零三页，本课件共有131页1 1 负指数服务时间负指数服务时间M/M/1M/M/1模型模型只有负指数分布时排队长的一半。只有负指数分布时排队长的一半。2 定长服务时间定长服务时间M/D/1模型模型第一百零四页，本课件共有131页3 k阶爱尔朗服务时间阶爱尔朗服务时间M/Ek/1模型模型若顾客需接受若顾客需接受k个串行的服务台的个串行的服务台的服务后才离开，且每个服务台服务时服务后才离开，且每个服务台服务时间服从负指数分布，平均服务时间相间服从负指数分布，平均服务时间相等。等。则总服务时间服从则总服务时间服从k阶爱尔朗分布。阶爱尔朗分布。第一百零五页，本课件共有131页ErlangErlang分布的均值和方差分布的均值和方差总服务时间服从爱尔朗分布：总服务时间服从爱尔朗分布：每个服务台的平均服务时间是：每个服务台的平均服务时间是：第一百零六页，本课件共有131页M/EM/Ek k/1/1系统的运行指标系统的运行指标第一百零七页，本课件共有131页例例8 有一汽车冲洗台，汽车按有一汽车冲洗台，汽车按Poisson流到流到达，平均每小时到达达，平均每小时到达18辆；冲洗时间辆；冲洗时间T的的平均值平均值=0.05小时小时/辆，方差辆，方差Var(T)=0.01(小时小时/辆辆)2，求该洗车台的运行指标，并对，求该洗车台的运行指标，并对它进行评价。它进行评价。解：解：本例是本例是M/G/1系统，且已知系统，且已知第一百零八页，本课件共有131页 可见顾客等待时间太长，队列也太长。主可见顾客等待时间太长，队列也太长。主要原因是服务时间的方差太大！要原因是服务时间的方差太大！第一百零九页，本课件共有131页例例9 某单人裁缝店做西服，每套需经过某单人裁缝店做西服，每套需经过4个不个不同的工序，同的工序，4个工序完成后才开始做另一套。每个工序完成后才开始做另一套。每一工序的时间服从负指数分布，期望值为一工序的时间服从负指数分布，期望值为2小小时。顾客到来服从泊松分布，平均订货率为时。顾客到来服从泊松分布，平均订货率为5.5套套/周（设一周周（设一周6天，每天天，每天8小时）。问一顾客小时）。问一顾客为等到做好一套西服期望时间有多长？为等到做好一套西服期望时间有多长？解：解：=5.5套套/周周1/:平均每套所需时间平均每套所需时间1/4:平均每工序所需时间，为平均每工序所需时间，为2小时小时1/8套套/小时小时6套套/周周第一百一十页，本课件共有131页顾客为等到做好一套西服期望时间：顾客为等到做好一套西服期望时间：第一百一十一页，本课件共有131页排队论练习题排队论练习题第一百一十二页，本课件共有131页 练习练习1 1：某修理店只有一位修理工，来修理的顾某修理店只有一位修理工，来修理的顾客到达过程为客到达过程为Poisson流，平均每小时流，平均每小时4人；修理人；修理时间服从负指数分布，平均需要时间服从负指数分布，平均需要6分钟。试求：分钟。试求：修理店空闲的概率；店内恰有修理店空闲的概率；店内恰有3位顾客的概率；位顾客的概率；店内至少有一位顾客的概率；在店内平均顾店内至少有一位顾客的概率；在店内平均顾客数；每位在店内平均逗留时间；等待服务客数；每位在店内平均逗留时间；等待服务的平均顾客数；每位顾客平均等待服务时间；的平均顾客数；每位顾客平均等待服务时间；顾客在店内逗留时间超过顾客在店内逗留时间超过10分钟的概率。分钟的概率。第一百一十三页，本课件共有131页解：本例可看成一个解：本例可看成一个M/M/1/M/M/1/排队问题，其中排队问题，其中 =4=4，=1/0.1=10(=1/0.1=10(人人/小时），小时），=/=2/51=2/510=ePT10=e-10(1/6-1/15)-10(1/6-1/15)=e=e=e=e-1-1-1-1=0.3677=0.3677PTt=ePTt=ePTt=ePTt=e-(-(-)t)tt=10t=10分钟分钟,=10=10人人/小时小时=10/60=1/6=10/60=1/6 =4=4人人/小时小时=4/60=1/15=4/60=1/15第一百一十六页，本课件共有131页 练习练习2 2：考虑一个铁路列车编组站。设待编列车到考虑一个铁路列车编组站。设待编列车到达时间间隔服从负指数分布，平均每小时到达达时间间隔服从负指数分布，平均每小时到达2 2列；服务台是编组站，编组时间服从负指数列；服务台是编组站，编组时间服从负指数分布，平均每分布，平均每2020分钟可编一组。已知编组站上分钟可编一组。已知编组站上共有共有2 2股道，当均被占用时，不能接车，再来的股道，当均被占用时，不能接车，再来的列车只能停在站外或前方站。求：列车只能停在站外或前方站。求：1 1、在平衡状态下系统中列车的平均数；、在平衡状态下系统中列车的平均数；2 2、每一列车的平均逗留时间；、每一列车的平均逗留时间；3 3、等待编组的列车平均数；、等待编组的列车平均数；4 4、列车在系统中的平均等待编组时间列车在系统中的平均等待编组时间；5 5、如果列车因站中、如果列车因站中2 2股道均被占用而停在站外股道均被占用而停在站外或前方站时，每列车每小时费用为或前方站时，每列车每小时费用为a a元，求每元，求每天由于列车在站外等待而造成的损失。天由于列车在站外等待而造成的损失。第一百一十七页，本课件共有131页解：解：本例可看成一个本例可看成一个M/M/1/M/M/1/排队问题，其中排队问题，其中=2=2，=3=3，=/=2/31=2/32=W1-P=WPN2=W1-P=WPN2=W1-P=WPN2=W1-P0 0-P-P1 1-P-P2 2 =W1-(=W1-(l-l-)-)-(l-l-)1 1-(l-l-)2 2 2 2 =1*=1*3 3 3 3=3 3=(2/3)=(2/3)3 3=0.296=0.296（小时）（小时）（小时）（小时）故每天列车由于等待而支出的平均费用故每天列车由于等待而支出的平均费用E=24E=24 W W0 0a=24*2*0.296*a=14.2aa=24*2*0.296*a=14.2aa=24*2*0.296*a=14.2aa=24*2*0.296*a=14.2a元元元元第一百一十九页，本课件共有131页练习练习3 3：(病人候诊问题病人候诊问题)某单位医院的一个科某单位医院的一个科室有一位医生值班，经长期观察，每小平均有室有一位医生值班，经长期观察，每小平均有4 4个病人，医生每小时平均可诊个病人，医生每小时平均可诊5 5个病人，病人的个病人，病人的到来服从泊松分布，医生的诊病时间服从负指到来服从泊松分布，医生的诊病时间服从负指数分布，试问：数分布，试问：1 1、该科室平均有病人数；平均排队候诊病人数；看一次、该科室平均有病人数；平均排队候诊病人数；看一次病平均所需的时间；排队等候看病的平均时间病平均所需的时间；排队等