运筹排队论汇总素材.pptx

2024/4/24 周三1运筹学运筹学OPERATIONS RESEARCH2024/4/24 周三21 1 排队服务系统的基本概念排队服务系统的基本概念 排队论排队论是研究排队系统（又称随机服务是研究排队系统（又称随机服务系统）的数学理论和方法，是运筹学的一系统）的数学理论和方法，是运筹学的一个重要分支。个重要分支。有形排队现象：有形排队现象：进餐馆就餐，到图书馆进餐馆就餐，到图书馆借书，车站等车，去医院看病，售票处售借书，车站等车，去医院看病，售票处售票，到工具房领物品等现象。票，到工具房领物品等现象。第十章第十章 排队论排队论2024/4/24 周三3 无形排队现象：无形排队现象：如几个旅客同时打电如几个旅客同时打电话订车票；如果有一人正在通话，其他人话订车票；如果有一人正在通话，其他人只得在各自的电话机前等待，他们分散在只得在各自的电话机前等待，他们分散在不同的地方，形成一个无形的队列在等待不同的地方，形成一个无形的队列在等待通电话。通电话。排队的不一定是人，也可以是物。如排队的不一定是人，也可以是物。如生产线上的原材料，半成品等待加工；因生产线上的原材料，半成品等待加工；因故障而停止运行的机器设备在等待修理；故障而停止运行的机器设备在等待修理；码头上的船只等待装货或卸货；要下降的码头上的船只等待装货或卸货；要下降的飞机因跑道不空而在空中盘旋等。飞机因跑道不空而在空中盘旋等。2024/4/24 周三4当然，进行服务的也不一定是人，可以当然，进行服务的也不一定是人，可以是跑道，自动售货机，公共汽车等。是跑道，自动售货机，公共汽车等。顾客顾客要求服务的对象。要求服务的对象。服务员服务员提供服务的服务者（也称服提供服务的服务者（也称服务机构）。务机构）。顾客、服务员的含义是广义的。顾客、服务员的含义是广义的。2024/4/24 周三5随机性随机性顾客到达情况与顾客接受服顾客到达情况与顾客接受服务的时间是随机的。务的时间是随机的。一般来说，排队论所研究的排队系统中，一般来说，排队论所研究的排队系统中，顾客相继到达时间间隔和服务时间这两顾客相继到达时间间隔和服务时间这两个量中至少有一个是随机的，因此，排个量中至少有一个是随机的，因此，排队论又称队论又称随机服务理论。随机服务理论。随机服务理论随机服务理论研究如何合理的设置服务系统，研究如何合理的设置服务系统，更好的为顾客服务，减少排队时间，同时又更好的为顾客服务，减少排队时间，同时又要使得费用尽可能节省。要使得费用尽可能节省。2024/4/24 周三6排队系统类型排队系统类型1：服务台服务台顾客到达顾客到达顾客到达顾客到达服务完成后离开服务完成后离开服务完成后离开服务完成后离开单服务台排队系统单服务台排队系统2024/4/24 周三7排队系统类型排队系统类型2：服务台服务台2 2顾客到达顾客到达顾客到达顾客到达服务完成后离开服务完成后离开服务完成后离开服务完成后离开S S个服务台，一个队列的排队系统个服务台，一个队列的排队系统服务台服务台s s服务台服务台1 12024/4/24 周三8排队系统类型排队系统类型3：服务台服务台2顾客到达顾客到达顾客到达顾客到达服务完成后离开服务完成后离开服务完成后离开服务完成后离开S S个服务台，个服务台，S S个队列的排队系统个队列的排队系统服务台服务台s服务台服务台1服务完成后离开服务完成后离开服务完成后离开服务完成后离开服务完成后离开服务完成后离开服务完成后离开服务完成后离开2024/4/24 周三9排队系统类型排队系统类型4：服务台服务台服务台服务台1 1顾客到达顾客到达顾客到达顾客到达离开离开离开离开多服务台串联排队系统多服务台串联排队系统服务台服务台服务台服务台s s s s2024/4/24 周三10 排队系统的描述排队系统的描述 实际中的排队系统各不相同，但概括实际中的排队系统各不相同，但概括起来都由三个基本部分组成：起来都由三个基本部分组成：1 1、输入过程、输入过程;2 2、排队及排队规则、排队及排队规则;3 3、服务机构、服务机构2024/4/24 周三11 河流上游流入水库的水量可认为是无限的；车河流上游流入水库的水量可认为是无限的；车河流上游流入水库的水量可认为是无限的；车河流上游流入水库的水量可认为是无限的；车间内停机待修的机器显然是有限的。间内停机待修的机器显然是有限的。间内停机待修的机器显然是有限的。间内停机待修的机器显然是有限的。到达方式：到达方式：是单个到达还是成批到达。是单个到达还是成批到达。库存问题中，若把进来的货看成顾客，则为成批到库存问题中，若把进来的货看成顾客，则为成批到库存问题中，若把进来的货看成顾客，则为成批到库存问题中，若把进来的货看成顾客，则为成批到达的例子。达的例子。达的例子。达的例子。v1、输入过程、输入过程顾客总体（顾客源）数顾客总体（顾客源）数：可能是有限，：可能是有限，也可能是无限。也可能是无限。2024/4/24 周三12顾客（单个或成批）相继到达的时顾客（单个或成批）相继到达的时间间隔分布间间隔分布：这是刻划输入过程的：这是刻划输入过程的最重要内容。最重要内容。令令T T0 0=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)。2024/4/24 周三13XXn n 的分布的分布A(t)A(t)常见的有：常见的有：定长分布定长分布（D D）：顾客相继到达的时间间）：顾客相继到达的时间间隔为确定的。隔为确定的。如产品通过传送带进入包装箱就是定常分布。如产品通过传送带进入包装箱就是定常分布。如产品通过传送带进入包装箱就是定常分布。如产品通过传送带进入包装箱就是定常分布。最简单流（或称最简单流（或称Poisson)Poisson)（M M）：顾客相）：顾客相继到达的时间间隔继到达的时间间隔XXn n 为独立的，同为为独立的，同为负指数分布，其密度函数为：负指数分布，其密度函数为：f(t)=e-t t 0 0 t 02024/4/24 周三14v2、排队及排队规则、排队及排队规则排队排队有限排队有限排队排队系统中顾客数是有限排队系统中顾客数是有限的。（的。（损失制排队系统，混合制排队系统损失制排队系统，混合制排队系统损失制排队系统，混合制排队系统损失制排队系统，混合制排队系统）无限排队无限排队顾客数是无限，队列可以顾客数是无限，队列可以排到无限长（等待制排队系统）。排到无限长（等待制排队系统）。2024/4/24 周三15有限排队有限排队还可以分成：还可以分成：损失制排队系统损失制排队系统：排队空间为零的系：排队空间为零的系统，即不允许排队。（顾客到达时，统，即不允许排队。（顾客到达时，服务台占满，顾客自动离开，不再回服务台占满，顾客自动离开，不再回来）（电话系统）来）（电话系统）混合制排队系统混合制排队系统：是等待制与损失制：是等待制与损失制结合，即允许排队，但不允许队列无结合，即允许排队，但不允许队列无限长。限长。2024/4/24 周三16混合制排队系统：混合制排队系统：1.1.队长有限队长有限,即系统等待空间是有限的。即系统等待空间是有限的。例：最多只能容纳例：最多只能容纳例：最多只能容纳例：最多只能容纳K K K K个顾客在系统中，当新顾客到达个顾客在系统中，当新顾客到达个顾客在系统中，当新顾客到达个顾客在系统中，当新顾客到达时，若系统中的顾客数（又称为队长）小于时，若系统中的顾客数（又称为队长）小于时，若系统中的顾客数（又称为队长）小于时，若系统中的顾客数（又称为队长）小于K K K K，则，则，则，则可进入系统排队或接受服务；否则，便离开系统，可进入系统排队或接受服务；否则，便离开系统，可进入系统排队或接受服务；否则，便离开系统，可进入系统排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床并不再回来。如水库的库容是有限的，旅馆的床并不再回来。如水库的库容是有限的，旅馆的床并不再回来。如水库的库容是有限的，旅馆的床位是有限的位是有限的位是有限的位是有限的。2024/4/24 周三172.2.等待时间有限。即顾客在系统中等待时等待时间有限。即顾客在系统中等待时间不超过某一给定的长度间不超过某一给定的长度T T，当等待时间，当等待时间超过超过T T时，顾客将自动离开，不再回来。时，顾客将自动离开，不再回来。如如如如:易损失的电子元件的库存问题，超过一定存储易损失的电子元件的库存问题，超过一定存储易损失的电子元件的库存问题，超过一定存储易损失的电子元件的库存问题，超过一定存储时间的元器件被自动认为失效。时间的元器件被自动认为失效。时间的元器件被自动认为失效。时间的元器件被自动认为失效。混合制排队系统：混合制排队系统：3.3.逗留时间（等待时间与服务时间之和）有逗留时间（等待时间与服务时间之和）有限。限。例：用高射炮射击飞机，当敌机飞越射击有效区域的例：用高射炮射击飞机，当敌机飞越射击有效区域的例：用高射炮射击飞机，当敌机飞越射击有效区域的例：用高射炮射击飞机，当敌机飞越射击有效区域的时间为时间为时间为时间为t t t t时，若这个时间内未被击落，也就不可能时，若这个时间内未被击落，也就不可能时，若这个时间内未被击落，也就不可能时，若这个时间内未被击落，也就不可能再被击落了。再被击落了。再被击落了。再被击落了。2024/4/24 周三18说明：说明：损失制和等待制可看成是混合制损失制和等待制可看成是混合制的特殊情形的特殊情形.如如:记记s s为系统中服务台个数，则为系统中服务台个数，则当当k=sk=s时，混合制即为损失制；时，混合制即为损失制；当当k=k=时，即成为等待制。时，即成为等待制。2024/4/24 周三19排队规则排队规则 当顾客到达时，若所有服务台都被当顾客到达时，若所有服务台都被占有且又允许排队，则该顾客将进入占有且又允许排队，则该顾客将进入队列等待。服务台对顾客进行服务所队列等待。服务台对顾客进行服务所遵循的规则通常有：遵循的规则通常有：先来先服务先来先服务（FCFSFCFS）2024/4/24 周三20后来先服务后来先服务（LCFSLCFS）。在许多库存系统）。在许多库存系统中就会出现这种情况。中就会出现这种情况。如：钢板存入仓库后，需要时总是从最上面取出；如：钢板存入仓库后，需要时总是从最上面取出；如：钢板存入仓库后，需要时总是从最上面取出；如：钢板存入仓库后，需要时总是从最上面取出；又如在情报系统中，后来到达的信息往往更重要，又如在情报系统中，后来到达的信息往往更重要，又如在情报系统中，后来到达的信息往往更重要，又如在情报系统中，后来到达的信息往往更重要，首先要加以分析和利用。首先要加以分析和利用。首先要加以分析和利用。首先要加以分析和利用。具有优先权的服务具有优先权的服务（PSPS）。服务台根据）。服务台根据顾客的优先权的不同进行服务。顾客的优先权的不同进行服务。如：病危的病人应优先治疗；重要的信息应优先处如：病危的病人应优先治疗；重要的信息应优先处如：病危的病人应优先治疗；重要的信息应优先处如：病危的病人应优先治疗；重要的信息应优先处理；出价高的顾客应优先考虑理；出价高的顾客应优先考虑理；出价高的顾客应优先考虑理；出价高的顾客应优先考虑。2024/4/24 周三21v3 3、服务机制、服务机制包括：包括：包括：包括：服务员的数量及其连接方式服务员的数量及其连接方式服务员的数量及其连接方式服务员的数量及其连接方式（串联还是并（串联还是并（串联还是并（串联还是并联联联联）顾客是单个还是成批接受服务顾客是单个还是成批接受服务顾客是单个还是成批接受服务顾客是单个还是成批接受服务；服务时间的分布服务时间的分布服务时间的分布服务时间的分布记某服务台的服务时间为记某服务台的服务时间为V V，其分布函数，其分布函数为为B(t),B(t),密度函数为密度函数为b(t),b(t),则常见的分布则常见的分布有：有：定长分布（定长分布（定长分布（定长分布（D D）负指数分布负指数分布负指数分布负指数分布（M）KK阶爱尔朗分布（阶爱尔朗分布（阶爱尔朗分布（阶爱尔朗分布（E Ek k）2024/4/24 周三22定长分布（定长分布（D D）：每个顾客接受的服：每个顾客接受的服务时间是一个确定的常数。务时间是一个确定的常数。负指数分布（负指数分布（M M）：每个顾客接受的：每个顾客接受的服务时间相互独立，具有相同的负指服务时间相互独立，具有相同的负指数分布：数分布：f(t)=e-t t 00 t0为一常数。为一常数。2024/4/24 周三23K 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 时，方差时，方差 0 0 即为完全非即为完全非随机的。随机的。2024/4/24 周三24 排队系统的符号表示：排队系统的符号表示：“KendallKendall”记号：记号：X X/Y/Z/WY/Z/W其中：其中：X X表示顾客相继到达的时间间隔分布；表示顾客相继到达的时间间隔分布；Y Y表示服务时间的分布；表示服务时间的分布；Z Z表示服务台个数；表示服务台个数；W W表示系统的容量，即可容纳的最多顾客数。表示系统的容量，即可容纳的最多顾客数。2024/4/24 周三25例例1 1 M M/M/1/M/1/M M M M表示顾客相继到达的时间间隔服从负指数分布；表示顾客相继到达的时间间隔服从负指数分布；表示顾客相继到达的时间间隔服从负指数分布；表示顾客相继到达的时间间隔服从负指数分布；M M M M表示服务时间为负指数分布；单个服务台；系表示服务时间为负指数分布；单个服务台；系表示服务时间为负指数分布；单个服务台；系表示服务时间为负指数分布；单个服务台；系统容量为无限（等待制）的排队模型统容量为无限（等待制）的排队模型统容量为无限（等待制）的排队模型统容量为无限（等待制）的排队模型 。例例2 2 M M/M/S/M/S/K K顾客到达的时间间隔服从负指数分布；顾客到达的时间间隔服从负指数分布；顾客到达的时间间隔服从负指数分布；顾客到达的时间间隔服从负指数分布；服务时间为服务时间为服务时间为服务时间为负指数分布；负指数分布；负指数分布；负指数分布；S S S S个服务台；系统容量为个服务台；系统容量为个服务台；系统容量为个服务台；系统容量为K K K K的排队模型。的排队模型。的排队模型。的排队模型。当当当当 K=S K=S K=S K=S 时为损失制排队模型；时为损失制排队模型；时为损失制排队模型；时为损失制排队模型；当当当当 K=K=K=K=时为等待制排队模型。时为等待制排队模型。时为等待制排队模型。时为等待制排队模型。2024/4/24 周三26排队系统的主要数量指标：排队系统的主要数量指标：系统状态：系统状态：也称为队长，指排队系统也称为队长，指排队系统中的顾客数（排队等待的顾客数与正中的顾客数（排队等待的顾客数与正在接受服务的顾客数之和）。在接受服务的顾客数之和）。排队长：排队长：系统中正在排队等待服务的系统中正在排队等待服务的顾客数。顾客数。2024/4/24 周三27N(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 时，整个系统的平均服时，整个系统的平均服务率（单位时间内可以服务完的平均顾客数）务率（单位时间内可以服务完的平均顾客数）；2024/4/24 周三28 当当当当 n n n n为常数时记为为常数时记为为常数时记为为常数时记为 ；（单位时间内到达的顾客数）单位时间内到达的顾客数）单位时间内到达的顾客数）单位时间内到达的顾客数）当每个服务台的平均服务率为常数时，记每个服当每个服务台的平均服务率为常数时，记每个服当每个服务台的平均服务率为常数时，记每个服当每个服务台的平均服务率为常数时，记每个服务台的服务率为务台的服务率为务台的服务率为务台的服务率为 ，则当则当则当则当n n n n s s s s 时，有时，有时，有时，有 n n n n=s=s=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 ，则则则则 为系统的为系统的为系统的为系统的服务强度服务强度服务强度服务强度。2024/4/24 周三29平稳状态：平稳状态：p pn n(t)(t)称为系统在时刻称为系统在时刻t t的瞬间的瞬间分布，一般不容易求得，同时，由于分布，一般不容易求得，同时，由于排队系统运行一段时间后，其状态和排队系统运行一段时间后，其状态和分布都呈现出与初始状态或分布无关分布都呈现出与初始状态或分布无关的性质，的性质，称具有这种性质的状态或分称具有这种性质的状态或分布为平稳状态或平稳分布。布为平稳状态或平稳分布。排队论一般更注意研究系统在排队论一般更注意研究系统在平稳状态平稳状态下的性质。下的性质。2024/4/24 周三30排队系统在平稳状态时一些基本指标：排队系统在平稳状态时一些基本指标：P P P Pn n n n :系统中恰有系统中恰有系统中恰有系统中恰有n n n n个顾客的概率；个顾客的概率；个顾客的概率；个顾客的概率；L L L Ls s s s：系统中顾客数的平均值，又称为平均队长；：系统中顾客数的平均值，又称为平均队长；：系统中顾客数的平均值，又称为平均队长；：系统中顾客数的平均值，又称为平均队长；L L L Lq q q q：系统中正在排队的顾客数的平均值，又称为平均：系统中正在排队的顾客数的平均值，又称为平均：系统中正在排队的顾客数的平均值，又称为平均：系统中正在排队的顾客数的平均值，又称为平均 排队长；排队长；排队长；排队长；T T T T：顾客在系统中的逗留时间；：顾客在系统中的逗留时间；：顾客在系统中的逗留时间；：顾客在系统中的逗留时间；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)：顾客在系统中的平均排队等待时间。：顾客在系统中的平均排队等待时间。：顾客在系统中的平均排队等待时间。：顾客在系统中的平均排队等待时间。2024/4/24 周三31Little 公式公式其中其中 是是单位时间内到达的平均顾客数；单位时间内到达的平均顾客数；是是单位时间内可以服务完的平均顾客数。单位时间内可以服务完的平均顾客数。系统中系统中系统中系统中平均平均平均平均顾客数顾客数顾客数顾客数 =单位时间内到达的平均顾客数单位时间内到达的平均顾客数平均逗留时间平均逗留时间平均逗留时间平均逗留时间又又如果求得如果求得Pn ,则则 即可得到。即可得到。另外另外 1-P0 是系统的忙期概率。是系统的忙期概率。2024/4/24 周三32 排队论研究的基本问题：排队论研究的基本问题：通过研究主要数量指标在瞬时或平稳状态通过研究主要数量指标在瞬时或平稳状态下的概率分布及数字特征，了解系统运行下的概率分布及数字特征，了解系统运行的基本特征。的基本特征。统计推断问题：建立适当的排队模型是排统计推断问题：建立适当的排队模型是排队论研究的第一步，建立模型过程中，系队论研究的第一步，建立模型过程中，系统是否达到平稳状态的检验；顾客相继到统是否达到平稳状态的检验；顾客相继到达时间间隔相互独立性的检验，服务时间达时间间隔相互独立性的检验，服务时间的分布及有关参数的确定等。的分布及有关参数的确定等。2024/4/24 周三33 排队研究的基本问题：排队研究的基本问题：系统优化问题：又称为系统控制问题系统优化问题：又称为系统控制问题或系统运营问题，其基本目的是使系或系统运营问题，其基本目的是使系统处于最优的或最合理的状态。包括：统处于最优的或最合理的状态。包括：最优设计问题和最优运营问题。最优设计问题和最优运营问题。2024/4/24 周三342 2 输入与服务时间的分布输入与服务时间的分布一、最简单流一、最简单流1、定义、定义;在时长为 t 的时间段内，有k个顾客到达的概率 服从poisson分布：t时段内平均到达顾客数；单位时段内平均到达顾客数2024/4/24 周三352、最简单流的性质、最简单流的性质（1）平稳性平稳性：在一定时间间隔内，有k个顾客到达的概率只与时长有关，与起始时刻无关；（2）无后效性无后效性：a,a+t时段内有k个顾客到达的概率与a时刻之前的客流无关；（3）普通性：普通性：在足够小的时段内有2个或个以上顾客到来的概率为零。说明：1、最简单流的性质可以简化有关计算；2、假设所研究的问题都是最简单流，或近似最简单流2024/4/24 周三36二、最简单流的有关计算二、最简单流的有关计算1、单位时间内到达的顾客数2、内没有顾客到达的概率3、恰有一个顾客到达的概率4、若顾客到达数 poisson分布，则相继到达间隔时 间 负指数分布 2024/4/24 周三37三、三、服务时间服务时间设服务时间设服务时间 负指数分布负指数分布1、单位时间内服务完毕，离去的顾客数2、内没有顾客离去的概率3、恰有一个顾客离去的概率4、若干负指数分布的最小值也是负指数分说明：服务机构中有s个并联服务台，各台 负指数分布，则整个服务时间 负指数分布。2024/4/24 周三38第第38页页生灭过程2024/4/24 周三39第第39页页2、t t时刻有时刻有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个顾客的概率为个顾客的概率为2024/4/24 周三40第第40页页于是于是特别的，特别的，n=0时时2024/4/24 周三41第第41页页移项求极限，得差分微分方程移项求极限，得差分微分方程时时,平稳状态平稳状态推导过程见书推导过程见书P2602024/4/24 周三42 4 4 最简单的最简单的排队模型排队模型一、一、M/M/1/M/M/1/模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布；服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布；服务台数为服务台数为1 1；系统的空间为无限，允许永远排队。系统的空间为无限，允许永远排队。2024/4/24 周三431 1、队长的分布、队长的分布记记 P Pn n=pN=n,n=0,1,2=pN=n,n=0,1,2.为系统达到平衡状态后队长的概率分布，为系统达到平衡状态后队长的概率分布，则则 n n=；n n=，=/11，有有 P Pn n=(1-(1-)n n,n=0,1,2.(P (P0 0=(1-(1-)2024/4/24 周三442 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/(-)2024/4/24 周三45平均逗留时间：平均逗留时间：W=E(T)=1/(W=E(T)=1/(-)（littlelittlelittlelittle公式公式公式公式)平均等待时间：平均等待时间：W Wq q=/(-)2024/4/24 周三46例例3 3：考虑一个铁路列车编组站。设待考虑一个铁路列车编组站。设待编列车到达时间间隔服从负指数分编列车到达时间间隔服从负指数分布，平均每小时到达布，平均每小时到达2 2列；服务台是列；服务台是编组站，编组时间服从负指数分布，编组站，编组时间服从负指数分布，平均每平均每2020分钟可编一组。已知编组分钟可编一组。已知编组站上共有站上共有2 2股道，当均被占用时，不股道，当均被占用时，不能接车，再来的列车只能停在站外能接车，再来的列车只能停在站外或前方站。求在平衡状态下系统中或前方站。求在平衡状态下系统中列车的平均数；每一列车的平均逗列车的平均数；每一列车的平均逗留时间；等待编组的列车平留时间；等待编组的列车平2024/4/24 周三47 均数。如果列车因站中均数。如果列车因站中2 2股道均被占股道均被占用而停在站外或前方站时，每列车每用而停在站外或前方站时，每列车每小时费用为小时费用为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（小时）（小时）故每天列车由于等待而支出的平均费用故每天列车由于等待而支出的平均费用E=24E=24 W W0 0a=24*2*0.296*a=14.2aa=24*2*0.296*a=14.2a元元2024/4/24 周三50例：例：某修理店只有一位修理工，来修理某修理店只有一位修理工，来修理的顾客到达过程为的顾客到达过程为PoissonPoisson流，平均每流，平均每小时小时4 4人；修理时间服从负指数分布，人；修理时间服从负指数分布，平均需要平均需要6 6分钟。试求：分钟。试求：修理店空闲的概率；修理店空闲的概率；修理店空闲的概率；修理店空闲的概率；店内恰有店内恰有店内恰有店内恰有3 3 3 3位顾客的概率；位顾客的概率；位顾客的概率；位顾客的概率；店内至少有一位顾客的概率；店内至少有一位顾客的概率；店内至少有一位顾客的概率；店内至少有一位顾客的概率；店内平均顾客数；店内平均顾客数；店内平均顾客数；店内平均顾客数；每位在店内平均逗留时间；每位在店内平均逗留时间；每位在店内平均逗留时间；每位在店内平均逗留时间；等待服务的平均顾客数；等待服务的平均顾客数；等待服务的平均顾客数；等待服务的平均顾客数；每位顾客平均等待服务时间；每位顾客平均等待服务时间；每位顾客平均等待服务时间；每位顾客平均等待服务时间；顾客在店内时间超过顾客在店内时间超过顾客在店内时间超过顾客在店内时间超过10101010分钟的概率。分钟的概率。分钟的概率。分钟的概率。2024/4/24 周三51解：本例可看成一个解：本例可看成一个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人人/小时小时=10/60=1/6=10/60=1/6 =4=4人人/小时小时=4/60=1/15=4/60=1/152024/4/24 周三55 二、二、M/M/1/NM/M/1/N 模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布；服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布；服务台数为服务台数为1 1；系统的空间为有限，最大容量系统的空间为有限，最大容量N N。2024/4/24 周三561 1、稳定状态下，系统中有稳定状态下，系统中有n n个顾客的概率个顾客的概率 各状态间概率强度的转换关系：各状态间概率强度的转换关系：各状态间概率强度的转换关系：各状态间概率强度的转换关系：012N-1N。2024/4/24 周三57由由 及上述差分方程可解得：及上述差分方程可解得：单位时间内的平均到达率单位时间内的平均到达率 单位时间内的平均单位时间内的平均有效到达率有效到达率 系统中有系统中有N N个顾客时，到达率为个顾客时，到达率为0 0，只有在少于，只有在少于N N个顾客时个顾客时到达率才有意义。到达率才有意义。还可验证还可验证 2024/4/24 周三582 2、系统运行指标系统运行指标2024/4/24 周三59例、例、单人理发店有六张椅子接待客人排队理发，当单人理发店有六张椅子接待客人排队理发，当6 6张椅张椅子坐满时，后来的顾客就不进店，随即离开，顾客平子坐满时，后来的顾客就不进店，随即离开，顾客平均到达率均到达率3 3人人/小时，理发平均需时小时，理发平均需时1515分钟，求：分钟，求：1 1、求顾客一到达就能理发的概率；、求顾客一到达就能理发的概率；2 2、求需要等待的平均顾客数；、求需要等待的平均顾客数；3 3、求有效到达率；、求有效到达率；4 4、每个顾客的平均逗留时间；、每个顾客的平均逗留时间；5 5、在可能到来的顾客中有百分之几不等待就离开？、在可能到来的顾客中有百分之几不等待就离开？2024/4/24 周三60解、解、该问题中该问题中 N=7 N=7，1 1、2 2、2024/4/24 周三613 3、4 4、5.5.损失率损失率2024/4/24 周三62 三、三、M/M/s/M/M/s/模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布；服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布；服务台数为服务台数为s s；系统的空间为无限系统的空间为无限2024/4/24 周三631 1、稳定状态下，系统中有稳定状态下，系统中有n n个顾客的概率个顾客的概率 各状态间概率强度的转换关系：各状态间概率强度的转换关系：各状态间概率强度的转换关系：各状态间概率强度的转换关系：012nn+1。n-1nn+1n-12024/4/24 周三64由由 及上述差分方程可解得：及上述差分方程可解得：2024/4/24 周三652 2、系统运行指标系统运行指标2024/4/24 周三66例、例、某售票点有三个窗口，顾客的到达服从某售票点有三个窗口，顾客的到达服从poisson poisson 过过程，平均到达率程，平均到达率 ，服务时间服从负，服务时间服从负指数分布，平均服务率指数分布，平均服务率 。现在假设顾客到达后排成一队，一次到空闲的窗口买现在假设顾客到达后排成一队，一次到空闲的窗口买票。分析下列各问题：票。分析下列各问题：1 1、整个售票点空闲的概率；、整个售票点空闲的概率；2 2、平均排队长；、平均排队长；3 3、平均排队时间；、平均排队时间；4 4、顾客到达后必须等待的概率。、顾客到达后必须等待的概率。2024/4/24 周三67解、解、该问题中该问题中 s=3 s=3，1 1、2 2、3 3、4 4、2024/4/24 周三68 四、四、M/M/s/NM/M/s/N 模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布；服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布；服务台数为服务台数为s s；系统的空间为有限，最多为系统的空间为有限，最多为N N2024/4/24 周三691 1、稳定状态下，系统中有稳定状态下，系统中有n n个顾客的概率个顾客的概率 当当当当s=Ns=Ns=Ns=N时时时时爱尔朗呼唤损失公式爱尔朗呼唤损失公式2024/4/24 周三702 2、系统运行指标系统运行指标2024/4/24 周三712024/4/24 周三72 M/M/S M/M/S 等待制排队模型等待制排队模型多服务台问题，又表示为多服务台问题，又表示为M/M/S/M/M/S/：顾：顾客相继到达时间服从参数为客相继到达时间服从参数为 的负指数的负指数分布；服务台数为分布；服务台数为S S；每个服务台的服；每个服务台的服务时间相互独立，且服从参数为务时间相互独立，且服从参数为 的的负指数分布。当顾客到达时，若有空负指数分布。当顾客到达时，若有空闲服务台马上被进行服务，否则便排闲服务台马上被进行服务，否则便排成一队列等待，等待空间为无限。成一队列等待，等待空间为无限。2024/4/24 周三73队长的分布队长的分布 记记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.2024/4/24 周三74 s=/s=/s,当当 s1时，有时，有 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 sp0p02024/4/24 周三75其中：其中：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等待公式，它给出了顾客等待公式，它给出了顾客到达系统时，需要等待的概率。到达系统时，需要等待的概率。2024/4/24 周三76平均排队长：平均排队长：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=2024/4/24 周三77平均队长：平均队长：L=L=平均排队长平均排队长+正在接受服务的顾客的正在接受服务的顾客的平均数平均数=L Lq q +对多服务台，对多服务台，