排队论大学课件7-MM排队模型

11:48:501排队模型回顾顾客到达排队系统请求服务如果排队系统中顾客数没有满，则进入排队系统如果有空闲的服务窗，则直接到服务机构接受服务如果服务窗全部被占用，则排队等候排队机构服务机构11:48:502M/M..排队系统的几种可能状态λ0=λμ0=0λ2=λμ2=2μλ7=λμ7=3μ假如此系统容量为7(M/M/3/7)λ7=0μ7=3μ11:48:503排队模型－Kendall记号A/B/C/D/E顾客到达间隔时间分布服务窗服务时间的分布服务窗个数系统中允许的最大顾客数，默认无穷顾客源中顾客数，默认无穷C=DE损失制队列最大长度D=等待制CD混合制队列长度有限11:48:504M/M/…的排队模型考虑整个排队系统中顾客数的变化有顾客到达，系统中顾客数加1有顾客服务完毕，系统中顾客数减1总之，顾客的到达和离开致使系统顾客数有变化M/M/…的排队系统顾客数变化有什么特点？顾客到达间隔与顾客服务时间均服从负指数分布因为顾客到达间隔时间是相互独立的，顾客接受服务也是相互独立的，因此，之前的顾客到达情况、服务情况不影响当前顾客数变化概率因为到达间隔时间和服务时间都具有无记忆性，因此，下一个顾客的到达间隔时间已经过去了多久、当前正在服务的顾客的服务时间已经过去了多久不影响当前顾客数的变化概率11:48:505M/M/…的排队模型M/M/…的排队系统，系统中顾客数变化是一种生灭过程0状态代表系统有0个顾客1状态代表系统中有1个顾客2状态代表系统中有2个顾客…生灭过程的增长率和消亡率怎么确定？增长率取决于到达率和当前系统状态消亡率取决于服务率和当前系统状态11:48:506增长率和消亡率的分析假定顾客到达为强度为的泊松流，服务窗的服务率为，服务时间服从负指数分布。考察在t（极短）时间内，若顾客到达间隔时间服从参数为的负指数分布，则在t（极短）时间内有1个顾客到达的概率为t＋o(t)，没有顾客到达的概率为1-t＋o(t)若服务时间服从参数为的负指数分布，则在t（极短）时间内有1个正在忙的服务窗服务完当前顾客的概率是t＋o(t)，1个正在忙的服务窗没有服务完的概率是1-t＋o(t)11:48:507增长率和消亡率的分析i状态下，i状态代表排队系统中有i个顾客，假定此时有j个顾客正在接受服务(ji)。若m为服务窗个数，j=i当im时,j=m当im时。,1,11()(0)(1)()()()()(1)(1)()()iittjiittjptPtPtkteeottotptPtPtkeCteotjtot内到达了1个，离开了个内到达了k个，离开了个,k2内到达了0个，离开了个内到达了k个，离开了个,k111:48:508增长率和消亡率的分析00()()()()()1()()0()()()()1()iittjtptPtPteeotjtotiptPtPteottot内到达了0个，离开了0个内到达了k个，离开了k个,k1当时内到达了0个内到达了k个，离开了k个,k111:48:509增长率和消亡率的分析由此，M/M/…型排队模型，在状态时的增长率和消亡率为：j=i,im系统顾客数少于等于服务窗数时，所有顾客都在接受服务j=m,im系统顾客数大于服务窗个数时，所有服务窗都在服务，正在接受服务的顾客数＝服务窗个数,100,100()0()limlim()0()limlimiiittiiittptttttptjttjjtt是正在忙的服务窗个数11:48:5010第三章单服务窗排队模型第一节损失制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/111:48:5011第一节单服务窗损失制排队模型M/M/1/111:48:5012排队模型分析M/M/1/1顾客到达间隔时间为负指数分布，参数为，服务窗服务时间为负指数分布，参数为，系统最大顾客数1决定了系统状态为{0,1}状态0系统中顾客数为0服务窗空闲状态1系统中有1个顾客，此顾客正在接受服务系统顾客满服务窗忙01损失的顾客()tate()tbteQ11:48:5013求解平稳分布根据马氏链、生灭过程求平稳分布的公式：列出平衡方程：0Q1001011111pppppp令本书从现在开始用{p0,p1,p2,…}表示平稳分布11:48:5014M/M/1/1的各个目标参量单位时间内损失的顾客数单位时间内平均进入系统的顾客数相对通过能力Q（即单位时间内被服务完的顾客数与请求服务顾客数之比值）绝对通过能力A（单位时间内被服务完顾客的均值）1Pp损211Lp01ep01eAp书44页011eQp11:48:5015M/M/1/1例题设某条电话线，平均每分钟有0.6次呼唤，若每次通话时间平均为1.25分钟，求相应的Q，A与P损（电话业务我们通常采用M/M/…排队模型）11:48:5016M/M/1/1例题设某条电话线，平均每分钟有0.6次呼唤，若每次通话时间平均为1.25分钟，求相应的Q，A与P损解：按题意知0130.60.80.751.254110.5757110.750.60.340.34110.75110.570.43eQpAQ损那么即在稳态时有％的呼唤得到服务即每条电话线路平均每分钟有次通话P即约43%的呼唤不能接通11:48:5017补充：系统负载业务强度（trafficintensity）/业务负载（trafficload）a.单位时间内的业务到达量（offeredload）＝单位时间内到达系统的平均呼叫数×平均通话时间长度＝b.单位时间内的业务承载量（carriedload）＝单位时间内得到服务的平均呼叫数×平均通话时间长度＝如果通话时间长度的单位为“小时”的话，则话务量单位为“小时呼”，也叫“爱尔兰（erl）”。话务量总是针对一段时间而言，如：一天或一小时。111()QQofferedload服11:48:5018补充：系统负载举例例如：某电话用户10～12点之间共拨打电话5次，总通话时间为30分钟，求此用户线平均每小时的业务量解：＝5/(2×60)＝5/30承载的业务量为a=/=30/(2×60)=0.25erl一个服务窗每小时最多提供1erl的业务承载量传统电话网：普通用户0.1~0.2erl集团交换机0.1~0.6erl11:48:5019补充：关于业务负载的几个典型参数分组交换网：考虑两个路由器之间的一条传输线路，假定每秒钟平均传输10个数据包，数据包平均长度400字节，线路传输速度为64kbps。=10=64,000/400×8则业务强度为：=10×400×8/64,000=0.5=50%如果线路速度为150Mbps，则=10×400×8/150,000,000=0.0002=0.02%11:48:5020服务强度资源利用率（utilizationratio）、服务强度＝承载业务量/线路数（服务窗个数）就是服务窗忙的概率，通信中就是输出线路有数据传输的概率或者通话线路被占用的概率1//1/1111MMp服在排队模型中，服务强度＝11:48:5021Little公式考虑一个能够达到平稳的排队系统，为到达率，W为每个顾客在系统中耗费的平均时间，L为系统中的平均顾客数，则有L=W证明：假设在一段比较长的时间区间（0,t）内，系统一直处于统计平衡状态，L，W都存在，表示单位时间进入到系统中的顾客数全部顾客一共耗费在系统中的时间＝到达的顾客数×平均等待时间＝t×W＝系统中的平均顾客数×t＝L×tlim1ttWLWLt11:48:5022Little公式的直观理解在统计平衡状态下，某一顾客离开排队系统时，回头看到的队列长度的平均值（L）应该等于此顾客在排队等待过程中平均进入排队系统的顾客数（W）WL排队系统11:48:5023Little公式的普遍性Little公式成立的条件只有一个，那就是排队系统要达到统计平衡状态，在此条件下，它适用于任何排队系统。它关心的只是排队系统的三个统计平均量，对顾客到达的间隔时间和服务时间的分布以及排队规则不作任何要求但值得注意的是，Little公式中的三个统计平均量必须是针对同一顾客群而言。Ls=sWsLq=qWqL服=服W服11:48:5024用M/M/1/1排队系统的结论验证Little公式0110011sssesssLLpppWWpLWLW服服服服服服11:48:5025Little公式的物理意义L是一个时间（timeaverage）平均的概念，是不同时刻队列长度在很长一段时间内的平均W是顾客平均的概念，是许许多多个不同顾客等待时间的平均一般来讲W比较容易从统计中获得，L比较容易从理论分析中获得01lim()ttLlxdxt11limniniWwn11:48:5026Little公式应用一个没有等待位置的餐厅，平均每小时服务完30人，平均就餐时间为30分钟，请问平均就餐人数=30W=0.5L=W=0.5×30=15（人）