三、排队论.ppt

M/M排队模型综述排队模型综述5/25/20241排队模型回顾排队模型回顾顾客到达排队系统请求服务如果排队系统中顾客数没有满，则进入排队系统如果有空闲的服务窗，则直接到服务机构接受服务如果服务窗全部被占用，则排队等候排队机构服务机构5/25/20242排队模型排队模型Kendall记号记号A/B/C/D/E顾顾客客到到达达间间隔隔时时间间分分布布服服务务窗窗服服务务时时间间的的分分布布服服务务窗窗个个数数系系统统中中允允许许的的最最大大顾顾客客数数，默默认认无无穷穷顾顾客客源源中中顾顾客客数数，默默认认无无穷穷C=D 损失制队列最大长度D=等待制CDm时j=m,m为服务窗个数5/25/20247增长率和消亡率的分析增长率和消亡率的分析5/25/20248增长率和消亡率的分析增长率和消亡率的分析 由此，M/M/型排队模型，在状态时的增长率和消亡率为：j=i,im 系统顾客数少于等于服务窗数时，所有顾客都在接受服务j=m,im 系统顾客数大于 服务窗个数时，所有服务窗都在服务，正在接受服务的顾客数服务窗个数5/25/20249第三章 单服务窗排队模型第一节 损失制M/M/1/1第二节 等待制M/M/1第三节 混合制M/M/1/m第四节 可变服务率的M/M/1第五节 可变输入率的M/M/1第六节 具有不耐烦顾客的M/M/1第七节 单服务窗闭合式M/M/1/m/m第八节 有差错服务的M/M/15/25/202410第一节第一节 单服务窗损失制排队模型单服务窗损失制排队模型M/M/1/15/25/202411排队模型分析排队模型分析M/M/1/1顾客到达间隔时间为负指数分布，参数为，服务窗服务时间为负指数分布，参数为，系统最大顾客数1决定了系统状态为0,1状态0系统中顾客数为0 服务窗空闲状态1 系统中有1个顾客，此顾客正在接受服务 系统顾客满服务窗忙01 损失的顾客损失的顾客5/25/202412求解平稳分布求解平稳分布根据马氏链、生灭过程求平稳分布的公式：列出平衡方程：本书从现在开始用p0,p1,p2,表示平稳分布5/25/202413M/M/1/1的各个目标参量的各个目标参量 单位时间内损失的顾客数单位时间内平均进入系统的顾客数相对通过能力Q（即单位时间内被服务完的顾客数与请求服务顾客数之比值）绝对通过能力A（单位时间内被服务完顾客的均值）书44页5/25/202414M/M/1/1例题例题设某条电话线，平均每分钟有0.6次呼唤，若每次通话时间平均为1.25分钟，求相应的Q，A与P损（电话业务我们通常采用M/M/排队模型）5/25/202415M/M/1/1例题例题设某条电话线，平均每分钟有0.6次呼唤，若每次通话时间平均为1.25分钟，求相应的Q，A与P损解：按题意知5/25/202416系统负载系统负载业务强度（traffic intensity）/业务负载（traffic load）a.单位时间内的业务到达量（offered load）单位时间内到达系统的平均呼叫数平均呼叫时间b.单位时间内的业务承载量（carried load）单位时间内得到服务的平均呼叫数平均呼叫时间5/25/202417系统负载举例系统负载举例例如：某电话用户1012小时间共拨打电话5次，总通话时间为30分钟，则该用户在1012小时间带给电话网的业务量为30分钟。5/(260)5/30业务强度为a=30/(260)=0.25erla=1意味着这项业务要占用一个服务窗5/25/202418电话网中的几个典型参数电话网中的几个典型参数传统电话网：个人用户 0.010.04erl公司用户 0.030.06erl集团交换机 0.10.6erl公共付费电话0.07erl分组交换网：考虑两个路由器之间的一条传输线路，假定每秒钟平均传输10个数据包，数据包平均长度400字节，线路传输速度为64kbps。则业务强度为：=104008/64,000=0.5=50%如果线路速度为150Mbps，则=104008/150,000,000=0.0002=0.02%5/25/202419服务强度服务强度资源利用率（utilization ratio）/服务强度承载业务量/线路数（服务窗个数）就是服务窗忙的概率，通信中就是传输线路有数据传输的概率或者通话线路被占用的概率5/25/202420附：附：Little公式公式考虑一个能够达到平稳的排队系统，为到达率，W为每个顾客在系统中耗费的平均时间，L为系统中的平均顾客数，则有L=W证明：假设在一段比较长的时间区间（0,t）内，系统一直处于统计平衡状态，L，W都存在，表示单位时间进入到系统中的顾客数全部顾客耗费在系统中的时间 到达的顾客数平均等待时间tW系统中的平均顾客数tLt5/25/202421Little公式的直观理解公式的直观理解在统计平衡状态下，某一顾客离开排队系统时，回头看到的队列长度的平均值（L）应该等于顾客在排队等待过程中平均进入排队系统的顾客数（W）WL排队系统5/25/202422Little公式的普遍性公式的普遍性Little公式成立的条件只有一个，那就是排队系统要达到统计平衡状态，除此之外，它适用于任何排队系统。它关心的只是排队系统的三个统计平均量，对顾客到达的间隔时间和服务时间的分布以及排队规则不作任何要求但值得注意的是，Little公式中的三个统计平均量必须是针对同一顾客群而言。Ls=sWsLq=qWqL服=服W服5/25/202423Little公式的物理意义公式的物理意义L是一个时间（time average）平均的概念，是不同时刻队列长度在很长一段时间内的平均W是顾客平均的概念，是许许多多个不同顾客等待时间的平均一般来讲W比较容易从统计中获得，L比较容易从理论分析中获得5/25/202424第三章 单服务窗排队模型第一节 损失制M/M/1/1第二节 等待制M/M/1第三节 混合制M/M/1/m第四节 可变服务率的M/M/1第五节 可变输入率的M/M/1第六节 具有不耐烦顾客的M/M/1第七节 单服务窗闭合式M/M/1/m/m第八节 有差错服务的M/M/15/25/2024252.1 单服务窗等待制排队模型单服务窗等待制排队模型M/M/1顾客到达参数为的泊松流顾客服务时间负指数分布，服务率为队列最大长度5/25/2024262.2 M/M/1排队模型分析排队模型分析k=k=0,1,2,3.k=k=1,2,3,4012k-1kk+1 5/25/2024272.3 平稳分布平稳分布5/25/2024282.4 目标参量目标参量1.平均系统队长2.顾客在系统内平均逗留时间5/25/2024292.4 目标参量目标参量3.系统内排队等候的平均顾客数4.顾客平均排队等候时间5/25/2024302.4 目标参量目标参量5.系统内多于k个顾客的概率6.记ls为系统内顾客数，则其方差 为7.记lq为系统内排队等候的顾客数，则其方差为5/25/202431某音乐厅设有一个售票处，营业时间为8时到16时，假定顾客流和服务时间均为负指数分布，且顾客到来的平均间隔时间为2.5分钟，窗口为每位顾客服务平均需1.5分钟，试求：顾客不需等待的概率p0；平均排队长度Ls；顾客在系统中平均逗留时间Ws；平均排队等待人数Lq；平均排队等待时间；例题例题2.1 M/M/15/25/202432 某音乐厅设有一个售票处，营业时间为8时到16时，假定顾客流和服务时间均为负指数分布，且顾客到来的平均间隔时间为2.5分钟，窗口为每位顾客服务平均需1.5分钟，试求：系统内顾客人数超过4个的概率 p=P（ls4）；顾客在系统内逗留时间大于15分钟的概率P（Ws1/4）；在六天工作日内系统中没有顾客的小时数；若决定当顾客平均逗留时间超过半小时时，就应增加一个售票窗口，试问这相当于要求顾客的平均到达率是原有的几倍？例题例题2.1 M/M/15/25/2024333.1 单服务窗混合制排队模型单服务窗混合制排队模型M/M/1/m顾客到达间隔时间参数为的负指数分布服务时间参数为的负指数分布排队系统容量：m如果顾客到达系统发现系统满员，则不得不离开，是系统损失了的顾客等待队列最大长度m-1m损失的顾客5/25/2024343.2 M/M/1/m排队模型分析排队模型分析k=k=0,1,2,3,m-1k=k=1,2,3,4,m可约、状态有限，因此是个遍历链，必定存在唯一的平稳分布012m-1m 5/25/2024353.3 平稳分布平稳分布5/25/2024363.4 目标参量（目标参量（1）1 P损2 相对通过能力Q3 等待队列的平均长度5/25/2024373.4 目标参量（目标参量（1）4 服务机构平均顾客数L服5 系统内平均顾客数Ls5/25/2024383.4 目标参量（目标参量（1）6 单位时间内平均损失的顾客数7 单位时间内平均进入系统的顾客数8 平均等待时间5/25/2024393.4 目标参量（目标参量（1）9 服务窗平均服务强度任何一个单服务窗的平均服务强度等于平均队长5/25/2024403.4 目标参量（目标参量（=1）当=1时，5/25/2024413.5 例题例题设某自行车修理处只有一个修理工，修理处内最大容量可以停放7量自行车，又自行车按平均每小时3辆的速率到达修理处要求修理，而修理工平均修理一辆自行车需要15分钟，试求各相应目标参量。5/25/2024424 可变服务率的可变服务率的M/M/1排队模排队模型型服务率会因为系统中的顾客数不同而变化举例1（有2种服务率的情况）等待制排队系统，服务率大于到达率时系统才能进入统计平衡状态0n-121n11111n+122222顾客数小于等于n时，采用服务率1顾客数大n时，采用服务率25/25/2024434 可变服务率的可变服务率的M/M/1排队模型排队模型5/25/2024444 可变服务率的可变服务率的M/M/1排队模型排队模型5/25/2024454 可变服务率的可变服务率的M/M/1排队模型排队模型例4.1书60页5/25/2024464 可变服务率的可变服务率的M/M/1排队模型排队模型举例2（服务率根据系统内顾客数成倍增长的情况）系统内顾客数为jm+1时，服务率发生变化10nn+1222n2n+1332jnjn+1(j+1)j(j+1)5/25/2024474 可变服务率的可变服务率的M/M/1排队模排队模型型平均服务率平均服务时间平均服务强度LsLq=Ls-L服WsWq5/25/2024484 可变服务率的可变服务率的M/M/1排队模型排队模型例4.2书64页5/25/2024495 可变输入率的可变输入率的M/M/1排队模排队模型型顾客到达排队系统，因为不愿进入排队系统而离开，顾客进入系统、离开系统的概率与系统内顾客人数有关。最大顾客数因不愿排队而损失的顾客（1k）k5/25/2024505 可变输入率的可变输入率的M/M/1排队模排队模型型举例:顾客进入系统的概率为实际进入到排队系统的顾客输入率为0k-121k/2/3/(k-1)/kk+1/(k+2)/(k+1)5/25/2024515 可变输入率的可变输入率的M/M/1排队模型排队模型平均输入率平均服务强度损失概率，系统内有k个顾客时，损失概率为(1-k)5/25/2024525 可变输入率的可变输入率的M/M/1排队模型排队模型例5.15/25/2024536 具有不耐烦顾客的具有不耐烦顾客的M/M/1排排队模型队模型顾客在排队等候的过程中，会因为不耐烦而离开排队系统，使系统顾客数减1，成为系统损失的顾客最大顾客数因不耐烦而离开的顾客k排队等候的顾客k个5/25/2024546 具有不耐烦顾客的具有不耐烦顾客的M/M/1排排队模型队模型假如离开的顾客流泊松流，强度与系统内排队等候的顾客数有关k，则系统内顾客数变化是生灭过程 0k-121k+1+2+k-2+k-1k+1+k5/25/2024556 具有不耐烦顾客的具有不耐烦顾客的M/M/1排队排队模型模型5/25/2024566 具有不耐烦顾客的具有不耐烦顾客的M/M/1排队排队模型模型5/25/2024576 具有不耐烦顾客的具有不耐烦顾客的M/M/1排队排队模型模型5/25/2024587 单服务窗闭合式排队模型单服务窗闭合式排队模型M/M/1/m/m顾客到达排队系统间隔时间服从负指数分布顾客接受服务的时间服从负指数分布，参数为假定顾客源中单个顾客的到达率为最大顾客数m(m-c)系统内的顾客数c顾客源中的顾客数m-c0cm5/25/2024597 单服务窗闭合式排队模型单服务窗闭合式排队模型M/M/1/m/m到达率分析顾客源中单个顾客的到达率为当系统中有k个顾客的时候，顾客源中有(m-k)个顾客，到达率为(m-k)，0m-121mm(m-1)(m-2)2M/M/1/m/m排队模型的状态流图5/25/2024607 单服务窗闭合式排队模型单服务窗闭合式排队模型M/M/1/m/m求平稳分布得：5/25/2024617 单服务窗闭合式排队模型单服务窗闭合式排队模型M/M/1/m/m此排队模型虽然系统内顾客最大数有限，但是不会出现顾客损失的情况，所有的顾客都可以进入到排队系统等候、接受服务目标参量5/25/2024627 单服务窗闭合式排队模型单服务窗闭合式排队模型M/M/1/m/m例题设机器维修工人一人负责看管3台机器，每台机器平均正常工作5天后出现一次故障，维修工人平均每天可以修复半台机器。试求平均停机台数Ls，平均停机等待修理台数Lq，机器发生故障停机到修复的平均耗时Ws，出故障机器平均等待检修的时间Wq，以及机器运转的效率与维修工人的劳动强度5/25/2024638 有差错服务的有差错服务的M/M/1排队模型排队模型0m-121mm(m-1)(m-2)2pppppM/M/1/m/m排队模型的状态流图到达率分析顾客源中单个顾客的到达率为;当系统中有k个顾客的时候，顾客源中有(m-k)个顾客，到达率为(m-k)；排出故障的正确服务率为p。5/25/2024648 有差错服务的有差错服务的M/M/1排队模型排队模型例8.15/25/202465