运筹学排队论新

《运筹学排队论新》由会员分享，可在线阅读，更多相关《运筹学排队论新（131页珍藏版）》请在装配图网上搜索。

1、运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外排队论排队论Queuing TheoryQueuing Theory第十二章第十二章 排队论排队论 到达间隔的分布和服务时间的分布到达间隔的分布和服务时间的分布本章内容本章内容基本概念基本概念单服务台负指数分布排队系统的分析单服务台负指数分布排队系统的分析多服务台负指数分布排队系统的分析多服务台负指数分布排队系统的分析一般服务时间一般服务时间M/G/1模型模型 排队论排队论(Queuing Theory)，又称，又称随机服务随机服务系统理论系统理论(Random Service System Theory)。1909年由丹麦工

2、程师爱尔朗年由丹麦工程师爱尔朗(A.KErlang)在在研究电话系统时创立的。具体地说，它是在研究电话系统时创立的。具体地说，它是在研究各种排队系统研究各种排队系统概率规律性概率规律性的基础上，解的基础上，解决相应排队系统的决相应排队系统的最优设计最优设计和和最优控制最优控制问题。问题。特别是自二十世纪特别是自二十世纪60年代以来，由于计算机年代以来，由于计算机的飞速发展，使排队论的应用有了更广阔的的飞速发展，使排队论的应用有了更广阔的前景。前景。Where the Time Goes?美国人一生中平均要花费美国人一生中平均要花费-6年年 饮食饮食5年年 排队等待排队等待4年年 做家务做家务2

3、年年 回电话不成功回电话不成功 1年年 寻找放置不当的物品寻找放置不当的物品8个月个月 打开邮寄广告打开邮寄广告6个月个月 停在红灯前停在红灯前商业服务系统商业服务系统系统类型系统类型顾客顾客服务台服务台理发店理发店人人理发师理发师银行出纳服务银行出纳服务人人出纳出纳ATMATM机服务机服务人人ATMATM机机商店收银台商店收银台人人收银员收银员管道服务管道服务阻塞的管道阻塞的管道管道工管道工电影院售票窗口电影院售票窗口人人售票员售票员机场检票处机场检票处人人航空公司代理人航空公司代理人经纪人服务经纪人服务人人股票经纪人股票经纪人运输服务系统运输服务系统系统类型系统类型顾客顾客服务台服务台公路

4、收费站公路收费站汽车汽车收费员收费员卡车装货地卡车装货地卡车卡车装货工人装货工人港口卸货区港口卸货区轮船轮船卸货工人卸货工人等待起飞的飞机等待起飞的飞机飞机飞机跑道跑道航班服务航班服务人人飞机飞机出租车服务出租车服务人人出租车出租车电梯服务电梯服务人人电梯电梯消防部门消防部门火灾火灾消防车消防车停车场停车场汽车汽车停车空间停车空间急救车服务急救车服务人人急救车急救车 面对拥挤现象，如何做到既保证一定面对拥挤现象，如何做到既保证一定的服务质量指标，又使服务设施费用经济的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，这

5、就是排队论所要施费用大小这对矛盾，这就是排队论所要研究解决的问题之一。研究解决的问题之一。第一节第一节 基本概念基本概念（一）排队系统的特征及组成（一）排队系统的特征及组成 排队系统的共同特征排队系统的共同特征:有要求得到某种服务的人或物。排有要求得到某种服务的人或物。排队论里把要求服务的对象统称为队论里把要求服务的对象统称为“顾客顾客”有提供服务的人或机构。把提供服有提供服务的人或机构。把提供服务的人或机构称为务的人或机构称为“服务台服务台”或或“服务服务员员”顾客的到达、服务的时间至少有一顾客的到达、服务的时间至少有一个是个是随机的随机的，服从某种分布。，服从某种分布。一般的排队系统，都可

6、由图一般的排队系统，都可由图12-112-1加以描述。加以描述。顾客源顾客源排队结构排队结构服务机构服务机构排队规则排队规则顾客到来顾客到来服务规则服务规则离去离去图图12-1排队系统排队系统 排队系统都有输入过程、排队规则和排队系统都有输入过程、排队规则和服务台等服务台等3个组成部分：个组成部分：1、输入过程输入过程 这是指要求服务的顾客是按怎这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把样的规律到达排队系统的过程，有时也把它称为顾客流一般可以从它称为顾客流一般可以从3个方面来描述个方面来描述输入过程。输入过程。排队系统的组成排队系统的组成(1)顾客总体数组成顾客总体数组成(

7、又称顾客源又称顾客源)是是有限有限的，的，也可以是也可以是无限无限的。例如，到售票处购票的顾的。例如，到售票处购票的顾客总数可以认为是无限的，而某个工厂因故客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。障待修的机床则是有限的。(2)顾客到达方式。描述顾客是怎样来到系统顾客到达方式。描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。顾客，那么这种顾客

8、则是成批到达的。(3)顾客流的概率分布，或称顾客相继到顾客流的概率分布，或称顾客相继到达时间间隔的分布。这是求解排队系统达时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的有关运行指标问题时，首先需要确定的指标。指标。顾客流的概率分布一般有定长分布、顾客流的概率分布一般有定长分布、二项分布、泊松流二项分布、泊松流(最简单流最简单流)、爱尔朗分、爱尔朗分布等若干种。布等若干种。2、排队规则排队规则 这是指服务台从队列中选取这是指服务台从队列中选取顾客进行服务的顺序。顾客进行服务的顺序。损失制损失制混合制混合制队长有限队长有限等待时间有限等待时间有限逗留时间有限逗留时间有限排队规则

9、排队规则等待制等待制先到先服务先到先服务后到先服务后到先服务随机服务随机服务优先权服务优先权服务3服务台情况服务台情况。服务台可以从。服务台可以从3方面来描述：方面来描述：(1)服务台数量及构成形式服务台数量及构成形式图图12-2 单队列单队列-单服务台排队系统单服务台排队系统图图12-3 单队列单队列S个服务台并联的排队系统个服务台并联的排队系统图图12-4 S个队列个队列S个服务台的并联排队系统个服务台的并联排队系统图图12-5 单队单队多个服务台的串联排队系统多个服务台的串联排队系统图图12-6 多队多队多服务台混联、网络系统多服务台混联、网络系统(2)服务方式服务方式。这是指在某一时刻

10、。这是指在某一时刻接受服务的顾客数，它有单个服务和接受服务的顾客数，它有单个服务和成批服务两种。成批服务两种。(3)服务时间的分布服务时间的分布。在多数情况。在多数情况下，对每一个顾客的服务时间是一随下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负机变量，其概率分布有定长分布、负指数分布、指数分布、K级爱尔朗分布、一般分级爱尔朗分布、一般分布布(所有顾客的服务时间都是独立同分所有顾客的服务时间都是独立同分布的布的)等等。等等。为了区别各种排队系统，根据输入过程、为了区别各种排队系统，根据输入过程、排队规则和服务机制的不同，对排队模型进排队规则和服务机制的不同，对排队模型进行分类

11、。行分类。DGKendall在在1953年提出了模年提出了模型分类方法，型分类方法，1971年在年在排队论符号标准化会排队论符号标准化会议议上，将上，将Kendall符号扩充为如下固定格式：符号扩充为如下固定格式：X/Y/Z/A/B/C各符号的意义为：各符号的意义为：（二）排队模型的分类（二）排队模型的分类X表示顾客相继到达间隔时间分布，常用下表示顾客相继到达间隔时间分布，常用下列符号：列符号：X/Y/Z/A/B/CM表示到达过程为泊松过程或负指数分布；表示到达过程为泊松过程或负指数分布；D表示定长输入；表示定长输入；Ek表示表示k阶爱尔朗分布；阶爱尔朗分布；GI表示一般相互独立的时间间隔分布

12、；表示一般相互独立的时间间隔分布；G表示一般服务时间的分布。表示一般服务时间的分布。Y表示服务时间分布，常用下列符号：表示服务时间分布，常用下列符号：X/Y/Z/A/B/CM表示服务过程为泊松过程或负指数分布；表示服务过程为泊松过程或负指数分布；D表示定长分布；表示定长分布；Ek表示表示k阶爱尔朗分布；阶爱尔朗分布；G表示一般相互独立的随机分布。表示一般相互独立的随机分布。Z表示服务台表示服务台(员员)个数：个数：“1”则表示单个服务台，则表示单个服务台，“s”(s1)表表示多个服务台。示多个服务台。X/Y/Z/A/B/CA表示系统中顾客容量限额，或称等待空表示系统中顾客容量限额，或称等待空间

13、容量：间容量：时为等待制系统，此时时为等待制系统，此时一般省略不一般省略不写；若为有限整数时，为混合制系统。写；若为有限整数时，为混合制系统。B表示顾客源限额。表示顾客源限额。分有限与无限两种，分有限与无限两种，表示顾客源无限，表示顾客源无限，此时一般此时一般也可省略不写。也可省略不写。X/Y/Z/A/B/CC表示服务规则，常用下列符号：表示服务规则，常用下列符号：FCFS：表示先到先服务；：表示先到先服务；LCFS：表示后到先服务；：表示后到先服务；PR：表示优先权服务。：表示优先权服务。例如：某排队问题为例如：某排队问题为 MMSFCFS则表示顾客到达间隔时间为负指数分则表示顾客到达间隔时

14、间为负指数分布布(泊松流泊松流)；服务时间为负指数分布；服务时间为负指数分布；有有s(s1)个服务台；个服务台；系统等待空间容量无限系统等待空间容量无限(等待制等待制)；顾客源无限，采用先到先服务规则。顾客源无限，采用先到先服务规则。可简记为：可简记为：M/M/s 某些情况下，排队问题仅用某些情况下，排队问题仅用上述表达形式中的前上述表达形式中的前3个、个、4个、个、5个符号。如不特别说明均理解为个符号。如不特别说明均理解为系统等待空间容量无限；顾客源系统等待空间容量无限；顾客源无限，先到先服务，单个服务的无限，先到先服务，单个服务的等待制系统等待制系统。（三）排队系统的主要数量指标（三）排队

15、系统的主要数量指标1.队长和排队长队长和排队长队长队长是指系统中的顾客数是指系统中的顾客数(排队等待的顾排队等待的顾 客数与正在接受服务的顾客数之和客数与正在接受服务的顾客数之和)。排队长排队长是指系统中正在排队等待服务的顾是指系统中正在排队等待服务的顾客数。客数。2等待时间和逗留时间等待时间和逗留时间 从顾客到达时刻起到他开始接受服务止从顾客到达时刻起到他开始接受服务止这段时间称为这段时间称为等待时间等待时间，是随机变量。，是随机变量。从顾客到达时刻起到他接受服务完成止从顾客到达时刻起到他接受服务完成止这段时间称为这段时间称为逗留时间逗留时间，也是随机变量。，也是随机变量。3忙期和闲期忙期和

16、闲期忙期忙期是指从顾客到达空闲着的服务机是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段构起，到服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间。这是个时间，即服务机构连续忙的时间。这是个随机变量，它关系到服务员的服务强度。随机变量，它关系到服务员的服务强度。与忙期相对的是与忙期相对的是闲期闲期，即服务机构连，即服务机构连续保持空闲的时间。在排队系统中，忙期续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。和闲期总是交替出现的。除了上述几个基本数量指标外，除了上述几个基本数量指标外，还会用到其他一些重要的指标：还会用到其他一些重要的指标：损失制或系统容量有限的情

17、况下，损失制或系统容量有限的情况下，由于顾客被拒绝，而使服务系统受到由于顾客被拒绝，而使服务系统受到损失的损失的顾客损失率顾客损失率及及服务强度服务强度等，也等，也都是十分重要的数量指标。都是十分重要的数量指标。4.一些数量指标的常用记号一些数量指标的常用记号 (1)主要数量指标主要数量指标 N(t)：时刻：时刻t系统中的顾客数系统中的顾客数(又称为系又称为系统的状态统的状态)，即队长；，即队长；Nq(t)：时刻：时刻t系统中排队的顾客数，即排系统中排队的顾客数，即排队长；队长；T(t)：时刻：时刻t到达系统的顾客在系统中的逗到达系统的顾客在系统中的逗留时间；留时间；Tq(t)：时刻：时刻t到

18、达系统的顾客在系统中的等到达系统的顾客在系统中的等待时间。待时间。上面数量指标一般都是和系统运行上面数量指标一般都是和系统运行的时间有关的随机变量，求它们的瞬时的时间有关的随机变量，求它们的瞬时分布一般很困难。注意到相当一部分排分布一般很困难。注意到相当一部分排队系统在运行了一定时间后，都会趋于队系统在运行了一定时间后，都会趋于一个平衡状态一个平衡状态(或称平稳状态或称平稳状态)。在平衡状态下，这些量与系统所处在平衡状态下，这些量与系统所处的时刻无关，而且系统的初始状态的影的时刻无关，而且系统的初始状态的影响也会消失。因此，我们响也会消失。因此，我们在本章中将主在本章中将主要讨论与系统所处时刻

19、无关的性质，即要讨论与系统所处时刻无关的性质，即统计平衡性质。统计平衡性质。L L或或L Ls s平均队长平均队长稳态系统任一时刻的顾客数的期望值；稳态系统任一时刻的顾客数的期望值；L Lq q平均等待队长或队列长平均等待队长或队列长稳态系统任一时刻等待服务的顾客数期望值；稳态系统任一时刻等待服务的顾客数期望值；W W或或W Ws s 平均逗留时间平均逗留时间 进入稳态系统的顾客逗留时间期望值；进入稳态系统的顾客逗留时间期望值；W Wq q平均等待时间平均等待时间 进入稳态系统的顾客等待时间期望值。进入稳态系统的顾客等待时间期望值。P Pn n 系统的状态系统的状态P Pn n=P P N N

20、=n n：稳态系统任一时刻状态为：稳态系统任一时刻状态为n n的概率。的概率。当当 n=0 时，时，Pn即即P0为稳态系统所有服务台全部空闲的概率。为稳态系统所有服务台全部空闲的概率。(2)其他常用数量指标其他常用数量指标s系统中并联服务台的数目系统中并联服务台的数目平均到达率平均到达率（单位时间内到达的（单位时间内到达的平均顾客数）平均顾客数）1/平均到达间隔平均到达间隔 平均服务率（平均服务率（单位时间内可以服单位时间内可以服务完的平均顾客数）务完的平均顾客数）1/平均服务时间平均服务时间 对于损失制和混合制的排队系统，对于损失制和混合制的排队系统，顾客在到达服务系统时，若系统容量已顾客在

21、到达服务系统时，若系统容量已满，则自行消失。这就是说，到达的顾满，则自行消失。这就是说，到达的顾客不一定全部进入系统，为此引入：客不一定全部进入系统，为此引入：e 有效平均到达率有效平均到达率，即每单位时间，即每单位时间实际进入系统的平均顾客数（期望值），实际进入系统的平均顾客数（期望值），不同于不同于 。对于等待制的排队系统，有：对于等待制的排队系统，有：e 第二节第二节 到达间隔的分布和服务时间的分布到达间隔的分布和服务时间的分布 一、一、Poisson流流（Poisson过程过程）定义定义 满足以下三个条件的输入流称为满足以下三个条件的输入流称为PoissonPoisson流流1 1、无

22、后效性无后效性：不相交的时间区间内到达的顾客数互：不相交的时间区间内到达的顾客数互相独立。相独立。2 2、平稳性平稳性：在时间区间在时间区间t,t+t,t+t)t)内到达内到达1 1个顾客个顾客的概率只与的概率只与 t t有关。即有关。即 表示单位时间内有一个顾客到达的概率。表示单位时间内有一个顾客到达的概率。3 3、普通性普通性：设在设在t,t+t,t+t t）内到达多于一个顾客）内到达多于一个顾客的概率极小，即的概率极小，即2(,)()nnpt ttot 1(,)()p t tttot Poisson流与流与Poisson分布分布定理定理1 对于一个参数为对于一个参数为 的的Poisson

23、流，在流，在0，t内到达内到达n个顾客的概率为个顾客的概率为即服从以即服从以 为参数的为参数的Poisson分布。分布。()()0,1,20!ntntP tenn定理定理1说明说明 如果顾客的到达为如果顾客的到达为Poisson流的话，则流的话，则到达顾客数的分布恰好为到达顾客数的分布恰好为Poisson分布。分布。二、负指数分布二、负指数分布 在实际的排队系统中服务时间的概率分布可以是在实际的排队系统中服务时间的概率分布可以是各种形式，但在排队论中，最容易进行数学处理、最各种形式，但在排队论中，最容易进行数学处理、最常用的一种重要分布是负指数分布。常用的一种重要分布是负指数分布。设随机变量设

24、随机变量T服从以服从以 为参数的负指数分布，它为参数的负指数分布，它的分布函数为：的分布函数为：1,0()0,0tetP Ttt()1/E t方差：2()1/V ar t期望：负指数分布的性质：负指数分布的性质：性质性质1 1 由条件概率公式容易证明由条件概率公式容易证明 性质性质2 2 当单位时间内的顾客到达数服从以当单位时间内的顾客到达数服从以 为平均数为平均数的泊松分布时，则顾客相继到达的间隔时间的泊松分布时，则顾客相继到达的间隔时间T T服从负服从负指数分布。指数分布。这性质称为这性质称为无记忆性无记忆性。若。若T T表示排队系统中顾客到达的表示排队系统中顾客到达的时间间隔，那么这个性

25、质说明一个顾客到来所需要的时间间隔，那么这个性质说明一个顾客到来所需要的时间与过去一个顾客到来所需要的时间时间与过去一个顾客到来所需要的时间s s无关，所以说无关，所以说在这种情形下的顾客到达是纯随机的。在这种情形下的顾客到达是纯随机的。|p Tts Tsp Tt由性质由性质2 2可知：可知：相继到达的间隔时间是独立且为相同相继到达的间隔时间是独立且为相同参数的负指数分布，与输入过程为泊松流（参数为参数的负指数分布，与输入过程为泊松流（参数为 ）是等价的。是等价的。根据负指数分布与泊松流的关系可以推导出，当根据负指数分布与泊松流的关系可以推导出，当服务机构对顾客的服务时间服从参数为服务机构对顾

26、客的服务时间服从参数为 的负指数分的负指数分布，如果服务机构处于忙期，则该服务机构的输出，布，如果服务机构处于忙期，则该服务机构的输出，即服务完毕离开服务机构的顾客数将是服从泊松分布即服务完毕离开服务机构的顾客数将是服从泊松分布的泊松流。其中的泊松流。其中 为每个顾客的平均服务时间，也是为每个顾客的平均服务时间，也是顾客相继离开的间隔顾客相继离开的间隔。三、三、k阶爱尔朗分布阶爱尔朗分布定理定理 设设v1，v2，vk是是k个互相独立的随机变量，个互相独立的随机变量，服从相同参数服从相同参数k 的负指数分布，那么的负指数分布，那么S=v1+v2+vk服从服从k阶阶Erlang分布，分布，S的密度

27、函数为的密度函数为1()()0(1)!kttb tetk()1/E t方差：2()1/V ar tk 期望：K K=1=1时爱尔朗分布化归为负指数分布，当时爱尔朗分布化归为负指数分布，当K K时，得到长度为时，得到长度为1/1/的定长服务。的定长服务。m=1k=1k=2k=4k=8第三节第三节 单服务台负指数分布排队系统的分析单服务台负指数分布排队系统的分析标准排队模型标准排队模型 M/M/1:/FCFS顾客到达的时间间隔是负指数分布，顾客到达的时间间隔是负指数分布，即输入流是参数为即输入流是参数为 的的Poisson流流服从参数为服从参数为的负指数分布的负指数分布一个服务台一个服务台排队系统

28、的容量无限排队系统的容量无限顾客源的容量无限顾客源的容量无限实行先到先服务的一个服务系统实行先到先服务的一个服务系统一、系统稳态概率一、系统稳态概率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时刻时刻无到达，无离开无到达，无离开无到达，离开一个无到达，离开一个到达一个，无离开到达一个，无离开到达一个，离开一个到达一个，离开一个)1()1(tt)1(tt(1)tttt由于这四种方式互不相容，故由概率的加法定理得：

29、由于这四种方式互不相容，故由概率的加法定理得：11()()(1)()(1)()(1)()nnnnPttPtttPtttPtttot ttotPtPtPttPttPnnnnn)()()()()()(11得：令0t1n )()()()(0n )()()(11100tPtPtPdttdPtPtPdttdPnnnn该差分方程组为该差分方程组为瞬态解瞬态解，需求稳态解。，需求稳态解。M/M/1:/FCFS稳态时状态转移图稳态时状态转移图012n-1nn+10P1nP1nP2P1PnP 1n110n10 )(nnnPPPPP稳态情况下，系统状态已不随时间发生变化：稳态情况下，系统状态已不随时间发生变化：(

30、)0tdtndP稳态情况下，系统状态已不随时间发生变化：稳态情况下，系统状态已不随时间发生变化：()0tdtndP 0021201PPPPPPPPnnn 01nnP1102 Pn 得到得到 令令称称 为服务强度，则为服务强度，则 1 01001 nnP 210 )1(,nnnP 得得系统的过渡状态与稳定状态系统的过渡状态与稳定状态过渡过渡稳定稳定二、二、系统的数量指标系统的数量指标1 1、服务台空闲的概率和忙的概率：、服务台空闲的概率和忙的概率：空闲的概率：空闲的概率：P P0 0=1-=1-忙的概率：忙的概率：1-P0 0=2 2、系统中平均顾客数（队长期望值、系统中平均顾客数（队长期望值L

31、sLs）：）：0002(1)(1)(1)1(1)nnsnnnnLnPnn3 3、系统中等待的平均顾客数（队长期望值、系统中等待的平均顾客数（队长期望值LqLq）：）：111222(1)(1)(1)(1)(1)(1)1(1)nnqnnnnLnPnn4 4、系统中顾客逗留时间的期望值：、系统中顾客逗留时间的期望值：1ssLW5 5、队列中顾客逗留时间的期望值：、队列中顾客逗留时间的期望值：1qqsLWW现将以上公式归纳如下：现将以上公式归纳如下：1sWqWqLsLssLwqqLw1sqWWssLL它们相互关系如下：它们相互关系如下：Little公式公式下列公式对任何服务系统均成立下列公式对任何服务

32、系统均成立eqqessLWLW ,eqsqsLLWW ,1例例1 高速公路入口收费处设有一个收费高速公路入口收费处设有一个收费通道，汽车到达服从通道，汽车到达服从Poisson分布，平分布，平均到达速率为均到达速率为100辆小时，收费时间辆小时，收费时间服从负指数分布，平均收费时间为服从负指数分布，平均收费时间为15秒辆。求秒辆。求1、收费处空闲的概率；、收费处空闲的概率；2、收费处忙的概率；、收费处忙的概率；3、系统中分别有、系统中分别有1，2，3辆车的概率。辆车的概率。解：根据题意解：根据题意,=100辆辆/小时小时,1/=15（秒（秒/辆）辆）=1/240（小时（小时/辆）辆）,即即 2

33、40（辆（辆/小时）。小时）。因此，因此，=/=100/240=5/12。系统空闲的概率为：系统空闲的概率为：P0=1-=1-(5/12)=7/12=0.583系统忙的概率为：系统忙的概率为：1-P0=1-(1-)=5/12=0.417系统中有系统中有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例例2 高速公路入口收费处设有一个高速公路入口收费处设有一个收费通道

34、，汽车到达服从收费通道，汽车到达服从Poisson分布，平均到达速率为分布，平均到达速率为200辆小辆小时，收费时间服从负指数分布，时，收费时间服从负指数分布，平均收费时间为平均收费时间为15秒辆。求秒辆。求Ls、Lq、Ws和和Wq。解：根据题意，解：根据题意，=200辆辆/小时，小时，=240辆辆/小时，小时，=/=5/6。)(7590)(90)(025.02002401117.4551165656565秒秒秒秒小小时时 sqssqsWWWLLL 有限队列模型有限队列模型 M/M/1:N/FCFS 顾客到达进入队列顾客接受服务后离去.服务台.因队列满而离去 如果系统的最大容量为如果系统的最大

35、容量为N时，排队等待的顾客最多时，排队等待的顾客最多为为N-1，在某时刻一顾客到达时，如系统中已有，在某时刻一顾客到达时，如系统中已有N个个顾客，那么这个顾客就被拒绝进入系统。顾客，那么这个顾客就被拒绝进入系统。系统的状态概率平衡方程系统的状态概率平衡方程对于状态对于状态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

36、.39（分钟）（分钟）1010（分钟）（分钟）平均等待时间平均等待时间1.891.89（分钟）（分钟）7.57.5（分钟）（分钟）M/M/c:N/FCFS模型模型 离开离开服务台服务台服务台服务台服务台服务台顾客到达顾客到达顾客离去顾客离去顾客离去顾客离去顾客离去顾客离去队列队列设系统容量为设系统容量为N(Nc)。设顾客到达的速率为。设顾客到达的速率为，每个服务台服务的速率为每个服务台服务的速率为，=/c。由于系统不会无。由于系统不会无限止地接纳顾客，对限止地接纳顾客，对不必加以限制。不必加以限制。状态转移图与状态转移方程状态转移图与状态转移方程对状态对状态0:P0=P1对状态对状态1:P0+

37、2P2=(+)P1对状态对状态c：Pc-1+cPc+1=(+c)Pc对状态对状态N PN-1=cPN 01cc2Ncc状态概率状态概率11NnnP11)(!)(100 ckNcckcckcP )(!)0(!)(00NncPcccnPncPncnn 运行指标运行指标 )1(NsessPLLW 02)1()(1)1(!)(PccNccLNcNcq )1(NqsPcLL )1(NqeqqPLLW 例例6 某旅馆有某旅馆有8个单人房间，旅客到达服个单人房间，旅客到达服从从Poisson流，平均速率为流，平均速率为6人天，旅人天，旅客平均逗留时间为客平均逗留时间为2天，求：天，求：(1)每天客房平均占用

38、数；每天客房平均占用数；(2)旅馆客满的概率。旅馆客满的概率。解：解：12,2,6,85.061 ccN51876543210010963.3!8)12(!7)12(!6)12(!5)12(!4)12(!3)12(!2)12(!1)12(!0)12(P423.010963.3!8)12(!)(5808 PncPn 旅馆旅馆8个房间全满的概率为个房间全满的概率为0.423 924.6)423.01(12)1(csPcL 平均占用客房数为平均占用客房数为6.9间。间。M/M/c:/m/FCFS模型模型 顾客到达顾客到达修理速率修理速率发生故障等待修理的机器发生故障等待修理的机器修理速率修理速率修理

39、速率修理速率正在修理的机器正在修理的机器到达速率到达速率 (m-n)(m-n)修理速率修理速率cc运行的机器数运行的机器数 m-nm-n状态概率状态概率 ckmckkckmkmccmckmkmP010)!(1!)!(!11!1 其中其中 cm mncPccnmmcnPnnmmPncnnn1!)!(!0!)!(!00 运行指标运行指标 mnnsnPL1 mcnnqPcnL1)(有效到达速率有效到达速率e为单位时间内出现故为单位时间内出现故障的机器数，有障的机器数，有e=(m-Ls)例例7 7 车间有车间有5 5台机器，每台机器的故障率为台机器，每台机器的故障率为1 1次小时，有次小时，有2 2个

40、修理工负责修理这个修理工负责修理这5 5台机台机器，工作效率相同，为器，工作效率相同，为4 4台小时。求：台小时。求：(1)(1)等待修理的平均机器数；等待修理的平均机器数；(2)(2)正在修理的平均机器数；正在修理的平均机器数；(3)(3)每小时发生故障的平均机器数；每小时发生故障的平均机器数；(4)(4)平均等待修理的时间；平均等待修理的时间；(5)(5)平均停工时间。平均停工时间。解解 81,41,2,4,1,5 mmccmcm 3149.081!01!2281!11!2281!21!2241!3!2141!4!1141!5!01!51)!(1!)!(!11!11524232210010

41、 ckmckkckmkmccmckmkmP 可以计算得到（算式略）：可以计算得到（算式略）：P1=0.394，P2=0.197，P3=0.074，P4=0.018，P5=0.002 由此，计算系统的各项运行指标如下：由此，计算系统的各项运行指标如下：118.032)()1(5431 PPPPcnLmcnnq092.15432)2(543211 PPPPPnPLmnns908.3)092.15(1)()3(seLm )(8.1)(03.0908.3118.0)4(分分小时小时 eqqLW)(8.16)(28.0908.3902.1)5(分分小时小时 essLW 第第5 5节节 一般服务时间一般服

42、务时间M/G/1M/G/1模型模型服务时间一般分布时，需要知道服务时服务时间一般分布时，需要知道服务时间的均值间的均值 和方差和方差 。当。当 时，排队系时，排队系统可以达到平稳状态。统可以达到平稳状态。121 1,)1(2,12220 qsqqqqsWWLWLLLpPK公式公式1 1 负指数服务时间负指数服务时间M/M/1M/M/1模型模型221 1)1(2)1(2222222qL)1(22 qL只有负指数分布时排队长的一半。只有负指数分布时排队长的一半。02 2 定长服务时间定长服务时间M/D/1模型模型3 k阶爱尔朗服务时间阶爱尔朗服务时间M/Ek/1模型模型若顾客需接受若顾客需接受k个

43、串行的服务台个串行的服务台的服务后才离开，且每个服务台服的服务后才离开，且每个服务台服务时间服从负指数分布，平均服务务时间服从负指数分布，平均服务时间相等。时间相等。则总服务时间服从则总服务时间服从k阶爱尔朗分阶爱尔朗分布。布。ErlangErlang分布的均值和方差分布的均值和方差总服务时间服从爱尔朗分布：总服务时间服从爱尔朗分布：21)(,1)(kTVarTE k1每个服务台的平均服务时间是：每个服务台的平均服务时间是：M/EM/Ek k/1/1系统的运行指标系统的运行指标2(1)2(1)qsqssqqkLkLLLWLW例例8 有一汽车冲洗台，汽车按有一汽车冲洗台，汽车按Poisson流流

44、到达，平均每小时到达到达，平均每小时到达18辆；冲洗时间辆；冲洗时间T的平均值的平均值=0.05小时小时/辆，方差辆，方差Var(T)=0.01(小时小时/辆辆)2，求该洗车台的运行指，求该洗车台的运行指标，并对它进行评价。标，并对它进行评价。24.301.018,01.02005.0,19.005.018,1822221 解：解：本例是本例是M/G/1系统，且已知系统，且已知)(125.105.0175.1(175.11815.21)(15.219.025.20)(25.20)9.01(29.024.3)1(22222小小时时小小时时）辆辆辆辆 qssqsqWLWLLL 可见顾客等待时间太长

45、，队列也太长。主可见顾客等待时间太长，队列也太长。主要原因是服务时间的方差太大！要原因是服务时间的方差太大！例例9 某单人裁缝店做西服，每套需经过某单人裁缝店做西服，每套需经过4个个不同的工序，不同的工序，4个工序完成后才开始做另一个工序完成后才开始做另一套。每一工序的时间服从负指数分布，期套。每一工序的时间服从负指数分布，期望值为望值为2小时。顾客到来服从泊松分布，平小时。顾客到来服从泊松分布，平均订货率为均订货率为5.5套套/周（设一周周（设一周6天，每天天，每天8小小时）。问一顾客为等到做好一套西服期望时）。问一顾客为等到做好一套西服期望时间有多长？时间有多长？解：解：=5.5套套/周周

46、1/:平均每套所需时间平均每套所需时间1/4:平均每工序所需时间，为平均每工序所需时间，为2小时小时1/8套套/小时小时6套套/周周2115.5(),()64 6E TVar T，2188.765.5126415.565.565.5222 sL顾客为等到做好一套西服期望时间：顾客为等到做好一套西服期望时间：周周3.15.52188.7 ssLW某修理店只有一位修理工，来修理某修理店只有一位修理工，来修理的顾客到达过程为的顾客到达过程为Poisson流，平均每小时流，平均每小时4人；修理时间服从负指数分布，平均需要人；修理时间服从负指数分布，平均需要6分钟。试求：修理店空闲的概率；店内恰有分钟。

47、试求：修理店空闲的概率；店内恰有3位顾客的概率；店内至少有一位顾客的概位顾客的概率；店内至少有一位顾客的概率；在店内平均顾客数；每位在店内平均逗率；在店内平均顾客数；每位在店内平均逗留时间；等待服务的平均顾客数；每位顾客留时间；等待服务的平均顾客数；每位顾客平均等待服务时间；顾客在店内逗留时间超平均等待服务时间；顾客在店内逗留时间超过过10分钟的概率。分钟的概率。解：解：本例可看成一个本例可看成一个M/M/1/M/M/1/排队问题，其中排队问题，其中=2=2，=3=3，=/=2/31=2/31 1 1、系统中列车的平均数、系统中列车的平均数 L=L=/(1-/(1-)=(2/3)/(1-2/3

48、)=2)=(2/3)/(1-2/3)=2（列）（列）2 2、列车在系统中的平均停留时间、列车在系统中的平均停留时间 W=L/W=L/=2/2=12/2=1（小时）（小时）3 3、系统中等待编组的列车平均数、系统中等待编组的列车平均数 Lq=L-Lq=L-=2-2/3=4/3=2-2/3=4/3（列）（列）4 4、列车在系统中的平均等待编组时间、列车在系统中的平均等待编组时间 WqWq=Lq/Lq/=(4/3)/(1/2)=2/3=(4/3)/(1/2)=2/3（小时）（小时）练习练习3 3：(病人候诊问题病人候诊问题)某单位医院的一个某单位医院的一个科室有一位医生值班，经长期观察，每小平均科室

49、有一位医生值班，经长期观察，每小平均有有4 4个病人，医生每小时平均可诊个病人，医生每小时平均可诊5 5个病人，病个病人，病人的到来服从泊松分布，医生的诊病时间服从人的到来服从泊松分布，医生的诊病时间服从负指数分布，试问：负指数分布，试问：1 1、该科室平均有病人数；平均排队候诊病人数；看、该科室平均有病人数；平均排队候诊病人数；看一次病平均所需的时间；排队等候看病的平均时间一次病平均所需的时间；排队等候看病的平均时间 2 2 如果满足如果满足99%99%以上的病人有座，此科室至少应设多以上的病人有座，此科室至少应设多少座位少座位?3 3 如果该单位每天如果该单位每天2424小时上班，病人看病

50、小时上班，病人看病1 1小时因耽小时因耽误工作单位要损失误工作单位要损失3030元，这样单位平均每天损失多元，这样单位平均每天损失多少元少元?4 4 如果该科室提高看病速度，每小时平均可诊如果该科室提高看病速度，每小时平均可诊6 6个病个病人，单位每天可减少损失多少人，单位每天可减少损失多少?可减少多少座位可减少多少座位?4545081,.pnnn0208012.,解：该模型为解：该模型为MM1MM1该科室平均有病人数为该科室平均有病人数为 该科室内排队候诊病人数为该科室内排队候诊病人数为 看一次病平均所需的时间为看一次病平均所需的时间为 排队等候看病的平均时间为排队等候看病的平均时间为 为满

51、足为满足99%99%以上的病人有座，设科室应设以上的病人有座，设科室应设m m个座位，个座位，则则m m应满足应满足 Ls1081084.()人LLqs40832.()人WLss441()小时WWqs111508.()小时Pm.医务室病人数 099nmnm().1109910m1001.m ln.ln0 01120 所以该科室至少应设所以该科室至少应设2020个座位个座位 如果该单位如果该单位2424小时上班，则每天平均有病人小时上班，则每天平均有病人24244=964=96人，病人看病所花去的总时间为人，病人看病所花去的总时间为96961=961=96小时，因看病平均每天损失小时，因看病平均

52、每天损失303096=288096=2880元，如果医元，如果医生每小时可诊生每小时可诊6 6个病人，个病人，则，则 23LLWWsqsq2430513()().()()人人小时小时 这样单位每天的损失费为这样单位每天的损失费为96960.50.530=144030=1440元，元，因而单位每天平均可减少损失因而单位每天平均可减少损失2880-1440=14402880-1440=1440元，元，这时为保证这时为保证99%99%以上的病人有座，应设座位数个以上的病人有座，应设座位数个比原来减少了比原来减少了9 9个。个。练习练习4 4:某汽车加油站有两台加油泵为汽车某汽车加油站有两台加油泵为汽

53、车加油，加油站内最多能容纳加油，加油站内最多能容纳6 6辆汽车。已知辆汽车。已知顾客到达的时间间隔服从负指数分布，平顾客到达的时间间隔服从负指数分布，平均每小时到达均每小时到达1818辆汽车。若加油站中已有辆汽车。若加油站中已有K K辆车，当辆车，当K K 2 2时，有时，有K K/6/6的顾客将自动离去。的顾客将自动离去。加油时间服从负指数分布，平均每辆车需加油时间服从负指数分布，平均每辆车需要要5 5分钟。试求：分钟。试求：非标准的非标准的M/M/2/NM/M/2/N模型模型（1 1）系统空闲的概率为多少？）系统空闲的概率为多少？（2 2）求系统满的概率是多少？）求系统满的概率是多少？（3

54、 3）求系统服务台不空的概率）求系统服务台不空的概率?（4 4）若服务一个顾客）若服务一个顾客,加油站可以获得利润加油站可以获得利润1010元元,问平均每小时可获得利润为多少元？问平均每小时可获得利润为多少元？（5 5）求每小时损失掉的顾客数？）求每小时损失掉的顾客数？（6 6）加油站平均有多少辆车在等待加油？平均）加油站平均有多少辆车在等待加油？平均有多少个车位被占用？有多少个车位被占用？（7 7）进入加油站的顾客需要等多长的时间才能）进入加油站的顾客需要等多长的时间才能开始加油？开始加油？进入加油站的顾进入加油站的顾 客需要多长时间才客需要多长时间才能离去？能离去？（1 1）系统空闲的概率

55、为多少？）系统空闲的概率为多少？P P0 0（2 2）求系统满的概率是多少？）求系统满的概率是多少？P P6 6（3 3）求系统服务台不空的概率）求系统服务台不空的概率 P P2 2+P+P3 3+P+P4 4+P+P5 5+P+P6 6=1-P=1-P0 0-P-P1 1 （4 4）若服务一个顾客）若服务一个顾客,加油站可以获得利润加油站可以获得利润1010元元,问平问平均每小时可获得利润为多少元？均每小时可获得利润为多少元？1010e e（5 5）求每小时损失掉的顾客数？）求每小时损失掉的顾客数？损损=-=-e e （6 6）加油站平均有多少辆车在等待加油？）加油站平均有多少辆车在等待加油

56、？L Lq q 平均有多少个车位被占用？平均有多少个车位被占用？L L（7 7）进入加油站的顾客需要等多长时间才能开始加油？）进入加油站的顾客需要等多长时间才能开始加油？W Wq q 进入加油站的顾客需要多长时间才能离去？进入加油站的顾客需要多长时间才能离去？W W 稳态概率关系：稳态概率关系：P P1 1=/PP0 0=1.5=1.5P P0 0=(3/2)=(3/2)P P0 0P P2 2=/(2/(2)P P1 1=0.75=0.75*1.51.5P P0 0=(9/8)=(9/8)P P0 0解：状态转移速度图解：状态转移速度图 以小时为单位以小时为单位=18 =18 =60/5=1

57、2=60/5=1222 2205124632(1-2/6)(1-3/6)(1-4/6)(1-5/6)P P3 3=(4/6)=(4/6)/(2/(2)P P2 2=(1/2)(9/8)=(1/2)(9/8)P P0 0=(9/16)=(9/16)P P P P4 4=(3/6)=(3/6)/(2/(2)P P3 3=(3/8)(9/16)=(3/8)(9/16)P P0 0=(27/128)=(27/128)P P0 0P P5 5=(2/6)=(2/6)/(2/(2)P P4 4=(1/4)(27/128)=(1/4)(27/128)P P0 0=(27/512)=(27/512)P P0

58、0P P6 6=(1/6)=(1/6)/(2/(2)P P5 5=(1/8)(27/512)=(1/8)(27/512)P P0 0=(27/4096)=(27/4096)P P0 0由由 P P0 0+P+P1 1+P P2 2+P P3 3+P P4 4+P P5 5+P P6 6=1=1解得：解得：P P0 0=0.22433=0.22433 P P1 1 P P2 2 P P3 3 P P4 4 P P5 5 P P6 60.33649 0.25237 0.12618 0.04732 0.01183 0.001480.33649 0.25237 0.12618 0.04732 0.01

59、183 0.00148运行指标：运行指标：(1)(1)P P0 0=0.22433=0.22433(2)(2)P P6 6=0.00148=0.00148(3)(3)P P忙忙=1-=1-P P0 0-P P1 1=0.43918=0.43918(4)(4)e e=0=0P P0 0+PP1 1+2+2(P P2 2+P P3 3+P P4 4+P P5 5+P P6 6)=14.578 =14.578（辆（辆/h/h）1010e e=145.78(=145.78(元元/小时）小时）(5)(5)损损=-e e =18-14.5782 =18-14.5782 =3.4218 =3.4218（辆（

60、辆/h/h）(6)(6)L Lq q=(3-2)=(3-2)P P3 3+(4-2)+(4-2)P P4 4+(5-2)+(5-2)P P5 5+(6-2)+(6-2)P P6 6 =0.26223 =0.26223 L L=L Lq q+e e/=0.26223+1.21485 =0.26223+1.21485 =1.47708 =1.47708(7)(7)W Wq q=L Lq q/e e=0.018h=1.08=0.018h=1.08分钟分钟 W W=W Wq q+1/+1/=0.101h=6.08=0.101h=6.08分钟分钟P342 12.2P342 12.2 12.11 12.11 12.12 12.12 12.17 12.17