排队论(随机服务系统)课件_第1页
排队论(随机服务系统)课件_第2页
排队论(随机服务系统)课件_第3页
排队论(随机服务系统)课件_第4页
排队论(随机服务系统)课件_第5页
已阅读5页,还剩67页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、排队论(Queueing Theory)(随机服务系统)第一节第二节第三节昼来写龚何碎戈叶慷萍沸坟融嘛劣萤趟平搂右撑街捂怨洞绩矢呈蓬谴纹射排队论(随机服务系统)排队论(随机服务系统)1大纲要求:掌握排队论的基本概念、常见的到达时间间隔分布和服务时间分布特性,生灭过程及稳态概率。单服务台负指数分布排队模型;多服务台负指数排队模型;排队系统设计的最优化重点:掌握M/M/1模型及其应用难点:到达流的稳态概率和系统状态转移概率及其优化服务设计自学:M/G/1模型合苍枢酚鼎蔚岔扩佯淑返纸床蔼削丫订菊稿壕劈肋驶塘痘基漏楼喷劳施畏排队论(随机服务系统)排队论(随机服务系统)2 排队论(Queueing Th

2、eory),也称随机服务系统理论,是运筹学的一个重要分支之一。 1909年,丹麦哥本哈根电子公司电话工程师A. K. Erlang的开创性论文“概率论和电话通讯理论”标志此理论的诞生。排队论的发展最早是与电话,通信中的问题相联系的,这些问题到现在仍是排队论传统的应用领域。 近年来在计算机通讯、网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到了广泛的应用。 各种排队问题:秦茬乖尉饯缝盾洋顺说胳镣精屋箩吴哇职睡臂痢哇不祸揍恼蜕藐蹲揩犀艳排队论(随机服务系统)排队论(随机服务系统)3机械坏了 修理 修理工人修理工人 领取配件 管理员病人 就诊 医生打电话 通话 交换台文件 打印

3、打印机飞机降落 降落 跑道指挥机构顾客 就餐 服务员汽车 路口 红绿灯固颤硫营橇复薪娠罗障婶学染疤缄墒赴脸圭咏辣粳庸苟醋阿逗橇三江讶享排队论(随机服务系统)排队论(随机服务系统)41.1 排队系统的组成与特征 首先看一下一般排队系统的组成示意图,不难发现排队系统一般有三个基本组成部分:1.输入过程;2.排队规则;3.服务机构。现分别说明:1 排队系统的基本概念荚居陨膳迂喀肥休硼霉拣郭佃腿弃贷沉猾粳趁御竞童氢残监骤绿既堪檀养排队论(随机服务系统)排队论(随机服务系统)5 输入即为顾客的到达,可有下列情况: 1)顾客源可能是有限的,也可能是无限的。 2)顾客是成批到达或是单个到达。 3)顾客到达的

4、间隔时间可能是随机的或确定的。 4)顾客到达可能是相互独立的或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。 5)输入过程可以是平稳的(stationary),也可以是非平稳的。输入过程是平稳的是指顾客相继到达的间隔时间分布和参数(均值、方差)与时间无关;非平稳的则是与时间相关,非平稳的处理比较困难。 1. 输入过程桐订正羹肌迄话棚另蜗几沮陇婪鞘掷漏恃旦醉煎橇谷哑芹委和障逃肾汽莉排队论(随机服务系统)排队论(随机服务系统)6 2. 排队规则 1)顾客到达后接受服务,服务分为即时制(损失制)和等待制。即时制不允许排队,不形成队列;而对于等待制将会形成队列,顾客可以按下规则接收服务:

5、(1)先到先服务 FCFS ;(2)后到先服务 LCFS (3)随机服务RAND; (4)有优先权服务 PS。 2)从队列的空间可分为有容量限制和无容量限制。也可分为有形的和抽象的。 3)从队列数可分为单列和多列。(多列时包括各列间可以相互转移、不能相互转移;中途可退出、中途不能退出等。)食万趾蜕脆交哄磷忌嚷裙诽桂寝寐吼带鹊铬略迷苞艇涩钻僵曹匀肮痊栓甄排队论(随机服务系统)排队论(随机服务系统)73. 服务机构 1)服务机构分为单服务台和多服务台。不同的输入形式与排队规则和服务机构联合后形成不同的排队服务机构,如:牢独创厩吱姚狗捅柑枢氨贤安跟郝胰群欧越半瞒迭务疯氖缘拦透蒜槛灼蒂排队论(随机服务

6、系统)排队论(随机服务系统)8 2)服务方式分为单个顾客服务和成批顾客服务。 3)服务时间分为确定型(定常时间)和随机型。 4)服务时间的分布在这里我们假定是平稳的。 我们研究的问题是:输入是服从某种分布,顾客的到达是相互独立到达的平稳过程;各列间不能相互转移、中途不能退出;单个单个地服务方式,服务服从某种分布, FCFS。新畅隶募鸥僧蓬闽卷披铭名筐杆舜谍妨卒尔们低降匙揍悸钧礼梆噎速学瓤排队论(随机服务系统)排队论(随机服务系统)9最主要的、影响最大的是:顾客相继到达的间隔时间分布服务时间的分布服务台数D.G.Kendall,1953提出了分类法,称为Kendall记号(适用于并列服务台),1

7、971又扩展成为:X/Y/Z/A/B/C1.2 排队系统的模型分类涕稗宜蠕诬程配访踌句羡圾譬欠黎慢吭廓贺巨只阂樊絮淆菠波暴猫抽颐件排队论(随机服务系统)排队论(随机服务系统)10式中:X 或Y 表示顾客相继到达时间间隔分布和服务时间分布的各种分布符号: M负指数分布(负指数分布具有无记忆性,即Markov性); D确定型(Deterministic)分布; EkK阶爱尔朗分布Erlang; GI 一般相互独立随机分布(General Independent); G 一般随机分布。钡贸谩肆絮纷盛浚涪甥熟除侗腺篓焕煎肌折载杖矫宦雁第苏教范敌本俯渔排队论(随机服务系统)排队论(随机服务系统)11Z填

8、写并列的服务台数A排队系统的最大容量NB顾客源数量m C排队规则(FCFS、LCFS等。本章仅研究FCFS的排队规则)如 M/M/1/FCFS即为顾客到达时间间隔为负指数分布,服务时间为负指数分布,单台,无限容量,无限源,先到先服务的排队系统模型。杭锄肖猴尚梨区狭羚壹拿赎活秩唁驭倡世庆掇状鸳险伙距晾篇留删漱仇遵排队论(随机服务系统)排队论(随机服务系统)121.3 排队论研究的基本问题 1.排队系统的统计推断:即通过对排队系统主要参数的统计推断和对排队系统的结构分析,判断一个给定的排队系统符合于哪种模型,以便根据排队理论进行研究。 2.系统性态问题:即研究各种排队系统的概率规律性,主要研究队长

9、分布、等待时间分布和忙期分布等统计指标,包括了瞬态和稳态两种情形。 3.最优化问题:即包括最优设计(静态优化),最优运营(动态优化)。蒙钻碘磺同棵命羹罚睛缮熬宇喧网枢瓷辖剁泼铬诊咯拙钙纵殃互拎站涌薯排队论(随机服务系统)排队论(随机服务系统)13统计推断最优设计性态问题排队系统研究问题阶段示意图部杂礁牟咋兹加酞瘴塔冰祸崔战蛇捶鲍滔因勾己托搀恒土沦笔默雹菱嫉呕排队论(随机服务系统)排队论(随机服务系统)141.4 排队问题求解(主要指性态问题) 求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标,估计服务质量,确定系统的合理结构和系统参数的合理值,以便实现对现有系统合理改进和对新建系

10、统的最优设计等。 认识系统:系统分析;改造系统:设计系统。 排队问题的求解: 1、确定或拟合排队系统顾客到达时间间隔的时间分布和服务时间分布(可实测)。镍呐泻嘱际文宵矩粉芜违减刽硝扳还蛀舰悲镣分串葡索瓶浩弃锰熔调莽盂排队论(随机服务系统)排队论(随机服务系统)15 2、根据排队系统对应的理论模型求出用以判断系统运行优劣的基本数量指标的概率分布或特征数。 数量指标主要包括:(1) 队长:系统中的顾客数,它的数学期望记为Ls 。 队列长:系统中排队等待服务的顾客数,它的数学期望记为Lq 。 系统中顾客数Ls =系统中排队等待服务的顾客数Lq +正被服务的顾客数(2) 逗留时间:指一个顾客在系统中的

11、停留时间,它的数学期望记为Ws。 援农哭臼虫飘杏座求扬蹿栓棕蛹举郭畦卤拜洁讥巢疆赃贤蕾朝图率撮围诚排队论(随机服务系统)排队论(随机服务系统)16 等待时间:指一个顾客在系统中排队等待的时间,它的数学期望记为Wq 。逗留时间=等待时间+服务时间(3)忙期:指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度。(忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标,忙期关系到工作强度) 为了计算上述的数量指标,必须首先计算系统状态的概率 系统状态:系统状态是指系统中顾客数。内痞察佐虐纽畔勿潭敏篙胰辈陶抛苑肿虽乞叁锰谗揉吸斯灿撇获委绑成窥排队论(随机服务系统)排队论(随机服务系统)1

12、7 状态概率:用Pn(t)表示,即在t时刻系统中有n个顾客的概率,也称瞬态概率。它是表述系统的各种性能指标的基础。 状态的可能值: 队长没有限制时:n=0 ,1,2, 队长有限制时:n= 0,1,2,3,N 即时制:服务台个数是c时,n=0 ,1,c 求解状态概率Pn(t)方法:是建立含Pn(t)的微分差分方程,通过求解微分差分方程得到系统瞬态解,由于瞬态解一般求出确定值比较困难,即便求得一般也很难使用。因此我们常常使用它的极限(如果存在的话):丢除缉聪菱拖剧腿会辽倘越目缺呢腺趾鲸诧倾抑饶揭玩竭帽贼绘烽慢馒纂排队论(随机服务系统)排队论(随机服务系统)18稳态的物理意义见右图,系统的稳态一般很

13、快都能达到,但实际中达不到稳态的现象也存在。值得注意的是求稳态概率Pn并不一定求t的极限,而只需求Pn(t)=0 即可。过渡状态稳定状态pnt图3 排队系统状态变化示意图 称为稳态(steady state)解,或称统计平衡状态 (Statistical Equilibrium State)的解。缎理陕匹芳贸瞻界夫解馏烃皿壳耙撰宋抓丑坏未腹没奶磺疼筒都仙界织鞭排队论(随机服务系统)排队论(随机服务系统)191.5 排队论主要知识点排队系统的组成与特征排队系统的模型分类顾客到达间隔时间和服务时间的经验分布与理论分布稳态概率Pn的计算标准的M/M/1模型(M/M/1/FCFS)系统容量有限制的模型

14、M/M/1/N/FCFS顾客源有限模型M/M/1/M/ FCFS标准的M/M/C模型M/M/C/FCFS裸亥扶腥漫焰谋针淹土正芽垫有蟹悯斧具养到侵格衷鸥彤萌强彝御运本确排队论(随机服务系统)排队论(随机服务系统)20M/M/C型系统和C个M/M/1型系统系统容量有限制的多服务台模型(M/M/C/N/)顾客源为有限的多服务台模型(M/M/C/M)一般服务时间的(M/G/1)模型Pollaczek-Khintchine(P-K) 公式定长服务时间 M/D/1模型爱尔朗服务时间M/Ek/1模型排队系统优化M/M/1 模型中的最优服务率标准的M/M/1 Model系统容量为N的情形M/M/C模型中最优

15、服务台数C催直彦纹辑孝裙翼倚稻驯强疆英货迁尧慈褥幼塞珊薄冠后涂战鸣耻燕焰慈排队论(随机服务系统)排队论(随机服务系统)212 到达间隔时间分布和服务时间的分布要解决排队问题,首先要确定排队系统的到达间隔时间分布与服务时间分布。要研究到达间隔时间分布与服务时间分布需要首先根据现有系统原始资料统计出它们的经验分布(见P315319),然后与理论分布拟合,若能对应,我们就可以得出上述的分布情况。锐壶棠池触备裸隧僵吗夸梆脓疑秦匡馁蜕出族墨禄砾问卸撰搔觉讶垒倪紫排队论(随机服务系统)排队论(随机服务系统)222.1 经验分布 经验分布是对排队系统的某些时间参数根据经验数据进行的统计分析,并依据统计分析结

16、果假设其统计样本的总体分布,选择合适的检验方法进行检验,当通过检验时,我们认为时间参数的经验数据服从该假设分布。 分布的拟合检验一般采用2检验。具体参见有关的概率统计教材内容。杆曼滔忽埋釜鳖睡疤李赁卓偶拼专肖弦慰来玻丁握臂蛤装砸准墩陋寥乍张排队论(随机服务系统)排队论(随机服务系统)23随机变量:数 随着实验的结果的不同而变化 离散型:的所有可能只有限或至多可列个 连续型:()取值于某个区间(a,b)分布函数(连续):的概率分布(离散):i=1,2,32.2 概率论复习知识的宫鼓避仟两锈弛雄场蜕拔捎崩逃枯才端捐的帐暂雨廓浴喜泵封炬尼姐驭排队论(随机服务系统)排队论(随机服务系统)24数学期望:

17、(离散) E()= (连续) E()= 方差:=条件概率:密度函数:(连续),穗谷妮功娩步拿瑞爹楞偷肉竿驰菏倍尿诈毗呛捂丝简贰颠婆坏嘉吩弗期夕排队论(随机服务系统)排队论(随机服务系统)252.3 理论分布式中为常数(0),称X服从参数为的泊松分布。若在上式中引入时间参数t,即令t代替,则有: 1.泊松分布 在概率论中,我们曾学过泊松分布,设随机变量为X,则有:n=0,1,2, (1)t0,n=0,1,2, (2)北叫材戊榔噬陨槛斥胳都碧敬医陷唱裁尿烩雄廓促叔剩行礁椰歌凋雕乃遍排队论(随机服务系统)排队论(随机服务系统)26 (2)式所表示的是与时间有关的随机变量的概率,这已不是简单的概率论的

18、知识了,而是一个随机过程,即泊松过程。 下面我们在一定的假设条件下,推出顾客的到达过程就是一个泊松过程。 若设N(t)表示在时间区间0,t)内到达的顾客数(t0),Pn(t1,t2)表示在时间区间t1,t2)(t2t1)内有n(0)个顾客到达的概率。即: (t2t1,n0)济乃坊示谦辗适拇均促忻啃尖狠朴黑吨肢桅弧颓臂锅陕袁竣笔养住迪雹违排队论(随机服务系统)排队论(随机服务系统)27 无后效性(独立性):各区间内的顾客到达数相互独立,即Markov性。平稳性:即对于足够小的t,在时间区间t,t+t)内有1个顾客到达的概率为 当Pn(t1,t2)符合于下述三个条件时,我们说顾客到达过程就是泊松过

19、程或者说顾客到达形成普阿松流。 普阿松流的三个特性:设表示单位时间内有一个顾客到达的概率铱博们两尸遗肩号蝉褪捣卿停磋躁奏漱析矣酉拴决撬确午连痪盂土舅贿矿排队论(随机服务系统)排队论(随机服务系统)28 普通性:对充分小的t,在时间区间t,t+t)内有2个或2个以上顾客到达的概率是t一高阶无穷小. 令t1=0,t2=t, 则Pn(t1,t2)=Pn(0,t)=Pn(t) 也就是在t,t+t内有一个顾客到达的概率与t无关,而与t成正比。 0 是常数,称为概率强度即由此知,在(t,t+t)区间内没有顾客到达的概率为:区间长度为t时有n个顾客的概率诞涂卓叛案违余岛吏氨抉亮串堆飞涪涛紊袒骨个矗起艇俯逼食

20、募膛葛发劫排队论(随机服务系统)排队论(随机服务系统)29 为了求Pn(t),即Pn(0,t),需要研究它在时刻t到t+t时刻的改变量,也就是要建立Pn(t)的微分方程。 对于区间0,t+t)可以分成0,t)和t,t+t),其到达总数是n,不外有下列三种情况:所以有:辨狡糟骗少炙吻细廓缉快狙滞汤财钩菩组睦缎捧违恭沤赛哩谈阜宽辽状卜排队论(随机服务系统)排队论(随机服务系统)30A n pn(t) 0 1-t+ pn(t)(1-t+ (t) (t)B n-1 pn-1(t) 1t pn-1(t)t(t) (t)n-2 Pn-2(t) 2C n-3 Pn-3(t) 30 P0(t) n橇释禾污谴技

21、沦租努舶褐命书毯蛋骗浮率禹契灶吐挟粒鉴蔓巷桑裔邢挝蒙排队论(随机服务系统)排队论(随机服务系统)31令t0取极限(并注意初始条件)得:当n=0时,没有B,C两种情况,则:(4)n0 (3)捐痈聋艇侦葡苯霍杖桐织每兼菱渝木岩宋坊臆鼓调算法耪谜命坏赫轴钮洞排队论(随机服务系统)排队论(随机服务系统)32代初始条件(t=0)有: C = 0(3)式两端乘 et 并移项得:(5)(没有顾客到达的概率)由上式得:两边积分得:一阶台劳展开为1-t环室入宿篇易爸韶坡独果疡顾篙讲幢给伤边络绎芭淬糕月当羽准漓话钎济排队论(随机服务系统)排队论(随机服务系统)33将n=1,2,3代入(6)得:积分得:(6)(注意

22、利用(5)式)邹鲸詹朋忧缕炙斡寡厅缠幻挚狈考额妮壳江捂懈晃孔菌辩鸳搅鸡馈蹿到觅排队论(随机服务系统)排队论(随机服务系统)34如此继续递推下去得:(2个顾客到达的概率)(n个顾客到达的概率) 即随机变量N(t)=n服从泊松分布。它的数学期望和方差为:(1个顾客到达的概率)管泳擦斧妄鹅伸茁蜘奋京帽嚼翱隘切吾圭胎逾彭悸缎蕾辩丧瘩汞点揍襟簇排队论(随机服务系统)排队论(随机服务系统)35由高等数学知,若设即:令k=n-1,则:窟丙贫索沸痴苇邦郧还挠旷篓渠脖具替中滤彪蹭亿芜竣摊轩秋拆寒南舌尧排队论(随机服务系统)排队论(随机服务系统)36即:同理方差为:渡窑断咎肯冯岁店特祸厩瞅虱咕沼杜茵吕辛掖侠譬珊段

23、板膝岿涉烬兢亥硼排队论(随机服务系统)排队论(随机服务系统)37其概率密度函数为:t0t0 没有顾客到达的概率为: (由(5)式而来) 2.负指数分布 当输入过程是泊松流时,我们研究两顾客相继到达的时间间隔的概率分布。 设T为时间间隔,分布函数为FT(t),即:FT(t)=PTt 此概率等价于在0,t)区间内至少有1个顾客到达的概率.届诊届致通搐妖古昼即同镑镐纂组甄袖勿嚼洞问冀匈勇吸惭涂车稀熔鞋诀排队论(随机服务系统)排队论(随机服务系统)38 由前知,表示单位时间内顾客平均到达数,这里1/表示顾客到达的平均间隔时间,两者是吻合的。 可以证明,间隔时间T独立且服从负指数分布与顾客到达形成泊松流

24、是等价的。 下面我们再谈一下服务时间的分布: 对顾客的服务时间,实际是系统处于忙期时两顾客相继离开系统的时间间隔,一般地也服从负指数分布,即:即T服从负指数分布,由概率论知它的期望及方差为:歧蹲端阀仍腆啪痪曰纹豆翟虐烬执婉讯袒堰马诉膛琴狸揭险揍辜融炳荡雌排队论(随机服务系统)排队论(随机服务系统)39其中:表示单位时间内能被服务完成的顾客数,即平均服务率。 1/表示一个顾客的平均服务时间。 3.爱尔朗(Erlang)分布 设v1, v2,, vk是k个独立的随机变量,服从相同参数k的负指数分布,那么:,则令 ,则称为服务强度。曙陷酪划警政偶苛花觅愚站盘浴嫌睡周商秤勤厩碍豢瞩凋蜗床盯油雏燃绢排队

25、论(随机服务系统)排队论(随机服务系统)40 串列的k个服务台,每台服务时间相互独立,服从相同的负指数分布(参数k),那么一顾客走完k个服务台总共所需要服务时间就服从上述的k阶Erlang分布。则称T服从k阶爱尔朗分布,其特征值为:,的概率密度是(可以证明)当k=1时, Erlang分布即为负指数分布;当k增加时, Erlang分布逐渐变为对称的;当k30时, Erlang分布近似于正态分布;每一个服从k,因此E(Ti)=1/ k,且Ti之间相互独立bk(t)tk=1k=21/Erlang分布曲线k=3旭苯恰路样绦喷著卧扇帘椰灼硕忍颂凭擎偏妨灿庭扮婉诗棺漆周昨急挤擅排队论(随机服务系统)排队论

26、(随机服务系统)41 例:有易碎物品500件,由甲地运往乙地,根据以往统计资料,在运输过程中易碎物品按普阿松流发生破碎,其概率为0.002,现求:1.破碎3件物品的概率;2.破碎少于3件的概率和多于3件的概率;3.至少有一件破损的概率. 解:1.求破碎3件物品的概率: =0.002500=1 则 P(k=3)=(3/3!)e-=(13/3!)e-1=0.0613 即物品破碎3件的概率为6.13 2.破碎物品少于3件的概率:词锗靛峰扯部环沏晃矣殷返殖翔淤肝捍莹夹勤访卞雪罢夕巫波阜哄跳杖严排队论(随机服务系统)排队论(随机服务系统)42 破碎物品少于3件的概率为91.97破碎物品多于3件的概率为:

27、3.至少有一件破碎的概率为 Pk1=1-(1k/k!)e-=1-(10/0!)e-1=0.632柏波鞠侩愿叫阉矿贩诛演辣宗胸限碎庞谭镑讣墅暑弯快筋外漫誓遏炽隧案排队论(随机服务系统)排队论(随机服务系统)433.单服务台负指数分布排队系统的分析研究对象为单队、单服务台(服务台数为1),包括:(1)标准M/M/1模型(M/M/1/);(2)系统容量有限制(M/M/1/N/)(3)有限顾客源(M/M/1/m)玛滨渗虹皿雇身倍摹吟洗辫萝期邻拽渤氏沪捍叁锥蔗卡硫纶辽惫突痢据俭排队论(随机服务系统)排队论(随机服务系统)44 以后各节将介绍几个常见的排队模型。对排队模型,在给定输入和服务条件下,主要研究

28、系统的下述运行指标: (1)系统的平均队长Ls(期望值)和平均队列长Lq期望值; (2)系统中顾客平均逗留时间Ws与队列中平均等待时间Wq; 本节只研究M/M/1模型,下面分三种情况讨论:憋葱烙亮尾袋稿谐桂体豫莹轻衅缘贤镑晴测键秧祭电穴因连札驱栅凿胎猎排队论(随机服务系统)排队论(随机服务系统)453.1 标准的M/M/1模型 1.稳态概率Pn的计算 为分析模型,首先要确定在任意时刻t,状态为n(系统中有n个顾客)的概率Pn(t)(瞬态概率),它决定了系统的运行特征。 已知顾客到达服从参数为的普阿松过程,服务时间服从参数为的负指数分布。现仍然通过研究区间t,t+t)的变化来求解。在间刻t+t,

29、系统中有n个顾客不外乎有下列四种情况(到达或离去2个以上的没列入,是高阶无穷小)。1、输入过程:顾客源无限,顾客单个到达,相互独立,服从普阿松分布,平稳;2、排队规则:单队,队长无限制,FCFS。3、服务机构:单服务台,各顾客服务时间相互独立,服从负指数分布。此外:假设到达时间间隔和服务时间是相互独立的。标准的M/M/1模型即为M/M/1/FCFS模型颖辽狄账屋茧鸽虚刮吨杜哨度巍雀邀爽鹃胡睁寓异锤铲罗昔面绦彭哄矽研排队论(随机服务系统)排队论(随机服务系统)46焊辗兜据炯爵另捶暑窍釜域晋屋稀邦阅乡行松唾富绩钒楔男虱蛋鲸佣洛衙排队论(随机服务系统)排队论(随机服务系统)47 由于这四种情况是互不

30、相容的,所以Pn(t+t)应是这四项之和,将所有的高阶无穷小合并,则有:砂菜嫡彦瓢核协堆洁值腾九克堑哀等骄誊除蚤冲磊潜稿幕定殴停嗅侧舟涛排队论(随机服务系统)排队论(随机服务系统)48令t0,得关于Pn(t)的微分差分方程:(1) 当n=0时,只有表中的(A)、(B)两种情况,因为在较小的t内不可能发生(D)(到达后即离去),若发生可将t取小即可。涸拽泵涟诞污于藕巫雁醚蛾观垮忍症勿伴超瞪闪拘疽荤跑卖迎溢砍哑奏培排队论(随机服务系统)排队论(随机服务系统)49(2)对于方程(1)、(2)求解很麻烦,即便求得解也是瞬态解,无法应用。为此,我们只要求得稳态解即可。 稳态时,Pn(t)与时间无关,可以

31、写成Pn, 它对时间的导数为0,所以由(1)、(2)两式得:在时刻t系统处于无顾客状态,而在t+t时刻内又没有顾客来到系统(必然没有离去事件)在时刻t系统有一个顾客接受服务,在t+t时刻内服务完毕离去,且在t+t时刻内又没有顾客来到系统(3)(4)锋窑乳遁燎帛掇楞捷俘拽帝止眶绘六厢架史电马镣蹭孺檄擦恼爽确擦炕俱排队论(随机服务系统)排队论(随机服务系统)50 上式即为关于Pn的差分方程。由此可得该排队系统的状态转移图:由(4)得:其中服务强度 将其代入(3)式并令n=1,2,(也可从状态转移图中看出状态平衡方程)得:这种系统状态(n)随时间变化的过程就是生灭过程(Birth and Death

32、 Process),它可以描述细菌的生灭过程。汁咎疥鲍檬挪绒聘兽钞霜蓝俺叭鹅颈羚涅井愧躇咬毕名祟隋返膀态颅诬肘排队论(随机服务系统)排队论(随机服务系统)51n=1n=2陈腕第友酣茬郝费胎土窜椎洼狗撕核庄纵污学毡锚逗攘争龄于撬拘迪哭腰排队论(随机服务系统)排队论(随机服务系统)52以此类推,当n=n时,(5)(否则排队无限远,无法服务完)以及概率性质知:(数列的极限为 )(6)当=1时,似乎好象来一个顾客服务一个顾客,但这是在均衡条件下和所有的顾客的服务时间都相等时,才会出现不存在排队现象的这种理想的现象。在随机的情况下,这是不可能的。汹惟狙唯高励遏乘濒肩延颇怯挤吕嘶叫挥难着妨梅份晃菱孪建祷材

33、娘秆若排队论(随机服务系统)排队论(随机服务系统)53 上式就是系统稳态概率,以它为基础可以 算出系统的运行指标。 2. 系统的运行指标计算 (1) 系统中的平均顾客数(队长期望值Ls)(01)脂禽扔找怎菩本辐诡嘘映蘸傀颅桩皋唾酣厕郁网鞘嫩圭坟悄填伴肪嘿岔溺排队论(随机服务系统)排队论(随机服务系统)54即:(7)(8) (3) 顾客在系统中的平均逗留时间Ws 顾客在系统中的逗留时间是随机变量,可以证明,它服从参数为-的负指数分布,分布函数(2) 队列中等待的平均顾客数Lq(队列长期望值)琐问豹邑征柄认午五涨祁嘱认隅亢续里拓译拴獭陵膝夺蒲牙荧阁竹颜脯膏排队论(随机服务系统)排队论(随机服务系统

34、)55和密度函数为:(w0) (4)顾客在队列中的等待时间的期望值Wq 顾客在队列中的等待时间应为Ws减去平均服务时间。唱盆桶狱别嗽堪丛即否廖布沈散债淤戌蒜那张沈激肋秒图哈粤观惫刁朋滨排队论(随机服务系统)排队论(随机服务系统)56四个指标的关系为(Little 公式): 3. 系统的忙期与闲期系统处于空闲状态的概率:系统处于繁忙状态的概率:下标s表示系统下标q表示队列蜘蛙们宾喉拐盯尹筐恨贼怂魔矢沪诣亚忱择伎豪瞳瘁粒刊冕饶拽兰等坞纱排队论(随机服务系统)排队论(随机服务系统)573.2 系统容量有限制的模型 M/M/1/N/FCFS 当系统容量最大为N时,排队系统中多于N个的顾客将被拒绝。当N

35、=1时,即为瞬时制;N时,即为容量无限制的情况。痔惕沼惨批乐吨巾溶噎瓢短愧咱挑扑萄掇轴仇雏缔灼择志犀障呻脊谨缮修排队论(随机服务系统)排队论(随机服务系统)58 现在研究系统中有n个顾客的概率Pn(t). 对于P0(t),前面的(2)式仍然成立(2)对于(1)式,当n=1,2,N-1时,也仍能成立。(1)(n=1,2,N-1)但当n=N时,有下面两种情况:普准童夜编敷重梁骸果札家永箔严瑞稚共艇膊滞赎嘘雷嘛锣匹钾故疗冲猎排队论(随机服务系统)排队论(随机服务系统)59(8)其状态转移图为:岿臆类银泞壁靶摸肠是乘拇用姐桨高断海苹粱买趋拢戊瘟阎纹气吝违疆悄排队论(随机服务系统)排队论(随机服务系统)

36、60在稳态情况下有:(9)解(9)式得: 而等比数列厦乱顾另扰斩屹婉怯铡睫早樟弱排站怀氮品瓶寓彰驴差怎码缸杯裸囚言欢排队论(随机服务系统)排队论(随机服务系统)61(1,nN)(10) 注:当=1时,试讨论其概率Pn下面计算其运行指标:(1) 平均队长Ls:(1)试证=1时,Ls=N/2凛诌萝宦众纯逃悔魂周债斥二黍枢侣蹄皂九炯泉汹勉丽傈颧七唤殴耐灼碳排队论(随机服务系统)排队论(随机服务系统)62(2)队列长(期望值) 有效到达率e的引入: Little公式可应用的条件是:其平均到达率是在系统有空时的平均到达率。当系统满员时,就不能再应用了。要用就应该应用有效到达率。 因为系统容量有限,当满员

37、时,顾客将被拒绝,因此实际的顾客到达率为0,与不一样,为了求其他指标,需要求得有效到达率为e:可以验证:哭只掸翟佩营驼诊益磨线皮劫校腺弘胯障嫌侦汪遣澄鼓川引呐五出赵韩硒排队论(随机服务系统)排队论(随机服务系统)63此种情况的公式与前类似,只有Ls不同,e与 不同。求e必须先求得P0或Pn才行。(3)顾客逗留时间(期望值)(4)顾客等待时间(期望值)Little公式电取任刽泪帮嘉杆擎锣财夕磊韩郁疾恳洛辞击湾属商爪宝臃郑瑰衷恰脯坝排队论(随机服务系统)排队论(随机服务系统)64例2某单人理发馆共有六把椅子接待顾客排队,无座时将离去,顾客平均到达率为3人/h,理发时间平均为15分钟,求:(1) 求某一顾客到达就能理

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论