您好,欢迎访问三七文档
什么是排队网络排队网络包含一组节点,每个节点有若干服务器。单个节点可以被视为一个排队系统。客户可以在从任何节点进入排队网络。当客户在某个节点排队获得服务以后,它们可以离开网络,也可以去另外的节点,甚至回到原来的节点。11.一个排队网络有k个节点,节点i(i=1,2,…,k)上有ci个服务器,服务器服务单个客户的时间服从指数分布,平均为1/μi。单个节点可以被视为一个M/M/c/∞排队系统2.客户到达是泊松过程,以速率γi到达节点i3.当一个客户在节点i的服务器上完成服务,它以概率rij进入节点j;以概率ri0离开排队网络满足以上3条被称为Jackson网络对任意i,若γi=0,ri0=0,被称为闭合Jackson网络(没有客户进入和离开)否则被称为开放Jackson网络2闭合Jackson网络例子:修理工模型,存在两个节点,正常工作和故障修理。i=1,2j=0,1,2r12=r21=1并且其余rij=0。开放Jackson网络,如果满足则这个排队网络被称为串联(Series)。客户从第一个节点进入网络客户依次经历节点1,2,3,...,直到离开网络3(1)0()ii其它1(1,11)1(,0)0()ijjiikrikj其它串联(Series)排队网络例子:医院看病:挂号、诊断开药、划价、缴费、拿药每个节点可以被视为一个M/M/c/∞,前一个节点的输出是下一个节点的输入4客户到达节点1服从泊松过程,速率为λ。节点i有ci个服务器,是一个M/M/ci排队系统。问题:客户从节点离开是怎样一个随机过程?离开时间间隔服从何种分布?结论:稳态下排队网络节点的离开过程=到达过程。离开时间间隔服从指数分布。直观解释:“时间倒流”,客户到达和客户离开互换,得到一个完全一样的稳态下的排队网络(队列长度,等待时间等指标均一样)。5理论证明系统中有N(t)=n个客户的概率T表示客户离开事件的时间间隔(类比于到达时间间隔)系统中有n个客户,且距离上次客户离开超过t的概率离开时间间隔分布6Pr{()}nNtnp()Pr{(),}nFtNtnTt0()Pr{}1()nnCtTtFt考虑在时间t+Δt有n个客户的概率令Δt→∞,有边界条件71100()(1)(1)()(1)()()()()(1)(1)()(1)()()(1)()(1)()()nnnnnnFtttctFttctFtotcnFtttntFttntFtotncFtttFtot1100()()()()()()()()()(1)()()nnnnnndFtcFtFtcndtdFtnFtFtncdtdFtFtdt(0)nnFp求解微分方程,得到800()Pr{}1()11ttnnnnCtTtFtepe离开时间间隔服从指数分布()tnnFtpe例子:超市某超市改进了结帐系统。当所有结帐柜台忙时,顾客获得一个号码并等待,当一个结帐柜台空闲,最小号码的顾客去柜台结帐。超市很大,可以容纳很多顾客。顾客到达超市服从泊松过程,平均每小时到达40位;每位顾客购物平均花费3/4小时,购物时间服从指数分布。每位顾客结帐平均需4分钟,结帐时间也服从指数分布。问:超市至少需要多少个结帐柜台?如果设置比最少要求多一个的结帐柜台,求顾客的平均等待结帐时间,平均有多少顾客等待结帐,多少顾客在超市的逗留。9两个节点的串联排队网络。节点1:购物,M/M/∞/∞,λ=40,μ1=4/3节点2:结帐,M/M/c/∞,λ=40,μ2=15问题1:ρ2=λ/cμ21c≥2.67,至少应该有3个柜台问题2:如果有4个柜台,M/M/4/∞,101430803181840.06!34!34nnpn4832150.060.0191.143!(6040)qW小时分钟11:0.757=4/600.08575.143/40.83650.14(3/4)33.44qqqL等待结账的顾客顾客结账时间小时分钟顾客商店逗留时间=购物时间+结账时间=小时分钟逗留的客户人阻塞的串联排队网络考虑具有两个节点的串联,每个节点只有1个服务器:如果节点2服务器繁忙,从节点1完成服务的客户滞留在节点1,当节点2服务器空闲时客户再进入如果节点1服务器不空闲,到达串联网络的客户离开客户只能从节点1进入,节点2离开客户在节点1有两种状态,获得服务和滞留12用(n1,n2)表示排队网络的状态客户到达速率λ,节点1的服务速率μ1,节点2的服务速率μ2用pn1,n2表示在状态(n1,n2)的概率13n1,n20,0系统空1,0客户在节点1接受服务0,1客户在节点2接受服务1,1两个客户分别在节点1和2接受服务b,1一个客户在节点2接受服务,同时有一个客户滞留在节点1等待进入节点2状态转移方程同时有,可以解状态方程如果μ1=μ2,则有140,020,111,021,10,020,111,02,1121,10,12,111,1000()0()0bbpppppppppppp12,1nnp21,00,00,10,01,10,02222,10,00,0222(2),,,222,2342bppppppppp对于带阻塞且不容许排队的情况,我们给出了节点数为2时的稳态方程并求解。如果节点个数增大,方法相同。Hunt在1956年考虑了另外一种串联排队模型:节点间不容许等待,一个客户在i-1个节点完成服务,如果不能进入第i个节点,立即离开。第一个节点有无穷大的队列空间。15开放Jackson排队网络网络有k个节点(服务设施);节点i(i=1,2,...,k)上有ci个服务器,每个服务器服务时间平均1/μi,服从指数分布;客户以速率γi到达节点i;当客户完成在节点i的服务,以概率rij进入节点j,以概率ri0离开排队网络;节点的队列容量无穷大16开放Jackson网络求解假设每个节点只有一个服务器,ci=1令Ni表示在节点i上的客户个数(排队等待+被服务)令需要得到所有状态的概率1712,,...,1122Pr{,,,}knnnkkpNnNnNn12(,,...,)knnn12,,...,knnnp状态记号12,,...,,,...,ijknnnnnn12,,...,1,,...,ijknnnnn;ni12,,...,1,,...,ijknnnnn;ni12,,...,1,...,1,...,ijknnnnn;nij状态概率方程对于节点i,客户到达的速率为矩阵形式定义ρi=λi/μi在1957年和1963年,Jackson证明18,0;;;111,111(1)kkkkkkiiijiiiiininninijniijiijiiiprprprpp(;)(;)(;)()()ninijninn从状态,,和到达状态的流量从状态离开的流量1kiijjijrλ=γ+λR1212,,...,1122(1)(1)(1)kknnnnnnnkkpp如果假设每个节点是一个M/M/1,节点i的客户到达速率为λi,平均服务时间为1/μi,则M/M/1中有n个客户的概率为可以看出,开放Jackson网络的解等于k个独立的M/M/1分别有n1,n2,...,nk个客户的联合概率仅仅是巧合!!开放Jackson网络的内部客户流量不是泊松过程。单个节点不是M/M/1,节点之间更不是相互独立的。19(1)inii121122(1)(1)(1)knnnnkkp要获得ρi,首先求解λi节点i的平均客户数客户在节点i的一次访问平均逗留时间根据Little’s等式,客户在整个网络的逗留时间20/(1)iiiL/iiiWL注意同一个客户可能多次访问一个节点11kiikiiL1()λ=γI-R当每个节点多于一个服务器,ci1,ri=λi/μi其中,,p0i满足再次,开放Jackson网络的状态概率等于k个独立M/M/c的状态概率的联合,但是这并不意味着开放Jackson网络的节点是相互独立的M/M/c2112,,...,01(/)()iknkinnnniiiiiiirpppran!()()!()iiiiiiinciiiinncanccnc00/()1iiniiiinpran讨论:由于开放Jackson网络的“内部流量”可能不服从泊松过程,因此很难求解等待时间概率分布等复杂的性能指标回馈网络和非回馈网络:如果排队网络中有回馈,即客户可以回到之前访问过的节点,这个排队网络被称为带回馈的,否则是非回馈的。非回馈网络:进入各节点的客户仍然可视为一个泊松过程,进一步分析队列或者节点的等待时间概率分布是可能的回馈网络:破坏了客户到达的泊松性质,非常难以分析我们之前获得的结果限于均值分析,适用于上述两种网络22例子:800免费电话某公司800免费电话服务如下:当用户拨号,在获得语音提示以后,可以按“1”进入产品介绍,按“2”进入问题咨询。用户用于听取语音提示并决定按“1”还是“2”的时间平均为30秒,指数分布。一次只能有一名用户听取语音提示。大约55%的用户选择产品介绍,产品介绍有三名客服人员负责,产品介绍平均6分钟,指数分布;45%的用户选择问题咨询,有7名客服人员负责问题咨询,问题咨询平均耗时20分钟,指数分布。大约有2%的用户在听完产品介绍以后转到问题咨询,1%的用户在咨询完问题以后转到产品介绍。每小时平均有35名用户拨打电话,泊松过程。当用户不能获得服务时,他们在电话里听到音乐并且等待。23问:每个环节平均有多少用户等待?用户拨打800电话的平均通话时间三个节点的开放Jackson网络,节点为:1语音提示、2产品介绍、3问题咨询节点转移概率矩阵到达速率2400.550.45000.0200.010R12335,0可得对M/M/1,M/M/3,M/M/725110.55460.461101.00020.0200.011.0002I-R1()(35,19.411,16.138)λ=γI-R111222333/35/1200.292,/19.411/101.941,/16.138/35.379rrr应用M/M/c关于队列长度的结果261231231122331231230.120,0.765,1.4020.412,2.706,6.781()/()0.283qqqqqqLLLLLrLLrLLrWLLL小时(17分钟)客户分类的开放Jackson网络客户被分为不同类型,具有不同的到达速率和节点转移矩阵。求解:第一步:分别求解,并计算λ=Σtλ(t)第二步:运用M/M/c排队模型求解节点内的平均客户数Li,客户逗留时间Wi第三步:计算每一种类型客户在节点内的平均数目,逗留时间27()()tttγR用和表示类型客户的到达速率和转移矩阵()()(1)(2)()ttiiiniiiLL()()()ttiitiLW()()()1()tttλγI-R例子:上面800电话的例子中,客户在听完产品介绍并完成问题咨询以后仍然可能进入产品介绍,而客户在完成问题咨
本文标题:排队网络
链接地址:https://www.777doc.com/doc-7208788 .html