排队论(QueuingTheory).ppt
《排队论(QueuingTheory).ppt》由会员分享,可在线阅读,更多相关《排队论(QueuingTheory).ppt(46页珍藏版)》请在三一办公上搜索。
1、2023/9/10,1,排队论(Queuing Theory),排队论(queuing),也称随机服务系统理论,是运筹学的一个主要分支。1909年,丹麦哥本哈根电子公司电话工程师A.K.Erlang的开创性论文“概率论和电话通讯理论”标志此理论的诞生。排队论的发展最早是与电话、通信中的问题相联系的,并到现在是排队论的传统的应用领域。近年来在计算机通讯网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到应用。,2023/9/10,2,1.1 排队系统的组成与特征 排队系统一般有三个基本组成部分:1.输入过程;2.排队规则;3.服务机构。现分别说明:,1 排队论的基本概念,2023
2、/9/10,3,输入即为顾客的到达,可有下列3种情况:1)顾客来源。顾客总体(称为顾客源)的组成可能是有限的,也可能是无限的。如,上游河水流入水库可以认为总体是无限的,工厂内停机待修的机器显然是有限的总体。2)顾客到达方式。顾客到来的方式可能是一个一个的,也可能是成批的。如,到餐厅就餐就有单个到来的顾客和受邀请来参加宴会的成批顾客。,1.输入过程,2023/9/10,4,3)顾客流的概率分布。顾客随机一个(批)个(批)来到排队系统,顾客流的概率分布用来描述相继到达的顾客之间的间隔时间分布是确定的还是随机的,分布参数是什么,到达的间隔时间是否独立,分布是随时间变化的还是平稳的。,2023/9/1
3、0,5,2.排队规则,1)损失制。顾客到达时,如果所有的服务台都被占用,且服务机构又不允许顾客等待,顾客只能离去,这种服务规则就是损失制。2)等待制。当顾客到达时,如果所有服务台都被顾客占用而无空闲,这时该顾客自动加入队列排队等待服务,服务完才离开。(1)先到先服务 FCFS(2)后到先服务 LCFS(3)随机服务RAND(4)有优先权服务 PR。,2023/9/10,6,3.服务机构,1)服务机构可以是单服务员和多服务员服务,这种服务形式与队列规则联合后形成了多种不同队列,不同形式的排队服务机构,如:,2023/9/10,7,2)服务方式分为单个顾客服务和成批顾客服务。3)服务时间分为确定型
4、和随机型。4)服务时间的分布在这里我们假定是平稳的。,2023/9/10,8,上述特征中最主要的、影响最大的是:顾客相继到达的间隔时间分布服务时间的分布服务台数,1953提出了分类法,称为Kendall记号(适用于并列服务台)即:X/Y/Z:A/B/C,1.2 排队系统的模型分类,2023/9/10,9,式中:X顾客相继到达间隔时间分布。M负指数分布Markov,D确定型分布Deterministic,EkK阶爱尔朗分布Erlang,GI 一般相互独立随机分布(General Independent),G 一般随机分布。Y服务时间分布(与上同)Z并列的服务台数A排队系统的最大容量B顾客源数量
5、C排队规则 如 M/M/1:/FCFS即为顾客到达为泊松过程,服务时间为负指数分布,单台,无限容量,无限源,先到先服务的排队系统模型。,2023/9/10,10,系统指标:(1)队长,指在系统中的顾客数,它的期望值记Ls;(2)排队长,指在系统中排队等待服务的顾客数,它的期望值记作Lq,一般情形,Ls(或Lq)越大,说明服务效率越低。,2023/9/10,11,(3)逗留时间,指一个顾客在系统中的停留时间,它的期望值记作Ws;(4)等待时间,指一个顾客在系统中排队等待的时间,它的期望值记作Wq;,2023/9/10,12,1.3 排队论研究的基本问题 1.排队系统的统计推断:即通过对排队系统主
6、要参数的统计推断和对排队系统的结构分析,判断一个给定的排队系统符合于哪种模型,以便根据排队理论进行研究。2.系统性态问题:即研究各种排队系统的概率规律性,主要研究队长分布、等待时间分布和忙期分布等统计指标,包括了瞬态和稳态两种情形。3.最优化问题:即包括最优设计(静态优化),最优运营(动态优化)。,2023/9/10,13,1.4 排队问题求解(主要指性态问题),求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标,估计服务质量,确定系统的合理结构和系统参数的合理值,以便实现对现有系统合理改进和对新建系统的最优设计等。排队问题的一般步骤:1.确定或拟合排队系统顾客到达的时间间隔分布和
7、服务时间分布(可实测)。2.研究系统状态的概率。系统状态是指系统中顾客数。状态概率用Pn(t)表示,即在t时刻系统中有n个顾客的概率,也称瞬态概率。,2023/9/10,14,求解状态概率Pn(t)方法是建立含Pn(t)的微分差分方程,通过求解微分差分方程得到系统瞬态解,由于瞬态解一般求出确定值比较困难,即便求得一般也很难使用。因此我们常常使用它的极限(如果存在的话):,稳态的物理意义见右图,系统的稳态一般很快都能达到,但实际中达不到稳态的现象也存在。值得注意的是求稳态概率Pn并不一定求t的极限,而只需求Pn(t)=0 即可。,称为稳态(steady state)解,或称统计平衡状态(Stat
8、istical Equilibrium State)的解。,2023/9/10,15,排队论主要知识点,排队系统的组成与特征排队系统的模型分类顾客到达间隔时间和服务时间的经验分布与理论分布稳态概率Pn的计算标准的M/M/1模型(M/M/1:/FCFS)系统容量有限制的模型M/M/1:N/FCFS顾客源有限模型M/M/1/M/FCFS标准的M/M/C模型M/M/C:/FCFS,2023/9/10,16,M/M/C型系统和C个M/M/1型系统系统容量有限制的多服务台模型(M/M/C/N/)顾客源为有限的多服务台模型(M/M/C/M)一般服务时间的(M/G/1)模型Pollaczek-Khintch
9、ine(P-K)公式定长服务时间 M/D/1模型爱尔朗服务时间M/Ek/1模型排队系统优化M/M/1 模型中的最优服务率u标准的M/M/1Model系统容量为N的情形M/M/C模型中最优服务台数C,2023/9/10,17,2 到达间隔时间分布和服务时间的分布,一个排队系统的最主要特征参数是顾客的到达间隔时间分布与服务时间分布。要研究到达间隔时间分布与服务时间分布需要首先根据现存系统原始资料统计出它们的经验分布,然后与理论分布拟合,以确定属于哪种分布理论,并估计它的参数值。,2023/9/10,18,3.1 经验分布,经验分布是对排队系统的某些时间参数根据经验数据进行统计分析,并依据统计分析结
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排队 QueuingTheory
链接地址:https://www.31ppt.com/p-5980170.html