经典排队论课件.ppt
《经典排队论课件.ppt》由会员分享,可在线阅读,更多相关《经典排队论课件.ppt(184页珍藏版)》请在三一办公上搜索。
1、1,排队论的发展史初期(10s-40s):主要研究应用于电话网和远程通信系统等无队列的排队系统(损失制)中期(40s-60s):推广应用到军事、运输、生产、社会服务等领域,主要研究有队列(等待制)的排队系统和排队网络近期(60s-今):主要研究大规模复杂排队系统的理论分析、数值分析和近似分析,尤其注重对业务突发性和带有各种网络控制的排队系统的研究,2,1909:Erlang 发表他的有关排队论的第一篇论文;1917:Erlang 发表著名的论文“Solution of Some Problems in the Theory of Probability of Significance in A
2、utomatic Telephone Exchanges”1936-47:Palm 发表论文“Repairmen in Serving Automatic Machines”1951:Kendall 发表论文”排队论中的某些问题”,在1953 年提出使用Kendall记号;1953-57:Kendall,Lindley,Pollaczek,3,1961:Little 提出Little 公式;1975/6:Kleinrock著的两卷”Queueing Systems”出版;1982:Wolff 提出和推广和 PASTA(Poisson Arrivals See Time Averages)准则1
3、981:Neuts 引进矩阵分析方法;在以后的时间里,有大量的描述突发和具有 相关性通信业务的模型(如流体模型,MMPP 模型等)发表;1990后:提出长相关自相似的业务量模型.,4,Kleinrock,Wolff,5,内容:1.基本概念和预备知识 2.Poisson到达指数服务的排队系统(M/M/1)3.M/M/m(n)问题 4.各种测度和指标 5.提高网效率的一些措施 6.优先权服务系统只涉及上世纪60年代以前的成果,此后的成果将在”现代通信中的排队论”课程中介绍,6,以上内容只是排队论的很少的一部分,也是最初等的一部分.除了从理论分析、数值分析和近似分析各方向(这些是从数学学科的角度)发
4、展外,近二十年来,在技术学科特别是通信学科的激励下,尤其注重对排队输入流(通信业务流)业务突发性和带有各种网络控制的排队系统的研究.可以毫不夸张地说,通信理论的发展,离不开排队论.,7,排队论所研究的问题有:(1)等待时间的分布,平均等待时间;(2)系统时间(也称逗留时间)的分布,平均系统时 间及系统时间的方差(时延抖动);(3)在系统中的顾客数(也称系统占有数)的分布及 均值;(4)等待顾客数的分布及其均值;(5)服务器忙着(或空闲)的概率;(6)忙期长度的分布及其均值;(7)在忙期被服务的顾客数的分布以及它的均值。,8,1.基本概念和预备知识概率知识:事件A,B它可推广到无穷多个事件的情形
5、:,(概率加法定理),9,事件A,B该公式称全概率公式若对事件A,B有则称A与B相互独立。,10,随机变量X的分布函数概率分布的母函数概率分布密度的Laplace变换X1,X2相互独立,则在离散时,和的母函数等于母函数的乘积;在连续时,和的Laplace变换等于Laplace变换的乘积.,11,Erlang,Kendall,其中:X-到达分布;Y-服务时间分布;Z-服务员个数 A-等待空间大小,B-顾客源的限制;C-服务规则,Kendall记号:X/Y/Z/A/B/C,12,2.Poisson到达指数服务的排队系统 指数分布指数分布和普松过程在排队论中有着特殊的地位。这是因为,一方面指数分布在
6、连续型概率分布中是唯一的具有无记忆性质的分布,普松分布又和指数分布有着紧密的关系。另一方面,实验证明普松分布是电话呼叫数概率分布的一种比较好的近似,而指数分布又是电话通话时间概率分布的一种好的近似,它们在排队论的发展历史中起了很大的作用并继续起着重要的作用。,13,定义 一个随机变量x当且仅当对任意的 满足条件 时,则称x的分布是无记忆的。无记忆性的直观理解是:一个物体的使用寿命是指被使用的时间,它是一个随机变量。如果该物体不论被使用了多久,其剩余寿命的分布与总寿命的分布完全相同,那么这种寿命分布是无记忆的,体现了永远年轻。,14,按条件概率定义,我们有 如果随机变量x是无记忆的,那么 反之,
7、如果随机变量的分布满足(*),则该分布是无记忆的。,15,因为指数分布的余分布函数为 而 故指数分布是无记忆的。当服务时间是指数分布时,则不论顾客占用服务台多久,其剩余的服务时间仍为指数分布的随机变量。在连续型随机变量中指数分布是唯一的具有无记忆分布的随机变量。在离散随机变量中,几何分布是唯一的具有无记忆性质的随机变量。,16,Poisson过程定义 若用n(t)表示从0开始到时刻t为止已经发生的事件的数目,则称随机过程n(t),t 0为计数过程。一般地说,在计数过程的记号上还应标以计数的起始时刻,如果过程的统计特性与起始时刻无关,则称过程为平稳的.下面我们讨论的,除非特别指明都是平稳过程。显
8、然,计数过程n(t)取非负的整数值,并且n(t)是t的非降函数。对于 是在区间(s,t内发生的事件数,量 称为n(t)在区间(s,t的增量。如当 独立,则称有独立增量.,17,Poisson过程定义(1):一计数过程n(t)如果满足1.n(0)=0;2.n(t),t 0有独立增量;3.发生在任何长为t的区间中的事件数服从参数为 的Poisson分布:Pn(t+s)-n(s)=n=则称计数过程n(t)是率(参数)为(0)的Poisson过程。,18,Poisson过程定义(2):一计数过程n(t)如果满足1.n(0)=0;2.n(t),t 0是平稳的,且有独立增量;3.Pn(h)=1=h+o(h
9、);4.Pn(h)2=o(h)。则称计数过程n(t)是参数为(0)的Poisson过程。,19,在一个时间区间内的顾客的到达数与时间起点无关叫平稳性;顾客的到达时刻相互独立称无后效性;在很短的时间间隔内到达两个以上顾客的概率可认为是0,这叫稀疏性.满足以上三个条件的随机流称为简单流.简单流的到达间隔是负指数分布的,且在一段时间内到达的顾客数是普松分布.现证明简单流的到达间隔是负指数分布:设到达间隔为t,把0,t)分成N等份,每份的长度为,在0,t)都未到达,而在时刻t有顾客到达了的概率为,20,再证明当到达间隔是指数分布时,在时间间隔T内的到达数是普松分布:把时间间隔T分成N等份,在这N个小区
10、间内,有k个顾客顾客:,21,现已证明:简单流的到达间隔是负指数分布;当到达间隔是指数分布时,在时间间隔T内的到达数是普松分布.在一段时间内,电话的呼叫是简单流,因为顾客的到达数与时间起点无关;顾客的到达时刻相互独立;在很短的时间间隔内到达两个以上顾客的概率可认为是0.,22,Poisson过程的性质如下:1.令 和 分别是具有参数和的独立Poisson过程,则N(t),t 0是率为+的Poisson过程。证明:Poisson过程的分布母函数:的分布母函数=,23,2.对于参数为的Poisson过程,假设发生的 每个事件独立地以概率p做了记录,未做记 录的概率为1-p。令n1(t)是到t为止被
11、做了记 录的事件数,而n2(t)是未被记录的事件数,则 和 分别是参数 为 和 的Poisson分布且相互独立.,24,证明:,25,这两条性质说的是:(1)独立Poisson过程的和仍是Poisson过程,而且“和过程”的参数为加项过程的参数之和;(2)Poisson过程的分支也是Poisson过程,而且 各分支过程的参数是分支概率乘以原过程 的参数.,26,Little定理:在排队系统中的平均顾客数=顾客的平均到达率平均逗留时间:EN=Es证明:,Little,27,A(t)=(0,t)内顾客的到达数,则在(0,t)内的平均到达率为。D(t)=在(0,t)内离开系统的顾客数。N(t)=在时
12、刻t,系统中的顾客数,于是N(t)=A(t)-D(t)。图中两条折线之间的面积表示在(0,t)内所有顾客花费在系统中的总时间,记为(t)。,Tt=在(0,t)内每一个顾客在系统中的平均逗留时间(对(0,t)内全部顾客取平均),于是.ENt=在(0,t)内系统中的平均顾客数,于是,令t取极限得 这里,EN是排队系统中的平均顾客数,T是一个顾客在系统中的平均逗留时间,是顾客的平均到达率。,28,这个结论与 到达间隔分布,服务时间分布,服务员个数以及 排队规则都无关。,29,排队系统(M/M/1)是指到达间隔(到达数)服从负指数(普松)分布,服务时间服从负指数分布,服务窗口数为1的排队系统.设到达分
13、布的参数为,服务时间分布的参数为,时间间隔t(不失一般性,可设为(0,t区间)内有n个顾客到达的概率记为.现考察区间,它可看成于是在内到达n个顾客这个事件可分解为以下事件的并:在 内到达n+1个顾客,在 内离开一个顾客,在 内到达n-1个顾客,在 内又到因为 的概率=;的概率=的概率=;的概率=,Markov,30,因为 的概率=;的概率=的概率=;的概率=,到达一个顾客,在 内到达n个顾客,在 内顾客的到达数和离开数相等.故而可列出以下瞬态方程:,31,在时刻 系统中有n个顾客是由以下三个事件组成:1)在时刻t有N+1个顾客,在 的时间里没有到达但离开一个顾客;2)在时刻t有N-1个顾客,在
14、 的时间里到达一个顾客但没有离开的顾客;2)在时刻t有N个顾客,在 的时间里到达和离去的顾客数相等(包括未到和未离去).,32,在 内到达一个顾客的概率为没有到达的概率为在 内离开一个顾客的概率为没有顾客离开的概率为,33,为m阶Bessel函数方程,瞬态方程的解为,34,下面我们考察随机稳态解。我们定义,于是有 这是一个递推公式,经逐次递推得 再由归一化条件求得,当然这一切必须在=/n=(1-)=,35,M/M/1的稳态解是那么平均队长是由Little定理,时延为,36,在稳定状态下指数系统的平衡方程法设所有到达间隔和服务时间都是指数分布的,那么从任何时刻直到状态变化的这段时间也是指数分布的
15、。以前我们写出P(t)的微分方程并让 而得到稳态方程,我们也可以直接列出方程。在稳定情况下,进入状态的率必须等于从同一个状态离开的率,即进入和离开的率必须平衡。对于M/M/1,以下的表是平衡的概念。,37,状态 离开率 进入率 0 P0=P1 1(+)P1=P0+P2 2(+)P2=P1+P3 3(+)P3=P2+P4 n(+)Pn=Pn-1+Pn+1 这些方程称为“平衡方程”。,38,生灭过程:它也是一种马尔科夫过程,只是状态只向相邻的状态转移.在连续时间的情况下,状态有以下转移率矩阵:,39,更一般地,对于生-灭过程,我们有n=系统处在n时的到达率,n=系统处在n时的服务率.那么由生-灭平
16、衡概念,得 状态 离开率 进入 0 0P0=1 P1 1(1+1)P1=0P0+2P2 2(2+2)P2=1P1+3P3 3(3+3)P3=2P2+4P4 n(n+n)Pn=n-1Pn-1+n+1Pn+1,40,在这情形,我们有 如此递推得 得,41,为使稳定解存在,必须要有否则 P0=0 P1=0 P2=0 等等。,42,3.M/M/m(n)问题(话务工程中的计算方法)在话务工程中,经典排队论被广泛地应用,其中爱尔兰(Erlang)-B公式和恩格塞特(Engset)公式在计算中起着重要的作用。在较长的时间内,使用这两个公式进行某种定量分析时依靠查表。国外的有些大学和研究机构早已把话务工程中涉
17、及的数学计算编成软件,如波兰波兹南大学的J.Kubasik(1985),AT&T的D.L.Jagerman(1984年)编了有关软件。现在我们将介绍这方面的内容。,43,有限源设总的用户数为N,中继线数为n,为每个用户呼叫的到达率,为服务率,如果总的话务量为A,则a.损失制如果没有缓冲器,那麽一旦系统的中继线全被占用,来到的呼叫将被拒绝,这就是损失制(式)。在损失制中我们总是假定N n(不然就无损失可言)。按设定我们有,44,系统的状态分布为,45,下面介绍呼损概率。应当说明,在有限源损失制中,有两种意义的损失率,其一为按时间计算的损失率,那就是全部服务台被占的概率 另一种意义的损失率是按呼叫
18、计算的损失率,那就是的Engset公式,它的意义是单位时间损失的平均呼叫数 与单位时间到达的平均呼叫数 之比:,46,47,b.等待制设系统的缓冲器容量为N,也就是说,如果系统的中继线全被占用,再来的呼叫总可以等待到有线路空出而得到通信。在这种制式下无损失而只有时延。按定义有,48,49,需要等待的概率为 PW0=系统中的平均顾客数(平均占有数)为 平均等待数为,50,无限源设到达率=,服务率=,中继线数=n。a.损失制状态分布为,51,阻塞(损失)概率 定义为顾客被拒绝进入队列的概率。因为按顾客计算的阻塞率是损失的顾客数与要求服务的顾客数之比,假定等待空间容量为K,当系统已达到稳定时,在长为
19、的时间内能进入系统的平均顾客数为 因为当系统在状态K时顾客的到达将被阻塞,顾客被阻塞的平均数为,所以在M/M/n的情况下,52,b.等待制,53,54,55,c.混合制(M/M/n/m),56,特别对于单服务损失制排队M/M/1/K,,57,下面我们推导一个比上式更一般的式子的递推计算公式。对于有限容量的(参数依赖状态的)M/M/1/K系统,58,以上利用了关系式:当 时,记 则有,59,按时间计算的阻塞率因为在这个系统中到达率不变,所以两种意义的阻塞率是相同的。,60,例1某商店有3个服务员,每个服务员在每一时刻只能服务一个顾客,服务时间为负指数分布,均值为2.5分钟.顾客到达为普松分布,平
20、均每分钟到达1.2人.设无等待,求顾客到达而未被服务所占的百分比;若要求到达而未被服务所占的比例小于5%,问需几个服务员?解:排队系统类型:M/M/3.,61,设需n个服务员,则,62,例2某厂有N=20台机床,每台机床平均每隔1小时就要损坏,维修人员修复一台机床的平均时间为0.1小时.如一台机床由于等待维修不能开工造成的损失为C1=180元/时.维修工的工资为C2=6元/小时.问最好保留几位维修工可使费用(损失加工资)最少?解:系统是M/M/n/N/N.排队系统的状态是损坏的机器数.,上述公式里的,63,如果发生故障的机床数为j,等待维修的机床数为(j-n),平均数为,由此造成的损失为:如果
21、损坏的机床数少于修理工的数目,则就有空闲的修理工,他们空闲着但工资照拿,对老板来说有损失:总损失=,这里都指每小时的损失.,64,65,例3某维修站有2名工人,站内可放5台机器.设待修机器的到达间隔与维修时间皆负指数分布,平均每隔5分钟就有一部机器送来,每部机器的修理时间平均为10分钟.求1)维修站里没有机器的概率;2)维修站里场地有空的概率;3)进入维修站的平均机器数;4)机器在维修站内的平均等待时间.解:这是M/M/2/5/FCFS问题.,66,67,例4售票处有三个窗口,顾客以每分钟4人的平均速度按普松规律到达,服务时间按指数分布,均值为0.5分钟.求1)售票处空闲的概率;2)平均队长;
22、3)平均等待时间和逗留时间.解:为M/M/3/,68,69,平均逗留时间:平均等待时间,70,例5有一洗车间,服务速率为60辆/小时,洗车间外可停4辆车,汽车到达的速率为40辆/小时.求1)汽车冲洗间无车的概率;2)停满车的概率;3)汽车到达此冲洗处的平均数目;4)平均等待数目;5)平均逗留时间;6)平均等待时间.解:M/M/1/5类型.,71,72,例6某商店每天开10个小时,一天平均有90个顾客到达商店,商店的服务是平均每小时服务10个顾客,若假定顾客到达服从普松规律,服务时间服从负指数分布.求1)在商店等待服务的顾客平均数;2)在队长中多于2个顾客的概率;3)在商店中的平均顾客数;4)若
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 经典 排队 课件
链接地址:https://www.31ppt.com/p-3939833.html