第十章排队论课件.ppt

《第十章排队论课件.ppt》由会员分享，可在线阅读，更多相关《第十章排队论课件.ppt（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十章第十章 排队论排队论（1）排队服务系统的基本概念排队服务系统的基本概念（2）输入与服务时间的分布输入与服务时间的分布（3）最简单的排队模型最简单的排队模型本章主要内容：本章主要内容：排队论排队论是研究排队系统（又称随机服务系是研究排队系统（又称随机服务系统）的数学理论和方法，是运筹学的一个重统）的数学理论和方法，是运筹学的一个重要分支。要分支。有形有形排队现象：排队现象：进餐馆就餐，到图书馆借进餐馆就餐，到图书馆借书，车站等车，去医院看病，售票处售票，书，车站等车，去医院看病，售票处售票，到工具房领物品等现象。到工具房领物品等现象。第一节第一节 排队排队服务系统的基本概念服务系统的基本概

2、念 无形排队现象：无形排队现象：如几个旅客同时打电如几个旅客同时打电话订车票；如果有一人正在通话，其他人话订车票；如果有一人正在通话，其他人只得在各自的电话机前等待，他们分散在只得在各自的电话机前等待，他们分散在不同的地方，形成一个无形的队列在等待不同的地方，形成一个无形的队列在等待通电话。通电话。排队的不一定是人，也可以是物。如排队的不一定是人，也可以是物。如生产线上的原材料，半成品等待加工；因生产线上的原材料，半成品等待加工；因故障而停止运行的机器设备在等待修理；故障而停止运行的机器设备在等待修理；码头上的船只等待装货或卸货；要下降的码头上的船只等待装货或卸货；要下降的飞机因跑道不空而在空

3、中盘旋等。飞机因跑道不空而在空中盘旋等。当然，进行服务的也不一定是人，可以当然，进行服务的也不一定是人，可以是跑道，自动售货机，公共汽车等。是跑道，自动售货机，公共汽车等。顾客顾客要求服务的对象。要求服务的对象。服务员服务员提供服务的服务者（也称服提供服务的服务者（也称服务机构）。务机构）。顾客、服务员的含义是广义的。顾客、服务员的含义是广义的。随机性随机性顾客到达情况与顾客接顾客到达情况与顾客接受服务的时间是随机的。受服务的时间是随机的。一般来说，排队论所研究的排队系一般来说，排队论所研究的排队系统中，顾客相继到达时间间隔和服务时统中，顾客相继到达时间间隔和服务时间这两个量中至少有一个是随机

4、的，因间这两个量中至少有一个是随机的，因此，排队论又称此，排队论又称随机服务理论。随机服务理论。随机服务理论随机服务理论研究如何合理的设置服务研究如何合理的设置服务系统，更好的为顾客服务，减少排队时间，系统，更好的为顾客服务，减少排队时间，同时又要使得费用尽可能节省。同时又要使得费用尽可能节省。排队系统类型排队系统类型1：服务台服务台顾客到达顾客到达顾客到达顾客到达服务完成后离开服务完成后离开服务完成后离开服务完成后离开单服务台排队系统单服务台排队系统排队系统类型排队系统类型2：服务台服务台2 2顾客到达顾客到达顾客到达顾客到达服务完成后离开服务完成后离开服务完成后离开服务完成后离开S S个服

5、务台，一个队列的排队系统个服务台，一个队列的排队系统服务台服务台s s服务台服务台1 12023/1/48排队系统类型排队系统类型3：服务台服务台2顾客到达顾客到达顾客到达顾客到达服务完成后离开服务完成后离开服务完成后离开服务完成后离开S S个服务台，个服务台，S S个队列的排队系统个队列的排队系统服务台服务台s服务台服务台1服务完成后离开服务完成后离开服务完成后离开服务完成后离开服务完成后离开服务完成后离开服务完成后离开服务完成后离开2023/1/49排队系统类型排队系统类型4：服务台服务台服务台服务台1 1顾客到达顾客到达顾客到达顾客到达离开离开离开离开多服务台串联排队系统多服务台串联排队

6、系统服务台服务台服务台服务台s s s s2023/1/410 排队系统的描述排队系统的描述 实际实际中的排队系统各不相同，但概括中的排队系统各不相同，但概括起来都由三个基本部分组成：起来都由三个基本部分组成：1 1、输入过程、输入过程;2 2、排队及排队规则、排队及排队规则;3 3、服务机构、服务机构2023/1/411 河流河流河流河流上游流入水库的水量可认为是无限的；车上游流入水库的水量可认为是无限的；车上游流入水库的水量可认为是无限的；车上游流入水库的水量可认为是无限的；车间内停机待修的机器显然是有限的。间内停机待修的机器显然是有限的。间内停机待修的机器显然是有限的。间内停机待修的机器

7、显然是有限的。到达方式：到达方式：是单个到达还是成批到达。是单个到达还是成批到达。库存问题中，若把进来的货看成顾客，则为成批到库存问题中，若把进来的货看成顾客，则为成批到库存问题中，若把进来的货看成顾客，则为成批到库存问题中，若把进来的货看成顾客，则为成批到达的例子。达的例子。达的例子。达的例子。v1、输入过程、输入过程顾客总体（顾客源）数顾客总体（顾客源）数：可能是有限，：可能是有限，也可能是无限。也可能是无限。2023/1/412顾客（单个或成批）相继到达的时顾客（单个或成批）相继到达的时间间隔分布间间隔分布：这是刻划输入过程的最：这是刻划输入过程的最重要内容。重要内容。令令T T0 0=

8、0=0，T Tn n表示第表示第n n顾客到达的时刻，顾客到达的时刻，则有则有T T0 0 T T1 1 T T2 2.T Tn n 记记X Xn n=T Tn n T Tn-1 n-1 n=1,2,n=1,2,则则X Xn n是第是第n n顾客与第顾客与第n-1n-1顾客到达的时间间隔。顾客到达的时间间隔。一般假定一般假定XXn n 是独立同分布，并记是独立同分布，并记分布函数为分布函数为A(t)A(t)。2023/1/413XXn n 的分布的分布A(t)A(t)常见的有：常见的有：定长分布定长分布（D D）：顾客相继到达的时）：顾客相继到达的时间间隔为确定的。间间隔为确定的。如产品通过传

9、送带进入包装箱就是定常分布。如产品通过传送带进入包装箱就是定常分布。如产品通过传送带进入包装箱就是定常分布。如产品通过传送带进入包装箱就是定常分布。最简单流（或称最简单流（或称Poisson)Poisson)（M M）：顾）：顾客相继到达的时间间隔客相继到达的时间间隔XXn n 为独立的，同为独立的，同为负指数分布，其密度函数为：为负指数分布，其密度函数为：f(t)=e-t t 0 0 t 02023/1/414v2、排队及排队规则、排队及排队规则排队排队有限排队有限排队排队系统中顾客数是有限排队系统中顾客数是有限的。（的。（损失制排队系统，混合制排队系统损失制排队系统，混合制排队系统损失制排

10、队系统，混合制排队系统损失制排队系统，混合制排队系统）无限排队无限排队顾客数是无限，队列可以顾客数是无限，队列可以排到无限长（等待制排队系统）。排到无限长（等待制排队系统）。2023/1/415有限排队有限排队还可以分成：还可以分成：损失制排队系统损失制排队系统：排队空间为零的系：排队空间为零的系统，即不允许排队。（顾客到达时，统，即不允许排队。（顾客到达时，服务台占满，顾客自动离开，不再回服务台占满，顾客自动离开，不再回来）（电话系统）来）（电话系统）混合制排队系统混合制排队系统：是等待制与损失制：是等待制与损失制结合，即允许排队，但不允许队列无结合，即允许排队，但不允许队列无限长。限长。2

11、023/1/416混合制排队系统：混合制排队系统：1.1.队长有限队长有限,即系统等待空间是有限的。即系统等待空间是有限的。例：最多只能容纳例：最多只能容纳例：最多只能容纳例：最多只能容纳K K K K个顾客在系统中，当新顾客到达个顾客在系统中，当新顾客到达个顾客在系统中，当新顾客到达个顾客在系统中，当新顾客到达时，若系统中的顾客数（又称为队长）小于时，若系统中的顾客数（又称为队长）小于时，若系统中的顾客数（又称为队长）小于时，若系统中的顾客数（又称为队长）小于K K K K，则，则，则，则可进入系统排队或接受服务；否则，便离开系统，可进入系统排队或接受服务；否则，便离开系统，可进入系统排队或

12、接受服务；否则，便离开系统，可进入系统排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床并不再回来。如水库的库容是有限的，旅馆的床并不再回来。如水库的库容是有限的，旅馆的床并不再回来。如水库的库容是有限的，旅馆的床位是有限的位是有限的位是有限的位是有限的。2023/1/4172.2.等待时间有限。即顾客在系统中等待时等待时间有限。即顾客在系统中等待时间不超过某一给定的长度间不超过某一给定的长度T T，当等待时间，当等待时间超过超过T T时，顾客将自动离开，不再回来。时，顾客将自动离开，不再回来。如如如如:易损失的电子元件的库存问题，超过一定存储易损失的电子元件的库存问

13、题，超过一定存储易损失的电子元件的库存问题，超过一定存储易损失的电子元件的库存问题，超过一定存储时间的元器件被自动认为失效。时间的元器件被自动认为失效。时间的元器件被自动认为失效。时间的元器件被自动认为失效。混合制排队系统：混合制排队系统：3.3.逗留时间（等待时间与服务时间之和）有逗留时间（等待时间与服务时间之和）有限。限。例：用高射炮射击飞机，当敌机飞越射击有效区域的例：用高射炮射击飞机，当敌机飞越射击有效区域的例：用高射炮射击飞机，当敌机飞越射击有效区域的例：用高射炮射击飞机，当敌机飞越射击有效区域的时间为时间为时间为时间为t t t t时，若这个时间内未被击落，也就不可能时，若这个时间

14、内未被击落，也就不可能时，若这个时间内未被击落，也就不可能时，若这个时间内未被击落，也就不可能再被击落了。再被击落了。再被击落了。再被击落了。2023/1/418说明：说明：损失制和等待制可看成是混合制损失制和等待制可看成是混合制的特殊情形的特殊情形.如如:记记s s为系统中服务台个数，则为系统中服务台个数，则当当k=sk=s时，混合制即为损失制；时，混合制即为损失制；当当k=k=时，即成为等待制。时，即成为等待制。2023/1/419排队规则排队规则 当顾客到达时，若所有服务台都被当顾客到达时，若所有服务台都被占有且又允许排队，则该顾客将进入队占有且又允许排队，则该顾客将进入队列等待。服务台

15、对顾客进行服务所遵循列等待。服务台对顾客进行服务所遵循的规则通常有：的规则通常有：先来先服务先来先服务（FCFSFCFS）2023/1/420后来先服务后来先服务（LCFSLCFS）。在许多库存）。在许多库存系统中就会出现这种情况。系统中就会出现这种情况。如：钢板存入仓库后，需要时总是从最上面取如：钢板存入仓库后，需要时总是从最上面取如：钢板存入仓库后，需要时总是从最上面取如：钢板存入仓库后，需要时总是从最上面取出；又如在情报系统中，后来到达的信息往往更重出；又如在情报系统中，后来到达的信息往往更重出；又如在情报系统中，后来到达的信息往往更重出；又如在情报系统中，后来到达的信息往往更重要，首先

16、要加以分析和利用。要，首先要加以分析和利用。要，首先要加以分析和利用。要，首先要加以分析和利用。具有优先权的服务具有优先权的服务（PSPS）。服务台）。服务台根据顾客的优先权的不同进行服务。根据顾客的优先权的不同进行服务。如：病危的病人应优先治疗；重要的信息应优如：病危的病人应优先治疗；重要的信息应优如：病危的病人应优先治疗；重要的信息应优如：病危的病人应优先治疗；重要的信息应优先处理；出价高的顾客应优先考虑先处理；出价高的顾客应优先考虑先处理；出价高的顾客应优先考虑先处理；出价高的顾客应优先考虑。2023/1/421v3 3、服务机制、服务机制包括：包括：包括：包括：服务员的数量及其连接方式

17、服务员的数量及其连接方式服务员的数量及其连接方式服务员的数量及其连接方式（串联还是并（串联还是并（串联还是并（串联还是并联联联联）顾客是单个还是成批接受服务顾客是单个还是成批接受服务顾客是单个还是成批接受服务顾客是单个还是成批接受服务；服务时间的分布服务时间的分布服务时间的分布服务时间的分布记某服务台的服务时间为记某服务台的服务时间为V V，其分布函数，其分布函数为为B(t),B(t),密度函数为密度函数为b(t),b(t),则常见的分布则常见的分布有：有：定长分布（定长分布（定长分布（定长分布（D D）负指数分布负指数分布负指数分布负指数分布（M）KK阶爱尔朗分布（阶爱尔朗分布（阶爱尔朗分布

18、（阶爱尔朗分布（E Ek k）2023/1/422定长分布（定长分布（D D）：每个顾客接受的服：每个顾客接受的服务时间是一个确定的常数。务时间是一个确定的常数。负指数分布（负指数分布（M M）：每个顾客接受的：每个顾客接受的服务时间相互独立，具有相同的负指服务时间相互独立，具有相同的负指数分布：数分布：f(t)=e-t t 00 t0为一常数。为一常数。2023/1/423K K阶爱尔朗分布（阶爱尔朗分布（E Ek k）：）：f(t)=k(k t)k-1(K-1)!e-k t当当k=1k=1时即为负指数分布；时即为负指数分布；k k 30,30,近似于正态分布近似于正态分布;当当 k k 时

19、，方差时，方差 0 0 即为完全非即为完全非随机的。随机的。2023/1/424 排队系统的符号表示：排队系统的符号表示：“KendallKendall”记号：记号：X X/Y/Z/WY/Z/W其中：其中：X X表示顾客相继到达的时间间隔分布；表示顾客相继到达的时间间隔分布；Y Y表示服务时间的分布；表示服务时间的分布；Z Z表示服务台个数；表示服务台个数；W W表示系统的容量，即可容纳的最多顾客数。表示系统的容量，即可容纳的最多顾客数。例例1 1 M M/M/1/M/1/M M M M表示顾客相继到达的时间间隔服从负指数分布；表示顾客相继到达的时间间隔服从负指数分布；表示顾客相继到达的时间间

20、隔服从负指数分布；表示顾客相继到达的时间间隔服从负指数分布；M M M M表示服务时间为负指数分布；单个服务台；系表示服务时间为负指数分布；单个服务台；系表示服务时间为负指数分布；单个服务台；系表示服务时间为负指数分布；单个服务台；系统容量为无限（等待制）的排队模型统容量为无限（等待制）的排队模型统容量为无限（等待制）的排队模型统容量为无限（等待制）的排队模型 。例例2 2 M M/M/S/M/S/K K顾客到达的时间间隔服从负指数分布；顾客到达的时间间隔服从负指数分布；顾客到达的时间间隔服从负指数分布；顾客到达的时间间隔服从负指数分布；服务时间为服务时间为服务时间为服务时间为负指数分布；负指

21、数分布；负指数分布；负指数分布；S S S S个服务台；系统容量为个服务台；系统容量为个服务台；系统容量为个服务台；系统容量为K K K K的排队模型。的排队模型。的排队模型。的排队模型。当当当当 K=S K=S K=S K=S 时为损失制排队模型；时为损失制排队模型；时为损失制排队模型；时为损失制排队模型；当当当当 K=K=K=K=时为等待制排队模型。时为等待制排队模型。时为等待制排队模型。时为等待制排队模型。排队系统的主要数量指标：排队系统的主要数量指标：系统状态：系统状态：也称为队长，指排队系统也称为队长，指排队系统中的顾客数（排队等待的顾客数与正中的顾客数（排队等待的顾客数与正在接受服

22、务的顾客数之和）。在接受服务的顾客数之和）。排队长：排队长：系统中正在排队等待服务的系统中正在排队等待服务的顾客数。顾客数。N(t)N(t)：时刻：时刻t(tt(t 0)0)的系统状态；的系统状态；p pn n(t)(t)：时刻：时刻t t系统处于状态系统处于状态n n的概率；的概率；S S：排队系统中并行的服务台数；：排队系统中并行的服务台数；n n：当系统：当系统处于状态处于状态n n 时，新来的顾客的平均时，新来的顾客的平均到达率（单位时间内到达的平均顾客数）；到达率（单位时间内到达的平均顾客数）；n n：当系统：当系统处于状态处于状态n n 时，整个系统的平均服时，整个系统的平均服务率

23、（单位时间内可以服务完的平均顾客数）务率（单位时间内可以服务完的平均顾客数）；2023/1/428 当当当当 n n n n为常数时记为为常数时记为为常数时记为为常数时记为 ；（单位时间内到达的顾客数）单位时间内到达的顾客数）单位时间内到达的顾客数）单位时间内到达的顾客数）当每个服务台的平均服务率为常数时，记每个服当每个服务台的平均服务率为常数时，记每个服当每个服务台的平均服务率为常数时，记每个服当每个服务台的平均服务率为常数时，记每个服务台的服务率为务台的服务率为务台的服务率为务台的服务率为 ，则当则当则当则当n n n n s s s s 时，有时，有时，有时，有 n n n n=s=s=

24、s=s （单位时间内可以服务完的平均顾客数）（单位时间内可以服务完的平均顾客数）（单位时间内可以服务完的平均顾客数）（单位时间内可以服务完的平均顾客数）因此，因此，因此，因此，顾客相继到达的平均时间间隔为顾客相继到达的平均时间间隔为顾客相继到达的平均时间间隔为顾客相继到达的平均时间间隔为E(TE(TE(TE(T1 1 1 1)=1/)=1/)=1/)=1/，平均服务时间为平均服务时间为平均服务时间为平均服务时间为E(TE(T2 2)=)=1/1/1/1/，令令令令 =/s/s/s/s ，则则则则 为系统的为系统的为系统的为系统的服务强度服务强度服务强度服务强度。2023/1/429平稳状态：平

25、稳状态：p pn n(t)(t)称为系统在时刻称为系统在时刻t t的瞬间分布，一般不容易求得，同时，的瞬间分布，一般不容易求得，同时，由于排队系统运行一段时间后，其状由于排队系统运行一段时间后，其状态和分布都呈现出与初始状态或分布态和分布都呈现出与初始状态或分布无关的性质，无关的性质，称具有这种性质的状态称具有这种性质的状态或分布为平稳状态或平稳分布。或分布为平稳状态或平稳分布。排队论一般更注意研究系统在排队论一般更注意研究系统在平稳平稳状态下的性质。状态下的性质。排队系统在平稳状态时一些基本指标：排队系统在平稳状态时一些基本指标：P P P Pn n n n :系统中恰有系统中恰有系统中恰有

26、系统中恰有n n n n个顾客的概率；个顾客的概率；个顾客的概率；个顾客的概率；L L L Ls s s s：系统中顾客数的平均值，又称为平均队长；：系统中顾客数的平均值，又称为平均队长；：系统中顾客数的平均值，又称为平均队长；：系统中顾客数的平均值，又称为平均队长；L L L Lq q q q：系统中正在排队的顾客数的平均值，又称为平均：系统中正在排队的顾客数的平均值，又称为平均：系统中正在排队的顾客数的平均值，又称为平均：系统中正在排队的顾客数的平均值，又称为平均 排队长；排队长；排队长；排队长；T T T T：顾客在系统中的逗留时间；：顾客在系统中的逗留时间；：顾客在系统中的逗留时间；：

27、顾客在系统中的逗留时间；W W W Ws s s s=E(T)=E(T)=E(T)=E(T)：顾客在系统中的平均逗留时间；：顾客在系统中的平均逗留时间；：顾客在系统中的平均逗留时间；：顾客在系统中的平均逗留时间；T T T Tq q q q：顾客在系统中的排队等待时间；：顾客在系统中的排队等待时间；：顾客在系统中的排队等待时间；：顾客在系统中的排队等待时间；W W W Wq q q q=E(T=E(T=E(T=E(Tq q q q)：顾客在系统中的平均排队等待时间。：顾客在系统中的平均排队等待时间。：顾客在系统中的平均排队等待时间。：顾客在系统中的平均排队等待时间。2023/1/431Litt

28、le 公式公式其中其中 是是单位时间内到达的平均顾客数；单位时间内到达的平均顾客数；是是单位时间内可以服务完的平均顾客数。单位时间内可以服务完的平均顾客数。系统中系统中系统中系统中平均平均平均平均顾客数顾客数顾客数顾客数 =单位时间内到达的平均顾客数单位时间内到达的平均顾客数平均逗留时间平均逗留时间平均逗留时间平均逗留时间又又如果求得如果求得Pn ,则则 即即可得到。可得到。另外另外 1-P0 是系统的忙期概率。是系统的忙期概率。2023/1/432 排队论研究的基本问题：排队论研究的基本问题：通过研究主要数量指标在瞬时或平稳状态通过研究主要数量指标在瞬时或平稳状态下的概率分布及数字特征，了解

29、系统运行下的概率分布及数字特征，了解系统运行的基本特征。的基本特征。统计推断问题：建立适当的排队模型是排统计推断问题：建立适当的排队模型是排队论研究的第一步，建立模型过程中，系队论研究的第一步，建立模型过程中，系统是否达到平稳状态的检验；顾客相继到统是否达到平稳状态的检验；顾客相继到达时间间隔相互独立性的检验，服务时间达时间间隔相互独立性的检验，服务时间的分布及有关参数的确定等。的分布及有关参数的确定等。2023/1/433 排队研究的基本问题：排队研究的基本问题：系统优化问题：又称为系统控制问题系统优化问题：又称为系统控制问题或系统运营问题，其基本目的是使系或系统运营问题，其基本目的是使系统

30、处于最优的或最合理的状态。包括：统处于最优的或最合理的状态。包括：最优设计问题和最优运营问题。最优设计问题和最优运营问题。第二节第二节 输入与服务时间的分布输入与服务时间的分布一、最简单流一、最简单流1、定义、定义;在时长为 t 的时间段内，有k个顾客到达的概率 服从poisson分布：t时段内平均到达顾客数；单位时段内平均到达顾客数2、最简单流的性质、最简单流的性质（1）平稳性平稳性：在一定时间间隔内，有k个顾客到达的概率只与时长有关，与起始时刻无关；（2）无后效性无后效性：a,a+t时段内有k个顾客到达的概率与a时刻之前的客流无关；（3）普通性：普通性：在足够小的时段内有2个或个以上顾客到

31、来的概率为零。说明：1、最简单流的性质可以简化有关计算；2、假设所研究的问题都是最简单流，或近似最简单流二、最简单流的有关计算二、最简单流的有关计算1、单位时间内到达的顾客数2、内没有顾客到达的概率3、恰有一个顾客到达的概率4、若顾客到达数 poisson分布，则相继到达间隔时 间 负指数分布 三、服务时间三、服务时间设服务时间设服务时间 负指数分布负指数分布1、单位时间内服务完毕，离去的顾客数2、内没有顾客离去的概率3、恰有一个顾客离去的概率4、若干负指数分布的最小值也是负指数分说明：服务机构中有s个并联服务台，各台 负指数分布，则整个服务时间 负指数分布。生灭过程生灭过程2、t t时刻有时

32、刻有n-1n-1个顾客，个顾客，时刻系统中有时刻系统中有n n个顾客的个顾客的概率为概率为1、t t时刻有时刻有n n个顾客，个顾客，时刻系统中仍有时刻系统中仍有n n个顾客的个顾客的概率为概率为 时刻系统中有时刻系统中有n个顾客的概率个顾客的概率3、t t时刻有时刻有n+1n+1个顾客，个顾客，时刻系统中有时刻系统中有n n个顾客的个顾客的概率为概率为4、t t时刻为时刻为n,n-1,n+1n,n-1,n+1个顾客之外的情况，个顾客之外的情况，时刻时刻系统中有系统中有n n个顾客的概率为个顾客的概率为2023/1/440第第40页页于是于是特别的，特别的，n=0时时移项求极限，得差分微分方程

33、移项求极限，得差分微分方程时时,平稳状态平稳状态 一、一、M/M/1/M/M/1/模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布；服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布；服务台数为服务台数为1 1；系统的空间为无限，允许永远排队。系统的空间为无限，允许永远排队。第第三三节节 最简单的排队模型最简单的排队模型1 1、队长的分布、队长的分布记记 P Pn n=pN=n,n=0,1,2=pN=n,n=0,1,2.为系统达到平衡状态后队长的概率分布，为系统达到平衡状态后队长的概率分布，则则 n n=；n n=，=/11，有有 P

34、Pn n=(1-(1-)n n,n=0,1,2.(P (P0 0=(1-(1-)2 2、几个数量指标、几个数量指标平均队长平均队长：L=L=n Pn Pn n=n n(1-(1-)n n=/(1-/(1-)=/(/(-)平均排队长平均排队长：L Lq q=(n-1)Pn-1)Pn n=2 2/(1-/(1-)=2 2/(-)平均逗留时间：平均逗留时间：W=E(T)=1/(W=E(T)=1/(-)（littlelittlelittlelittle公式公式公式公式)平均等待时间：平均等待时间：W Wq q=/(-)例例3 3：考虑一个铁路列车编组站。设待考虑一个铁路列车编组站。设待编列车到达时间间

35、隔服从负指数分编列车到达时间间隔服从负指数分布，平均每小时到达布，平均每小时到达2 2列；服务台是列；服务台是编组站，编组时间服从负指数分布，编组站，编组时间服从负指数分布，平均每平均每2020分钟可编一组。已知编组分钟可编一组。已知编组站上共有站上共有2 2股道，当均被占用时，不股道，当均被占用时，不能接车，再来的列车只能停在站外能接车，再来的列车只能停在站外或前方站。求在平衡状态下系统中或前方站。求在平衡状态下系统中列车的平均数；每一列车的平均逗列车的平均数；每一列车的平均逗留时间；等待编组的列车平留时间；等待编组的列车平均数均数。如果列车因站中。如果列车因站中2 2股道均被占股道均被占用

36、而停在站外或前方站时，每列车每小用而停在站外或前方站时，每列车每小时费用为时费用为a a元，求每天由于列车在站外等元，求每天由于列车在站外等待而造成的损失。待而造成的损失。解：本例可看成一个解：本例可看成一个M/M/1/M/M/1/排队问题，排队问题，其中其中 =2=2，=3=3，=/=2/31=2/32=WPN2=WS S1-P1-P0 0-P-P1 1-P-P2 2=W=WS S1-(1-(l-l-)-)-(l-l-)1 1-(l-l-)2 2=1*=1*3 3=3 3=(2/3)=(2/3)3 3=0.296=0.296（小时）（小时）故每天列车由于等待而支出的平均费用故每天列车由于等待

37、而支出的平均费用E=24E=24 W W0 0a=24*2*0.296*a=14.2aa=24*2*0.296*a=14.2a元元例：例：例：例：某修理店只有一位修理工，来修理的顾客某修理店只有一位修理工，来修理的顾客某修理店只有一位修理工，来修理的顾客某修理店只有一位修理工，来修理的顾客到达过程为到达过程为到达过程为到达过程为PoissonPoissonPoissonPoisson流，平均每小时流，平均每小时流，平均每小时流，平均每小时4 4 4 4人；修理时间人；修理时间人；修理时间人；修理时间服从负指数分布，平均需要服从负指数分布，平均需要服从负指数分布，平均需要服从负指数分布，平均需要

38、6 6 6 6分钟。试求：分钟。试求：分钟。试求：分钟。试求：修理店空闲的概率修理店空闲的概率修理店空闲的概率修理店空闲的概率；店店店店内恰有内恰有内恰有内恰有3 3 3 3位顾客的概率；位顾客的概率；位顾客的概率；位顾客的概率；店内至少有一位顾客的概率；店内至少有一位顾客的概率；店内至少有一位顾客的概率；店内至少有一位顾客的概率；店内平均顾客数店内平均顾客数店内平均顾客数店内平均顾客数；每每每每位在店内平均逗留时间；位在店内平均逗留时间；位在店内平均逗留时间；位在店内平均逗留时间；等待服务的平均顾客数；等待服务的平均顾客数；等待服务的平均顾客数；等待服务的平均顾客数；每位顾客平均等待服务时间

39、；每位顾客平均等待服务时间；每位顾客平均等待服务时间；每位顾客平均等待服务时间；顾客在店内时间超过顾客在店内时间超过顾客在店内时间超过顾客在店内时间超过10101010分钟的概率。分钟的概率。分钟的概率。分钟的概率。解：本例可看成一个解：本例可看成一个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-1-1=0.3677=0.3677PTt=ePTt=e-(-(-)t)tt=10t=10分钟分钟,=10=10人人/小

40、时小时=10/60=1/6=10/60=1/6 =4=4人人/小时小时=4/60=1/15=4/60=1/15 二、二、M/M/1/NM/M/1/N 模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布；服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布；服务台数为服务台数为1 1；系统的空间为有限，最大容量系统的空间为有限，最大容量N N。2023/1/4541 1、稳定状态下，系统中有稳定状态下，系统中有n n个顾客的概率个顾客的概率 各状态间概率强度的转换关系：各状态间概率强度的转换关系：各状态间概率强度的转换关系：各状态间概率强度的

41、转换关系：012N-1N。由由 及上述差分方程可解得：及上述差分方程可解得：单位时间内的平均到达率单位时间内的平均到达率 单位时间内的平均单位时间内的平均有效到达率有效到达率 系统中有系统中有N N个顾客时，到达率为个顾客时，到达率为0 0，只有在少于，只有在少于N N个顾客时个顾客时到达率才有意义。到达率才有意义。还可验证还可验证 2 2、系统运行指标系统运行指标例、例、单人理发店有六张椅子接待客人排队理发，单人理发店有六张椅子接待客人排队理发，当当6 6张椅子坐满时，后来的顾客就不进店，随张椅子坐满时，后来的顾客就不进店，随即离开，顾客平均到达率即离开，顾客平均到达率3 3人人/小时，理发

42、平均小时，理发平均需时需时1515分钟，求：分钟，求：1 1、求顾客一到达就能理发的概率；、求顾客一到达就能理发的概率；2 2、求需要等待的平均顾客数；、求需要等待的平均顾客数；3 3、求有效到达率；、求有效到达率；4 4、每个顾客的平均逗留时间；、每个顾客的平均逗留时间；5 5、在可能到来的顾客中有百分之几不等待就、在可能到来的顾客中有百分之几不等待就离开？离开？解、解、该问题中该问题中 N=7 N=7，1 1、2 2、3 3、4 4、5.5.三、三、M/M/s/M/M/s/模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布；服务时间服从参数为服务时

43、间服从参数为 的负指数分布；的负指数分布；服务台数为服务台数为s s；系统的空间为无限系统的空间为无限1 1、稳定状态下，系统中有稳定状态下，系统中有n n个顾客的概率个顾客的概率 各状态间概率强度的转换关系：各状态间概率强度的转换关系：各状态间概率强度的转换关系：各状态间概率强度的转换关系：012nn+1。n-1nn+1n-12023/1/462由由 及上述差分方程可解得：及上述差分方程可解得：2 2、系统运行指标系统运行指标例、例、某售票点有三个窗口，顾客的到达服从某售票点有三个窗口，顾客的到达服从poisson poisson 过程，平均到达率过程，平均到达率 ，服，服务时间服从负指数分

44、布，平均服务率务时间服从负指数分布，平均服务率 。现在假设顾客到达后排成一队，一次到空闲的现在假设顾客到达后排成一队，一次到空闲的窗口买票。分析下列各问题：窗口买票。分析下列各问题：1 1、整个售票点空闲的概率；、整个售票点空闲的概率；2 2、平均排队长；、平均排队长；3 3、平均排队时间；、平均排队时间；4 4、顾客到达后必须等待的概率。、顾客到达后必须等待的概率。解、解、该问题中该问题中 1 1、2 2、3 3、4 4、s=3s=3，四、四、M/M/s/NM/M/s/N 模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布；服务时间服从参数为服务时间

45、服从参数为 的负指数分布；的负指数分布；服务台数为服务台数为s s；系统的空间为有限，最多为系统的空间为有限，最多为N N1 1、稳定状态下，系统中有稳定状态下，系统中有n n个顾客的概率个顾客的概率 当当当当s=Ns=Ns=Ns=N时时时时爱尔朗呼唤损失公式爱尔朗呼唤损失公式2 2、系统运行指标系统运行指标M/M/S M/M/S 等待制排队模型等待制排队模型多服务台问题，又表示为多服务台问题，又表示为M/M/S/M/M/S/：顾客相继到达时间服从参数为：顾客相继到达时间服从参数为 的负指的负指数分布；服务台数为数分布；服务台数为S S；每个服务台的服；每个服务台的服务时间相互独立，且服从参数

46、为务时间相互独立，且服从参数为 的负的负指数分布。当顾客到达时，若有空闲服指数分布。当顾客到达时，若有空闲服务台马上被进行服务，否则便排成一队务台马上被进行服务，否则便排成一队列等待，等待空间为无限。列等待，等待空间为无限。队长的分布队长的分布 记记P Pn n=pN=n,n=0,1,2=pN=n,n=0,1,2.为系统为系统达到平衡状态后队长达到平衡状态后队长N N的概率分布，的概率分布，对多服务台有对多服务台有 n n=；n=0,1,2n=0,1,2.n n=n=n n=0,1,2n=0,1,2.s s n n=s=s n=s,s+1,s+2n=s,s+1,s+2.s=/s=/s,当当 s

47、1时，有时，有 Cn=(/)n n!(/)s s!(/s)n-s=(/)n s!sn-sn=1,2,.sn=1,2,.sn n s spn=(p)n n!n=1,2,.sn=1,2,.s n s!sn-sn n s sp0p0其中：其中：p p0 0=0 0s-1s-1p pn n/n/n!+!+s s/s!(1-/s!(1-s s)-1-1当当n n s s时，顾客必须等待，记时，顾客必须等待，记C(s,C(s,)=)=s s p pn n=s s/s!(1-/s!(1-s s)p p0 0称为称为ErlangErlang等待公式，它给出了顾客等待公式，它给出了顾客到达系统时，需要等待的概率

48、。到达系统时，需要等待的概率。平均排队长：平均排队长：L Lq q=s s(n-s)p(n-s)pn n=p p0 0 s s s s /s/s!(1-!(1-s s)2 2或或L Lq q =C(s,C(s,)s s /(1-/(1-s s)记系统中正在接受服务的顾客平均数记系统中正在接受服务的顾客平均数s,s,显然显然s s也是正在忙的服务台平均数。也是正在忙的服务台平均数。S S=0 0s-1s-1npnpn n+s*s*s s p pn n=平均队长：平均队长：L=L=平均排队长平均排队长+正在接受服务的顾客的正在接受服务的顾客的平均数平均数=L Lq q +对多服务台，对多服务台，LittleLittle公式依然成立：公式依然成立：W=L/W=L/W Wq q=L=Lq q/=W-(1/=W-(1/)