经典排队论课件.ppt

1,排队论的发展史初期(10s-40s):主要研究应用于电话网和远程通信系统等无队列的排队系统(损失制)中期(40s-60s):推广应用到军事、运输、生产、社会服务等领域，主要研究有队列(等待制)的排队系统和排队网络近期(60s-今):主要研究大规模复杂排队系统的理论分析、数值分析和近似分析，尤其注重对业务突发性和带有各种网络控制的排队系统的研究,2,1909:Erlang 发表他的有关排队论的第一篇论文;1917:Erlang 发表著名的论文“Solution of Some Problems in the Theory of Probability of Significance in Automatic 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)准则1981:Neuts 引进矩阵分析方法;在以后的时间里,有大量的描述突发和具有 相关性通信业务的模型(如流体模型,MMPP 模型等)发表;1990后:提出长相关自相似的业务量模型.,4,Kleinrock,Wolff,5,内容:1.基本概念和预备知识 2.Poisson到达指数服务的排队系统(M/M/1)3.M/M/m(n)问题 4.各种测度和指标 5.提高网效率的一些措施 6.优先权服务系统只涉及上世纪60年代以前的成果,此后的成果将在”现代通信中的排队论”课程中介绍,6,以上内容只是排队论的很少的一部分,也是最初等的一部分.除了从理论分析、数值分析和近似分析各方向(这些是从数学学科的角度)发展外,近二十年来，在技术学科特别是通信学科的激励下,尤其注重对排队输入流(通信业务流)业务突发性和带有各种网络控制的排队系统的研究.可以毫不夸张地说,通信理论的发展,离不开排队论.,7,排队论所研究的问题有:(1)等待时间的分布,平均等待时间;(2)系统时间(也称逗留时间)的分布,平均系统时 间及系统时间的方差(时延抖动);(3)在系统中的顾客数(也称系统占有数)的分布及 均值;(4)等待顾客数的分布及其均值;(5)服务器忙着(或空闲)的概率;(6)忙期长度的分布及其均值;(7)在忙期被服务的顾客数的分布以及它的均值。,8,1.基本概念和预备知识概率知识：事件A，B它可推广到无穷多个事件的情形：,(概率加法定理),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到达指数服务的排队系统 指数分布指数分布和普松过程在排队论中有着特殊的地位。这是因为,一方面指数分布在连续型概率分布中是唯一的具有无记忆性质的分布,普松分布又和指数分布有着紧密的关系。另一方面,实验证明普松分布是电话呼叫数概率分布的一种比较好的近似,而指数分布又是电话通话时间概率分布的一种好的近似,它们在排队论的发展历史中起了很大的作用并继续起着重要的作用。,13,定义 一个随机变量x当且仅当对任意的 满足条件 时，则称x的分布是无记忆的。无记忆性的直观理解是:一个物体的使用寿命是指被使用的时间，它是一个随机变量。如果该物体不论被使用了多久，其剩余寿命的分布与总寿命的分布完全相同，那么这种寿命分布是无记忆的，体现了永远年轻。,14,按条件概率定义，我们有 如果随机变量x是无记忆的，那么 反之，如果随机变量的分布满足(*)，则该分布是无记忆的。,15,因为指数分布的余分布函数为 而 故指数分布是无记忆的。当服务时间是指数分布时，则不论顾客占用服务台多久，其剩余的服务时间仍为指数分布的随机变量。在连续型随机变量中指数分布是唯一的具有无记忆分布的随机变量。在离散随机变量中，几何分布是唯一的具有无记忆性质的随机变量。,16,Poisson过程定义 若用n(t)表示从0开始到时刻t为止已经发生的事件的数目，则称随机过程n(t),t 0为计数过程。一般地说,在计数过程的记号上还应标以计数的起始时刻,如果过程的统计特性与起始时刻无关,则称过程为平稳的.下面我们讨论的,除非特别指明都是平稳过程。显然,计数过程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);4.Pn(h)2=o(h)。则称计数过程n(t)是参数为(0)的Poisson过程。,19,在一个时间区间内的顾客的到达数与时间起点无关叫平稳性;顾客的到达时刻相互独立称无后效性;在很短的时间间隔内到达两个以上顾客的概率可认为是0,这叫稀疏性.满足以上三个条件的随机流称为简单流.简单流的到达间隔是负指数分布的,且在一段时间内到达的顾客数是普松分布.现证明简单流的到达间隔是负指数分布:设到达间隔为t,把0,t)分成N等份,每份的长度为,在0,t)都未到达,而在时刻t有顾客到达了的概率为,20,再证明当到达间隔是指数分布时,在时间间隔T内的到达数是普松分布:把时间间隔T分成N等份,在这N个小区间内,有k个顾客顾客:,21,现已证明:简单流的到达间隔是负指数分布;当到达间隔是指数分布时,在时间间隔T内的到达数是普松分布.在一段时间内,电话的呼叫是简单流,因为顾客的到达数与时间起点无关;顾客的到达时刻相互独立;在很短的时间间隔内到达两个以上顾客的概率可认为是0.,22,Poisson过程的性质如下:1.令 和 分别是具有参数和的独立Poisson过程,则N(t),t 0是率为+的Poisson过程。证明:Poisson过程的分布母函数：的分布母函数=,23,2.对于参数为的Poisson过程，假设发生的 每个事件独立地以概率p做了记录，未做记 录的概率为1-p。令n1(t)是到t为止被做了记 录的事件数，而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)=在时刻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的排队系统.设到达分布的参数为,服务时间分布的参数为,时间间隔t(不失一般性,可设为(0,t区间)内有n个顾客到达的概率记为.现考察区间,它可看成于是在内到达n个顾客这个事件可分解为以下事件的并:在 内到达n+1个顾客,在 内离开一个顾客,在 内到达n-1个顾客,在 内又到因为 的概率=;的概率=的概率=;的概率=,Markov,30,因为 的概率=;的概率=的概率=;的概率=,到达一个顾客,在 内到达n个顾客,在 内顾客的到达数和离开数相等.故而可列出以下瞬态方程:,31,在时刻 系统中有n个顾客是由以下三个事件组成:1)在时刻t有N+1个顾客,在 的时间里没有到达但离开一个顾客;2)在时刻t有N-1个顾客,在 的时间里到达一个顾客但没有离开的顾客;2)在时刻t有N个顾客,在 的时间里到达和离去的顾客数相等(包括未到和未离去).,32,在 内到达一个顾客的概率为没有到达的概率为在 内离开一个顾客的概率为没有顾客离开的概率为,33,为m阶Bessel函数方程,瞬态方程的解为,34,下面我们考察随机稳态解。我们定义,于是有 这是一个递推公式,经逐次递推得 再由归一化条件求得,当然这一切必须在=/n=(1-)=,35,M/M/1的稳态解是那么平均队长是由Little定理,时延为,36,在稳定状态下指数系统的平衡方程法设所有到达间隔和服务时间都是指数分布的,那么从任何时刻直到状态变化的这段时间也是指数分布的。以前我们写出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时的服务率.那么由生-灭平衡概念,得 状态 离开率 进入 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)公式在计算中起着重要的作用。在较长的时间内,使用这两个公式进行某种定量分析时依靠查表。国外的有些大学和研究机构早已把话务工程中涉及的数学计算编成软件,如波兰波兹南大学的J.Kubasik(1985),AT&T的D.L.Jagerman(1984年)编了有关软件。现在我们将介绍这方面的内容。,43,有限源设总的用户数为N，中继线数为n，为每个用户呼叫的到达率,为服务率,如果总的话务量为A，则a.损失制如果没有缓冲器,那麽一旦系统的中继线全被占用,来到的呼叫将被拒绝,这就是损失制(式)。在损失制中我们总是假定N n(不然就无损失可言)。按设定我们有,44,系统的状态分布为,45,下面介绍呼损概率。应当说明,在有限源损失制中,有两种意义的损失率,其一为按时间计算的损失率,那就是全部服务台被占的概率 另一种意义的损失率是按呼叫计算的损失率,那就是的Engset公式,它的意义是单位时间损失的平均呼叫数 与单位时间到达的平均呼叫数 之比:,46,47,b.等待制设系统的缓冲器容量为N,也就是说,如果系统的中继线全被占用,再来的呼叫总可以等待到有线路空出而得到通信。在这种制式下无损失而只有时延。按定义有,48,49,需要等待的概率为 PW0=系统中的平均顾客数(平均占有数)为 平均等待数为,50,无限源设到达率=，服务率=，中继线数=n。a.损失制状态分布为,51,阻塞(损失)概率 定义为顾客被拒绝进入队列的概率。因为按顾客计算的阻塞率是损失的顾客数与要求服务的顾客数之比,假定等待空间容量为K，当系统已达到稳定时,在长为的时间内能进入系统的平均顾客数为 因为当系统在状态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分钟.顾客到达为普松分布,平均每分钟到达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),平均数为,由此造成的损失为:如果损坏的机床数少于修理工的数目,则就有空闲的修理工,他们空闲着但工资照拿,对老板来说有损失:总损失=,这里都指每小时的损失.,64,65,例3某维修站有2名工人,站内可放5台机器.设待修机器的到达间隔与维修时间皆负指数分布,平均每隔5分钟就有一部机器送来,每部机器的修理时间平均为10分钟.求1)维修站里没有机器的概率;2)维修站里场地有空的概率;3)进入维修站的平均机器数;4)机器在维修站内的平均等待时间.解:这是M/M/2/5/FCFS问题.,66,67,例4售票处有三个窗口,顾客以每分钟4人的平均速度按普松规律到达,服务时间按指数分布,均值为0.5分钟.求1)售票处空闲的概率;2)平均队长;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)若希望商店的平均顾客数少到2人,平均服务速度需提高到多少?解:M/M/1/问题,队长分布为,73,4.各种测度和指标业务量是指在指定时间内线路被占用的总时间.若某线路有m条信道,第r条信道被占 秒,则m条信道(或该线路)的业务量为.业务的强度通常指呼叫量,是线路占用时间与观察时间之比,单位是Erlang.一天内最忙的一小时内的呼叫量称日呼叫量.一年内取三十天,取这些天的日呼叫量的平均值称为年呼叫量或基准呼叫量.,74,时间阻塞率是在总观察时间内阻塞时间所占的百 分比,它也就是截止队长为n时的拒绝概率,记为pn.呼叫阻塞率是被拒绝的呼叫次数占总呼叫次数的百分比,通常称为呼损的就是这个呼叫阻塞率,记为pc.从排队论看,pn相当于随机时刻观察系统处于状态n的概率,pc相当于顾客到达时刻观察系统处于状态n的概率.(顾客到达时,系统处于状态n将被拒绝进入系统,其概率就是拒绝的百分比.)一般说来,由于阻塞期间可能没有顾客到达,故pc pn.,75,时延指消息进入网内后直到被利用完毕所需的时间,这包括等待时间,服务时间,传输时延和处理时间.在所要求的呼叫中,有一部分被拒绝,通常以单位时间通过的业务量为通过量,即(Erlang),其中a是呼叫量,pc是呼损.也有把单位时间内通过的呼叫次数作为通过量,即(次/秒).信道的利用率:,其中 是线路的容量.,76,今考虑用户数为有限值N的准随机呼叫,令 为每个用户在单位时间内的平均呼叫次数，截止队长为n.当r个用户已被接受排队服务时,到达率为(N-r),则呼叫阻塞率为其中分子是被阻塞的呼叫次数,分母是总呼叫次数.当N时,所有r与N相比均可忽略,且,则上式成为在N有限时,pcpn.当N n时,pc和pn差别不大.从统计测量来说,用pc比用pn方便.在Nn的情况下,准随机呼叫可近似成随机呼叫.,77,设网内的源宿端间某有向径上有r条边,边上呼损(i=1,2,r),源宿端间的呼损将为对于数字线路,其容量也可用路数m来表示,它是线路上传输速率R与信息传输速率r之比:通信网中有M条边,相当于M条线路,则全网效率为 总通过量为,78,业务分析步骤:1)建立模型;2)定义状态变量;3)列出状态方程;4)求解状态方程;最后计算所需的性能指标.,79,业务分析举例1）主叫线即时拒绝系统,80,81,系统的线路利用率,换个角度,(0,1),(1,0)时通过一个,(1,1)时通过2个.对于M/M/2/2系统,82,2）公共备线即时拒绝系统,83,84,85,86,87,88,89,A端用户的呼损B端用户的呼损简化：线路的利用率：若 得近似式：,90,3）两次排队问题,输入为普松流，到达率 包/秒。每包平均比特数为a，信包长为指数分布。r和s分别为在C1和C2前的队长，信道C1和C2的服务率分别是,91,92,平均时延,效率,93,5.提高网效率的一些措施(1)大群化效应(2)延迟效应(3)综合效应(4)迂回效应,94,大群化效应:资源集中利用优于分散经营.从 及(其中a=是呼叫量,m为信道数)可算出:大群化效应之例,95,阻塞率 值要求 0.1时,可得当a=1(Erlang)时,需m=3,此时=0.0625,=(1-)/3=31%,当a=10(Erlang)时,需m=13,此时=0.0843,=10(1-0.0843)/13=70.5%,当a=100(Erlang)时,需m=96,此=0.1017,=100.系统业务量愈大节省愈明显.,96,A=100,A=10,A=5,A=1,P,m,3,13,96,97,在信息交换网中主要关心时延.已知系统时间(时延)为 信道效率为=.若把n个到达率为的业务集中到一个大容量的线路中去,若要保持或效率不变,则信道容量C也要增到n倍,使和都增到n倍,此时时延可减小到1/n:,不变,而成了n.,98,反之若保持 不变,例如10个分别排队的业务,各自的=0.5,则=2/,集中在一起时,总到达率=10,服务率,则即容量只要增到5.5倍就可使时延不变.集中后的效率为,99,延迟效应利用混合制,可降低呼损.例如M/M/m/n排队模型,其中n=m+1,即只设一个等待位置.由计算得下表,100,阻塞率pc值(n=m+1),括号内数字是M/M/m时的相应值.,101,102,由此可见只要容许一个呼叫等待,呼损就明显下降,付出的代价是有的顾客须等待的时间,当m很大时,等待时间是很短的.并且在保证Pc 0.1的条件下,以a=1(Erlang)为例,延迟拒绝比瞬时拒绝可少用一条信道,而效率从31%提高到45.6%.,103,综合效应综合是指不同性质的业务综合起来在一条线路上传输.例如数字与模拟,宽带与窄带,实时的与非实时的,高速与低速业务等.以宽带与窄带综合为例:设一条线路能容纳m路窄带信号或s路宽带信号,而一条宽带信号占n条窄带信道,并令s=m/n=整数.再设窄带与宽带业务的到达率分别为 服务率分别为,则呼叫量分别为.取损失制,(r1,r2)为系统的状态,其中r1为系统中窄带业务数,r2为宽带业务数.0 r1 m,0 r2 s.,104,105,系统的稳态状态方程为,未占满,留下空位小于等于一路宽带,106,窄带信号呼损的条件是m条信道都占满,即r1+nr2=m,则呼损为宽带信号呼损的条件是空闲信道不足n条,即r1+nr2m-n则呼损为信道利用率是,107,总呼叫量为,宽带所占的比例为 R=1全是宽带,R=0 全是窄 带。在A一定的条件下呼损是R的函数.以m=12,n=3为例计算A=3,6,12时的pc1和pc2得下图：,108,迂回效应最短路径一般作为站间业务传输的主路由,可用径可作为迂回路由.今举下例来说明迂回效应.设站间业务量都是1(Erlang),各边均两条链路.当无迂回路由时,由Erlang公式,所有呼叫的呼损皆为 迂回效应举例,109,若按以下路由表选择迂回电路 12 142 23243 34324 21231 32312 43413 41421 13123 24214 14134 31341 42432 由于对称,各边的阻塞都相同,记为B.从路由表知,3-2与1-3间的溢出业务,将经过边e12.这些业务实际通过e12的将各为(3-2间阻塞,3-1和1-2未阻塞或1-3阻塞,1-2和2-3均未阻塞).1-2间的直通业务实际通过e12的为(1-B),共计(1-B)+2(Erlang),相当于需求的呼叫量是a=1+2B(1-B)(Erlang),其它边上也是如此.,110,因m=2,由Erlang公式,阻塞率应为 算得B=0.28.因此 若允许作二次迂回,例如以下路由表,111,若允许作二次迂回,例如以下路由表 12142132 23243213 34324314 41421431 13123143 24214234 21231241 32312342 43413423 14134124 31341321 42432412用同样方法,先算得B=0.3,各站间呼叫的呼损为pc2=0.078.,112,上面只是说明如果允许有迂回路由,那末端-端的阻塞率将降低,从无迂回的0.2到一次迂回的0.11到二次迂回的0.078.然而以上计算是建立在溢出业务量也是普松分布的假定下的.,113,更严格的算法将是:设(r,s)是状态,其中r是主路由的占线数,s是溢出而在迂回路由上的占线数.再设主路由有m条信道,迂回路由的信道无限.记P状态(r,s)=,主路由中有r条信道被占的概率为迂回信道上有s条信道被占的概率为,114,溢出呼叫的状态转移图,溢出呼叫状态转移图,115,稳态方程解出pr,s是困难的,今求溢出量s的均值与方差.状态方程对s求和得,116,117,对r求和得由递推得最后有,118,现求s的方差.令,则则方差为因此需求f(m)从状态方程的第一式两边乘s再相加,可得它的解为(可代入验证),119,120,6.优先权服务系统强占优先制:新到的顾客有优先权时,如遇服务台忙(全占)他可以强占无优先权顾客的服务台,使之中断服务,退到队列中去等待.非强占优先制:新到来的具有优先权顾客,不能去打断正在服务的任何顾客的服务,只能排在无优先权顾客之前等待服务.,121,这里只介绍求非强占优先制中任意一级顾客的平均等待时间设优先权有M级,高低次序从1到M.各级顾客的到达率为各级顾客的平均服务时间为则系统的平均服务时间为h=/,其中 是系统的业务量.,122,在系统稳定时,假定新到的顾客属于第P级优先权,他的等待时间将由三部分组成:1.等待服务台空出的平均时间:设占用服务台的 顾客的平均剩余时间是,则等待服务台空出的平均时间是,(因为服务台非空的概率是).2.已经在队列中等待的第1-P级顾客的平均总占用时间:设每一级顾客的平均排队等待人数为,则每级顾客占用总时间是,i=1,2,P,由此可知,123,3.在P级新到的顾客排队等待期间,高优先级第1到(P-1)级新到客(他们比P级新到顾客迟,但因优先级高故要往前排)平均总占用时间:新到P级顾客平均等待时间WP,此间新到的1至(P-1)级顾客的平均数为,这些顾客平均总占用时间为,124,移项整理后得上式中,以(P-1)代替P得经整理最后得,125,如果新到的顾客是最高优先级的,那么上述推导中没有,其中Z为服务时间,是M个服务时间的加权平均:,126,127,其中如果对各业务的服务时间相同,则,128,P级优先权顾客的平均等待时间,主要决定于优先权较高的业务量,而于优先权较低的业务量无关;如果顾客中大部分顾客有优先权,而只有少数没有优先权,则有优先权的顾客的平均等待时间并不会缩小多少,反而没有优先权股客的平均等待时间要大为延长;当各级顾客的平均服务时间不相等时,各级顾客的业务量要受的影响,平均服务时间较长者为优先时将延长全体顾客的平均等待时间,反之平均服务时间较短的顾客列为优先级时全体顾客的平均等待时间将缩短.(体现在某个 上.),129,7.一般排队问题1)M/G/1排队系统令 是第n个顾客离开时所看到的系统中的顾客数,(其中 是第n个顾客的离开时刻,)这是一个马氏链,称为嵌入在顾客离开时刻的嵌入Markov链.令 是在第n个顾客服务时间内到达的顾客数.于是有关系,130,引理1 设 是随机变量X的分布函数,是 的Laplace-Stieljes变换.是参数为 的Poisson过程,Y是在长为X的时间内 由 发生的事件数,则 其中 表示Y的母函数.,131,证明:,132,引理2 设q是取非负整数值的随机变量,其母函数为则,133,证明:,134,定理,135,证明:,136,137,定理:在M/G/1系统中当系统稳定时,在一个离开的顾客看来留在系统中有n个顾客的概率与一个顾客到达时发现在系统中有n个顾客的概率是相同的.证明:记一个到达者看到系统内有k个顾客的概率为,一个离开者看到系统内有k个顾客的概率为,138,假定在起始时刻t=0系统中有i个顾客.系统中顾客数N(t)增加一个的时刻记为,减少一个顾客的时刻为.并记 和.若,第n+1个离开者看到系统内的顾客数不大于k.那麽,此时系统中的顾客应是第n+2,n+3,至多是第n+1+k个到达者,这也就是说,由尚未进入而即将进入系统的第n+1+k个到达者看来系统中的顾客数(连同他自己)不会超过k个,即.,139,若,也就是说,由尚未进入而即将进入系统的第n+1+k个到达者看来系统中的顾客数不会超过k个,此时系统中至多曾有n+k个顾客进入,加上在起始时刻的i个顾客,应至多曾有过n+i+k个顾客.那麽第n+i个离开者看系统顾客数不大于k,即.于是,140,队长的Pollaczek-Khintchine公式应用以上结论,我们有q是离开者看系统的顾客数,是到达者看系统的顾客数,N是任意时刻看系统时的顾客数.,141,平方变异系数:对任意非负随机变量X,它的平方变异系数定义为队长的Pollaczek-Khintchine平均值公式.,142,143,144,M/G/1系统的逗留时间其中令 是任意顾客在系统中所化费的总时间,那么是系统的逗留时间分布的Laplace-Stieltjes变换.,145,任一顾客化费在系统中的总时间内的到达顾客数的母函数为.对FCFS系统而言,在一个顾客在系统中逗留这段时间内的到达数与他离开时留下的顾客数相同的,146,逗留时间的Pollaczek-Khintchine变换公式经代数运算,得到,147,逗留时间的Pollaczek-Khintchine平均值公式M/G/1系统的等待时间,148,用(2.11)和Laplace变换的性质可证明(这是关于等待时间的Pollaczek-Khintchine平均值公式.),149,有两个常用的分布:1)爱尔兰分布;2)超指数分布.爱尔兰分布:r个独立同分布的指数分布之和是r阶爱尔兰分布.其分布密度为,此时对应的指数分布的参数是.,150,当指数分布的参数是 时,相应的r阶爱尔兰分布的分布密度为,其拉氏变换为当 称为伽马(Gamma)分布.它的密度函数写为下面仍讨论r阶爱尔兰分布,151,对指数分布,152,对,超指数分布:,153,例如二阶超指数分布:,154,155,例7:某维修点有一维修工人,平均每小时有4台机器送来,假定待修机器的到达是普松分布,每台机器的修理分两个阶段,假定这两阶段修理时间是独立的负指数分布,平均服务时间皆5分钟.求1)没有修理活的概率;2)平均等待修理的机器数;3)机器的平均等待修理的时间.解:,156,例8:银行ATM,顾客按普松规律到达,平均每小时40人,ATM办理一笔取款所需时间为36秒,求1)顾客的平均等待时间;2)顾客的平均逗留时间;3)等候取款的人数.解:M/D/1型,平均逗留时间:,平均等待数=平均占有数-:,157,2.2 G/M/1排队系统G/M/1系统可以用在正好先于顾客到达时刻的点上的嵌入Markov链 来分析.Markov链的状态是第n个到达顾客所看到的在系统中的顾客数.(第n个到达间隔期间所完成的服务数),158,G/M/1系统的嵌入Markov链的平稳概率的解有非常简单的形式:其中 是以下方程在单位圆内的唯一实根:的值可用叠代法得到:,159,由于 是第n+1个到达间隔期间所完成的服务数事件 的概率分两种情况:1)当j=0,此时,如到达间隔的长为t,则2)当j0,此时,160,其中t表示到达间隔时间.,161,G/M/1的嵌入Markov链的一步转移概率矩阵是,162,和M/G/1的情形一样,若定义,记,即,163,验证.,164,G/M/1等待时间分布为:,165,例9求排队系统 的占有分布和等待时间的分布,其中 的分布密度为服务时间的负指数参数为解:,取,166,另,于是同样得到分布:等待时间分布为,167,3)G/G/1问题(求平均等待时间)令X为服务时间,T是到达间隔,168,补,169,170,Q(s)在左半平面解析,W(s)在右半平面解析,171,讨论,该式左边在左半平面解析,右边在右半平面解析.,172,173,174,175,176,177,178,若干简化1.(无共享)时,2.完全共享存储器情形(B=Mi):因B甚大故可把项忽略,此时有则$C(B)=A_0+sumN_i=1A_irhoB_i$上式限于各$rho_i$都不相等时,否则计算留数时稍繁些.,179,其中则上式限于各 都不相等时,否则计算留数时稍繁些.,180,呼损第i种业务的丢失率(呼损)为其中和该式可用来选择某一链路上所需的存储容量B和各种业务的截止队长Mi,也就是依照公平性决定B和Mi以使各丢失率Li小于某容许值.,181,S1集表明第i个缓冲器已满；S2集表明虽第i个缓冲器未满，但总的缓冲器已满；,182,S1集表明第i个缓冲器已满；S2集表明虽第i个缓冲器未满，但总的缓冲器已满；当各种业务的队长 已接近 时,可以通知前面一些节点不要再把这些业务送来,而在前面链路存储器中停留一段时间.这是利用缓冲器来缓和本链路上的丢失,此时可用最前面的时延公式.,