6通信网理论-排队论基础4

通信网理论（三）排队论与通信网业务分析排队论基础（4）纪阳北京邮电大学移动生活与新媒体实验室E-mail:[e-mail]补充：排队模型的分析举例¾单服务窗排队模型M/M/1ƒ回顾：单服务窗等待制排队模型M/M/1ƒ可变服务率的M/M/1排队模型ƒ可变输入率的M/M/1排队模型ƒ具有不耐烦顾客的M/M/1排队模型ƒ单服务窗闭合式排队模型M/M/1/m/mƒ有差错服务的M/M/1排队模型ƒ成批到达的排队模型//1kMM1）回顾：M/M/1模型1.问题描述：ƒ系统内只有1个服务窗口ƒ顾客按参数为λ的泊松分布到达，若顾客到达系统时服务窗忙则排队等待ƒ顾客到达的时间间隔与服务窗为每个顾客服务的时间均为负指数分布ƒ平均服务率为μ1）回顾：M/M/1模型2.状态图：012kK+1K-1…λλλλλλμμμμμμμλ…2）可变服务率的M/M/1排队模型1.问题描述：¾CASE1——根据队长改变平均服务强度•到达强度仍为λ（泊松分布）•服务时间仍按负指数分布•当排队长度超过某个n时，服务窗用快速服务率μ2，反之则用慢速服务率μ12）可变服务率的M/M/1排队模型2.CASE1状态图：012nn+1n-1…λλλλλλμ1μ1μ1μ1μ2μ2μ2λn+r……λμ13.问题描述：¾CASE2——根据队长改变平均服务强度•到达强度仍为λ（泊松分布）•服务时间仍按负指数分布•服务率随系统的队长k变化，记作μk2）可变服务率的M/M/1排队模型{0kkmjjmjμμμ≤≤≤L(j-1)mk，=2,3,＝2）可变服务率的M/M/1排队模型4.CASE2状态图：01m2m2m+1m+1…λλλλλλμμ2μ3μjμ(j+1)μλjm+1……λ3μjm…λλλμ2μ2μ(j+1)μ3）可变输入率的M/M/1排队模型1.问题提出：在日常生活中，经常可以看到顾客到达某服务窗前，发现因排队顾客较多而发生犹豫，究竟是否加入列等候服务。若队列较短，他下决心加入队列的可能性就大；反之，加入队列的可能性就小。2.问题描述：ƒ到达强度仍为λ，服务强度仍为μƒ3）可变输入率的M/M/1排队模型k0kkkkαααα→∞→顾客到达后加入队列的概率为（01）,是依赖于队长的，当k,kk111kααα==+0这样，顾客到达后不加入队列而离去的概率为1-在此，约定，并对进行讨论3）可变输入率的M/M/1排队模型3.状态图：012kK-1K+1……μμμμμμλλ/2λ/3λ/kλ/k+1λ/k+24)具有不耐烦顾客的M/M/1排队模型1.问题提出：当顾客到达系统时，发现窗口正忙着，则排队等候服务。如果等候排队的队伍越长或服务窗工作效率较低，引起正在排队等候的顾客出现烦躁情绪，甚至有的顾客昀终离开队伍去别处另求服务。2.问题描述：ƒ系统内只有单个服务窗，容量不限ƒ顾客到达强度仍为λƒ假设排队等候服务的顾客为k个（队长），队列中不耐烦顾客昀终离开队伍的强度为ƒ又假设顾客按泊松分布离开队伍另求服务，其强度为ƒ服务时间是服从参数为μ的负指数分布。4)具有不耐烦顾客的M/M/1排队模型kΔkΔkk→∞Δ→∞且当时，3.状态图：4)具有不耐烦顾客的M/M/1排队模型012k+2……μμ+Δ1λλλλλλk+1kμ+Δkμ+Δk+15）单服务窗闭合式排队模型M/M/1/m/m1.问题提出：例如：•一个工人负责照管（或维修）m台仪器•一条中继线连接着m条分线路•一台中央处理器接受来自m台电传打字机终端的各种信息•etc.5）单服务窗闭合式排队模型M/M/1/m/m2.问题描述：与前面所述的M/M/1模型相比，M/M/1/m/m系统容量是有限的（m），顾客数也是有限的（m）。M/M/1/m/m模型被描述为：•顾客到达系统的间隔时间和窗口为顾客服务的时间均为负指数分布•系统容量和潜在的顾客数均假定为m•顾客到达率为λ，窗口服务率为μ5）单服务窗闭合式排队模型M/M/1/m/m3.状态图：012…μμmλ(m-1)λ2λλm-1mμμμ(m-2)λ6）有差错服务的M/M/1排队模型1.问题提出：现实生活中，由于种种原因，服务窗出现差错的事件时有发生，服务的正确性存在一定的概率ρ（ρ1）。¾非闭合式排队系统：因顾客来源多，少量服务差错不影响顾客流的强度¾闭合式M/M/1/m/m排队系统：讨论有差错服务有意义6）有差错服务的M/M/1排队模型2.问题描述：假定有一工人照管m台机器（闭合式M/M/1/m/m排队系统），且在照管过程中有差错发生：•机器出故障服从参数为λ的泊松分布•工人排除故障所用的时间服从参数为μ的负指数分布•工人排除故障的一次成功率为ρ，则正确的服务率为ρμ6）有差错服务的M/M/1排队模型3.状态图：012kmm-1K+1k-1……mλ(m-1)λ(m-k)λ2λλρμρμρμρμρμ1.排队模型：ƒ顾客按参数为λ的泊松流到来，而且是成批的到达排队系统，其批量为kƒ服务窗口只有一个ƒ窗口服务时间为负指数分布称满足上述关系的排队系统为成批到达的排队模型7）成批到达的排队模型//1kMM//1kMM//1kMM2.问题描述：ƒ假定某时刻系统中已有n个顾客ƒ一个批量为k的顾客到来后，系统中顾客立即增加到n+kƒ服务窗的平均服务率为μ7）成批到达的排队模型//1kMM3.状态图：7）成批到达的排队模型//1kMM012kk+2k+1j+1……λλλλμμμμμjk+jμμ……λλ补充：排队模型的分析举例¾多服务窗排队模型M/M/nƒ回顾：多服务窗等待制排队模型M/M/nƒ窗口能力不等的多服务窗排队模型ƒ无限多个服务窗排队模型M/M/∞ƒ具有不耐烦顾客的M/M/n排队模型ƒ多服务窗闭合式排队模型M/M/n/m/mƒ多服务窗有备用品排队模型M/M/n/m+N/mƒ服务窗之间相互帮助的多服务窗排队模型1）回顾：M/M/n模型1.问题描述：ƒ系统有n个服务窗口，且各窗口工作相互独立ƒ顾客按泊松流到达，到达强度为λƒ各窗口服务时间为负指数分布，平均服务率为μƒ整个系统的平均服务率为nμ1）回顾：M/M/n模型2.状态图：012kn-1k-1…λλλλμ2μnμnμλn+1…(n-1)μn…λλkμ2）窗口能力不等的多服务窗排队模型1.问题描述：•系统内有n个服务窗，各个窗口工作独立•各个窗口的服务率分别为μ1，μ2，……，μn•系统的总服务率为•简单起见，仅考虑n=2的情形当顾客到达系统时，若两窗口均空闲着，顾客可在两服务窗之间任选一处请求服务。假定顾客选定1号或2号窗口的概率分别为φ1或φ2，φ2=1-φ11nkkμμ==∑2）窗口能力不等的多服务窗排队模型2.状态描述：ƒ0状态——系统内无顾客，而两窗口均空闲ƒ01状态——系统内只有一位顾客，且在2号窗口接受服务，1号窗口空闲着ƒ102）窗口能力不等的多服务窗排队模型状态——系统内只有一位顾客，且在1号窗口接受服务，2号窗口空闲着ƒ2状态——系统内有两位顾客，且分别在1、2号窗口接受服务ƒ3，4，…，k状态——系统内有3，4，…，k个顾客，其中两位各在1，2号窗口接受服务，其余则排队等候ƒ……3.状态图：1.问题描述：无限多个服务窗口——顾客处于随到随服务的状态ƒ顾客按泊松流到达系统，平均到达率为λƒ系统中有无限多个窗口，各个窗口工作独立ƒ各个窗口服务时间均为负指数分布，平均服务率为μ3）无限多个服务窗排队模型M/M/∞3）无限多个服务窗排队模型M/M/∞2.状态图：012…μ2μλλλλn-1n(n+2)μ(n+1)μnμn+1λ…4)具有不耐烦顾客的M/M/n排队模型1.问题提出：当顾客到达系统时，发现n个窗口均忙着，则排队等候。一般的，如果等候排队的队伍越长，或服务窗工作效率较差，引起正在排队等候的顾客出现不耐烦情绪，甚至昀终离队而去。2.问题描述：ƒ系统内有n个服务窗，容量不限ƒ顾客到达强度为λƒ假设排队队长为k时（系统中有k+n个顾客），队列中不耐烦顾客昀终离开队伍的强度与k有关，记为ƒ又假设顾客按泊松分布离开队伍，其强度为ƒ各服务窗的工作独立，服务时间服从参数为μ的负指数分布。4)具有不耐烦顾客的M/M/n排队模型kαkkα→∞→∞且当时，kα3.状态图：4)具有不耐烦顾客的M/M/n排队模型012…μ2μλλλλn+1nμ+αk+1nμ+α1nμn+kλ…n…5）多服务窗闭合式排队模型M/M/n/m/m1.问题提出：例如：•n个工人负责照管（或维修）m台仪器•n个地面机械师维护m架飞机•n台中央处理器接受各地m台电传打字机终端的信息•etc.5）多服务窗闭合式排队模型M/M/n/m/m2.问题描述：与前面所述的M/M/n模型相比，M/M/n/m/m系统容量是有限的（m），顾客数也是有限的（m）。M/M/n/m/m模型被描述为：•顾客到达系统的间隔时间和窗口为顾客服务的时间均为负指数分布•系统容量和潜在的顾客数均假定为m•顾客到达率为λ，各个窗口工作独立，服务率均为μ5）多服务窗闭合式排队模型M/M/n/m/m3.状态图：012nn+1n-1…(m-1)λmλλμ2μnμnμ…nμm(m-n+1)λ(m-n)λm-16）多服务窗有备用品排队模型M/M/n/m+N/m1.问题描述：设某单位有m部仪器正常运行，N部备用，且配备有n个维修工。如果发现仪器出现故障，则由备用品做替换，而维修工将修好的仪器作为备用。假如当出故障的仪器数大于N时，那么只好暂时缺额进行生产或实验。ƒ假定仪器出故障服从负指数分布，参数为λƒ修复仪器所需时间也是参数为μ的负指数分布称满足上述关系的排队模型为M/M/n/m+N/m。2.状态描述：–CASE1——维修工数n≤备用数N•0状态——有m台仪器运行，N台备用•1状态——有m台仪器运行，N-1台备用•……•N状态——有m台仪器运行，无备用的•N+1状态——有m-1台仪器运行，无备用的•……•N+m-1状态——有1台仪器运行，无备用的6）多服务窗有备用品排队模型M/M/n/m+N/m3.CASE1状态图：6）多服务窗有备用品排队模型M/M/n/m+N/m012…(m-1)λmλλμ2μnμnμ…nμmλN+1n+1nNN+m…mλmλnμnμ4.CASE2状态图：维修工数n备用数N6）多服务窗有备用品排队模型M/M/n/m+N/m012…mλλμ2μnμ…(N+1)μMλ(m-1)λn+1N+1NnN+m…mλnμ1.问题提出：在生产劳动和社会生活中,多服务窗口之间相互帮助的事情经常可见对此排队模型，我们需要考虑：¾当多个服务窗为一位顾客服务时,服务进度能快多少?¾各窗口之间相互帮助遵循什么原则?7）服务窗之间相互帮助的多服务窗排队模型2.问题描述：¾CASE1——损失制情形ƒ系统容量为n，当系统中有l（1≤l≤n）个顾客时，那么全体窗口在为l个顾客服务ƒ每一窗口服务强度均为μ，那么系统的服务强度为nμƒ顾客按泊松流到达，强度为λ7）服务窗之间相互帮助的多服务窗排队模型3.CASE1状态图：7）服务窗之间相互帮助的多服务窗排队模型012nμnμλλλλlnμnμnμl+1λ……l-1n-1n4.问题及状态描述：¾CASE2——混合制情形ƒ系统容量为n+m（即允许排队位置为m个），服务窗互助原则如CASE1ƒ状态l（0≤l≤n）——所有n个窗口中有l个正为l个顾客服务ƒ状态n+l（0≤l≤m）——n个窗口正为n个顾客服务，但有l个顾客正在排队等候7）服务窗之间相互帮助的多服务窗排队模型5.CASE2状态图：7）服务窗之间相互帮助的多服务窗排队模型012nμnμλλλλlnμnμnμn-1λ……l-1n+1nn+m…λnμ