六-排队论.ppt
《六-排队论.ppt》由会员分享,可在线阅读,更多相关《六-排队论.ppt(96页珍藏版)》请在咨信网上搜索。
1、第六章 随机服务系统理论确定型只是随机现象的特例排 队 论Queuing TheoryQueuing Theory1.6.1 随机服务系统基础系统的输入与输出是随机变量A.k.Erlang 于19091920年发表了一系列根据话务量计算电话机键配置的方法,为随机服务理论奠定了基础又称为排队论(Queuing Theory)或拥塞理论(Congestion Theory)应用广泛交通行业应用:交叉口/高速收费站/机场航班2.顾客来源队 列服务机构排队系统顾客服务完离开排队系统的三个基本组成部分.输入过程(顾客按照怎样的规律到达);排队规则(顾客按照一定规则排队等待服务);服务机构(服务机构的设置
2、,服务台的数量,服务的方式,服务时间分布等)6.1.1 基本要素3.输入过程顾客源有限无限经常性的顾客来源顾客到达间隔时间:到下一个顾客到达的时间服从某一概率分布(确定型/随机型)顾客的行为假定在未服务之前不会离开 当看到队列很长的时候离开从一个队列移到另一个队列4.排队服务规则队列容量有限/无限排队规则损失制等待制:先到先服务(FCFS),后到先服务(LCFS),随机服务(RS),优先权服务(PS)混合制逐个到达,成批服务;成批到达,逐个服务5.单通道和多通道并联服务串联服务串并联服务服务机构的组织方式与服务方式123顾客到达顾客离开123顾客到达顾客离开顾客离开顾客离开银行服务-叫号系统1
3、23顾客到达顾客到达顾客到达顾客离开顾客离开顾客离开机场安全检查通道6.u常用符号M泊松分布(负指数分布)Ekk阶爱尔朗分布D确定型分布G一般分布M/M/1/K/FCFSM/M/1/K/FCFS顾客到达服从泊松分布,顾客的服务时间服从负指数分布,单通道,系统容量有限(K K)而顾客源无限,先到先服务的排队系统顾客到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量/顾客总体数量/排队规则 (扩充的Kendall Kendall 符号)-)-Kendalls notation 6.1.2 符号表示7.队长:系统中的顾客数量的期望值排队长:系统中正在等待的顾客数量期望值逗留时间:
4、顾客在排队系统中的总时间(等待时间与被服务时间之和)的期望值排队时间:顾客的排队等待时间的期望值忙期:服务机构连续繁忙的时间长度服务强度:顾客到达率的期望值与服务率的期望值之比6.1.3 排队系统营运指标8.服务系统存在来自两个矛盾方面的要求顾客希望服务质量好,如排队等待时间短,损失率低系统运营方希望设备利用率高给用户一个经济上能够承受的满意的质量哪些系统特性会影响系统的性能?服务机构的组织方式与服务方式顾客的输入过程和服务时间分布系统采用的服务规则 与服务系统性能相关的特性9.6.2 顾客到达分布和服务时间分布 6.2.1 概述顾客的服务时间由于多种原因具有不确定性,最好的描述方法就是概率分
5、布;同样顾客到达的间隔时间也服从一定的概率分布10.若统计区间分得越细,样本越多,则经验分布的轮廓越接近曲线经验分布一般采用直方图来表示,如下图Frequency Distribution服务时间和到达间隔时间服从什么分布?可以先通过统计得到经验分布,然后再做理论假设和检验11.6.3.2 输入过程(顾客到达分布)可用相继到达顾客的间隔时间描述,也可以用单位时间内到达的顾客数描述间隔时间服从定长分布(Deterministic Distribution)间隔时间服从爱尔朗分布(Erlang distribution)二项分布(binomial distribution)单位时间 t(或时间区间
6、t)内到达的顾客数服从泊松分布(法国数学家Poisson,1836)最简单流(泊松流)(Poisson Distribution)负指数分布(Negative Exponential Distribution)12.6.3.2.1 最简单流(泊松流)-纯生过程(1)泊松流形成条件流的平稳性 对于任意的t0t0及t0t0,在时间区间(t,t+(t,t+t)t)内有n n个顾客到达的概率只与t t有关,与时间区间的起点t t无关。当t t充分小时,在(t,t+(t,t+t)t)内有一个顾客到达的概率与t t成正比,即其中,O(O(t)t)是当t 0t 0时,关于t t高阶无穷小;为单位时间内的顾客
7、到达平均数。13.在时间轴上,互不相交的时间区段 和 内,顾客的到达数是相互独立的,即前一顾客的到达不影响后一顾客的到达。流的无后效性当 t 充分小时,在 t 时间内到达一个顾客的概率为 t+o(t),到达两个或两个以上顾客的概率为 o(t);即两个顾客不可能同时到达流的普遍性14.设把长为t t的时间区间分成m m等分,每段长度为 。若在dtdt内,有一个顾客到达,则称被“占着”,如果在dtdt内,没有顾客到达,则称为“空着”。u被“占着”的概率近似为u被“空着”的概率近似在长为 t t 的时间区间内,到达n n个顾客的概率根据流的无后效性,在m m个dtdt中,有顾客到达与没有顾客到达可以
8、看成是m m次独立的试验 (2)泊松流详解15.在长为 t 的时间区间内,到达n个顾客的概率在m m个dtdt中,有n n个dtdt被顾客“占着”的概率 利用二项定律 16.dt0,m 17.符合最简单流(泊松流)的随机事件发生规律单位时间t 内有n个顾客到达的概率顾客的平均到达率(3)泊松分布18.(4)泊松输入过程及其特点1)平稳性:顾客到达数只与时间区间长度有关2)无后效性:不相交的时间区间内所到达的顾客数是独立的3)普遍性:在 t 时间内到达一个顾客的概率为 t+o(t),到达两个或两个以上顾客的概率为 o(t);即两个顾客不可能同时到达泊松过程具有可迭加性即独立的泊松分布变量的和仍为
9、泊松分布19.泊松过程的到达间隔时间为负指数分布令 h 代表间隔时间,则概率 Ph t代表时间区间t 内没有顾客来的概率;由泊松分布 可知:P0(h t)=Ph t=et故间隔时间 h 的分布为 P h t=1 et(1)推导n=06.3.2.2 负指数分布20.(2)负指数分布的特点负指数分布之所以常用,是因为它有很好的特性,使数学分析变得方便无记忆性。指的是不管一次服务已经过去了多长时间,该次服务所剩的服务时间仍服从原负指数分布21.如果顾客的到达过程服从最简单流,则顾客单位时间内的到达数服从泊松分布。如果顾客的到达过程服从最简单流,则顾客到达的时间间隔服从负指数分布。从本质上看,泊松分布
10、与负指数分布是同一个过程的不同表现形式。可适用于服务时间分布6.3.3 小结22.负指数分布泊松分布在单位时间t内,到达n个顾客的概率顾客到达时间间隔大于单位时间t t的概率顾客到达时间间隔小于单位时间t t的概率顾客的平均到达率23.例-1-1 一售货员出售两种商品A和B,每日工作 8 小时。购买每种商品的顾客到达过程为泊松分布,到达率分别为 A=8人/日,B=16人/日,试求:(1)1小时内来到顾客总数为 3 人的概率;(2)三个顾客全是购买B类商品的概率。解:(1)总到达率为 A+B=24人/日,1 小时=1/8 日,故(2)3 个顾客全是购买 B 类商品的概率为24.例-2-2 某铁路
11、与公路相交的平面交叉口,当火车通过交叉口时,横木护栏挡住汽车通行。每次火车通过时,平均封锁公路3min,公路上平均每分钟有4辆汽车到达交叉口。求火车通过交叉口时,汽车排队长度超过100m的概率(即排队汽车超过12辆的概率)。25.HomeworkHomeworkP186 226.研究系统内部状态变化的过程系统状态i i状态i+1i+1状态i-1i-1在t t时刻内发生两个或两个以上事件的概率为O(O(t)t)一个事件一个事件t0t0,O(O(t)0t)06.4 生灭过程(Birth and Death Processes)6.4.1 定义 系统具有0,1,2,0,1,2,个状态。在任何时刻,若
12、系统处于状态i i,并且系统状态随时间变化的过程满足以下条件,称为一个生灭过程:N(t)N(t)表示时刻t t系统中的顾客数。N(t)N(t),t t0 0为一随机过程。27.(1)(1)在(t,t+t,t+t t)内系统由状态i i转移到状态i+1i+1的概率为 i it+O(t+O(t)t)平稳性条件(2)(2)在(t,t+t,t+t t)内系统由状态i i转移到状态i-1i-1的概率为 i it+O(t+O(t)t)平稳性条件t t内有一个顾客离开的概率t t内有一个顾客到达的概率(3)(3)在(t,t+t,t+t t)内系统发生两次以上转移的概率为 O(O(t)t),即有2 2个以上顾
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排队
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。