第八章排队论.ppt
《第八章排队论.ppt》由会员分享,可在线阅读,更多相关《第八章排队论.ppt(62页珍藏版)》请在三一办公上搜索。
1、运筹帷幄之中,决胜千里之外,运 筹 学,中原工学院机电学院主讲:丁剑飞,Chapter 8 排队论(Queuing Theory),排队论的基本概念单服务台系统多服务台系统,本章主要内容:,引言,在人们生活和生产的实践活动中,经常会遇到拥挤现象,从而产生排队。为了获取较好的经济效益,有必要研究排队现象的规律性。要求得到服务的对象统称为顾客;顾客不仅可以是人,也可以是物。例如等待加工的零件,出故障等待维修的机器等都是顾客。提供服务的对象称为服务机构。顾客和服务机构形成了一个服务系统。例如到医院就医的患者和医院;出现故障的机器和及机器维修班组等,都是服务系统。顾客到达服务机构,当然是希望立即得到服
2、务。然而服务机构已经占满时,例如理发店的座位已满,维修班组已忙于维修机器,再到的顾客只能排队等候或者消失,这样造成的损失称为排队费用。例如机器的停工损失,在仓库的存储,排队论的基本概念,费用,因等候而降低的价值等,都属于排队费用。排队的时间越长,排队费用越大。另一方面,设立的服务机构越多,服务效率越高,需要支付的费用也越大,然而却可以减少排队时间。如何根据顾客的实际情况,设立适当的服务机构,以使得服务费用和排队费用总和最少,是排队论所要讨论和解决的问题。8.1 排队论的基本概念顾客到达服务机构,依照一定的规律等待,然后接受服务,服务完毕后离去。这个过程称为服务过程。,引言,如果顾客到达和接受服
3、务的时间都具有随机性,那么这个服务系统就称为随机服务系统,又称为排队系统;服务过程称为排队过程。一个排队过程,大体分为三个基本部分:输入过程、排列规则、服务机构。,输入过程,排队规则,服务机构,排队论的基本概念,一、输入过程对于排队系统,顾客是输入。输入过程是指顾客按怎样的规律到达服务机构。顾客来源的总体称为顾客源。例如待修机器和维修班组所形成的排队系统,工厂的全部机器是顾客源;对于到理发店来理发的顾客来说,全体居民是顾客源,等等。顾客源可以是无限集合,也可以是有限集合。顾客可能单个到达,也可能是成批到达,或者是接连不断地到达。本章我们主要讨论称为泊松流或者最简单流的到达方式。1.泊松流(记为
4、M)顾客的输入过程如果具备以下三个特点,则称为泊松流。,排队论的基本概念,(1)平稳性 对于任何t0和非负整数k,在区间(a,a+t内有k个顾客到达系统的概率对任何a0都是相等的。也就是说,这个概率只与t和k有关,而与a有关。我们以vk(t)记这个概率,以x(t)记在长为t的时间段内到达的顾客数,则有(2)无后效性 在时间区间(a,a+t内到达k个顾客的概率与时刻a以前系统的状况无关。就是说,事件(x(t)=k)与a以前系统所发生的事件相互独立。(3)普通性 记 为在时间段t内,到达两个和两个以上顾客的概率,即,则有t0时,。,排队论的基本概念,实际上,许多排队系统的输入过程都近似满足这些特征
5、。可以证明,凡是具备上述3个特征的输入过程,x(t)都是服从泊松分布的随机变量。即x(t)的期望值和方差分别为Ex(t)=t,Varx(t)=t。若取t=1,则Ex(1)=。这即是说,表示单位时间内到达系统顾客数的平均值,称为顾客的到达率或输入率。还可以证明,如果顾客的到达数服从泊松分布,那么它一定满足上述的3个特性。,(8.1),排队论的基本概念,2.定长输入(记为D)流水线上定时送往包装机的成品,其输入过程就是定长输入。如果规定的产品到达的间隔时间为c,则相继到达产品间隔时间t的分布函数为3.k阶爱尔朗分布(记为Ek)设t1,t2,tk是k个相互独立的,且具有相同参数的负指数分布随机变量,
6、则随机变量t=t1+t2+tk服从k阶爱尔朗分布,t的密度函数为,(8.2),排队论的基本概念,随机变量t的期望值和方差分别为:例如,如果顾客连续接受串联的k个服务台的服务,各服务台的服务时间相互独立,且均服从参数为的负指数分布,则顾客接受k个服务台总共所需的时间就服从k阶爱尔朗分布。,(8.3),排队论的基本概念,4.一般独立输入(记为GI)如果各相继到达顾客的间隔时间t1,t2,是相互独立的同分布的随机变量,那么称为一般独立输入。二、排队规则所谓排队规则,就是到达服务机构的顾客,若不能立即得到服务,应按怎样的方式等待接受服务。1.等待制顾客到达后,如果服务机构已经占满,当允许顾客等待时,再
7、到的顾客便排队等待。常见的有以下几种排队方式:,排队论的基本概念,(1)先到先服务 这是最普遍的情形。(2)后到先服务 许多存储系统运用这种规则。(3)随机服务 当一名顾客服务完毕离去时,随机地从等待的顾客中选择一名进行服务。等待中的每位顾客被选中的概率是相等的,例如电话订票服务。(4)优先服务 对于不同的顾客规定不同的优先权,具备较高优先权的顾客优先接受服务。2.消失制当服务机构已经全部占满时,再到的顾客不能进入服务系统,顾客自动消失,也就是不允许排队的情形。对于消失制的情形,不存在排队现象。主要考虑的是顾客消失的概率和服务机构的利用率。,排队论的基本概念,3.混合制等待制的排队方式可以认为
8、排队的队伍长度没有限制。当允许排队、但服务机构的空间和排队时间有限时,队伍长度必然有一定的限制,这种情形称为混合制。(1)等待空间有限 若服务机构最多只能容纳k个顾客,当顾客少于k时,再来者可以排队等待,当顾客等于k时,再来的顾客就自动消失。(2)等待时间有限 若顾客从进入系统开始,到开始接受服务为止,这段等候的时间称为等待时间,也就是顾客在排队系统中排队所占的时间。当顾客的等待时间有限时,到时若不能得到服务,那么顾客就会自动消失。(3)逗留时间优先 顾客从进入系统到接受服务完毕离开,排队论的基本概念,这段时间称为逗留时间。也就是说,逗留时间等于等待时间加接受服务的时间。三、服务机构服务机构中
9、可能是单服务台,也可能是多服务台。当有多个服务台时,排队的顾客可以排成一个队,依次到空出的服务台去接受服务;也可以每个服务台前排成一队,且一旦排好后,不能再更换。,排队论的基本概念,本章首先讨论单服务台的情形。由于顾客的情形不同,服务所需要的时间(称为服务时间)T也不同,因此T是个随机变量。最常见的情形是T服从负指数分布,即T的概率密度函数为,(8.4),排队论的基本概念,其中参数0。T的分布函数为对于服从负指数分布的时间T,有一个特性,就是不论过去已经服务多久,如果到现在仍然没有服务完毕,那么剩余的服务时间仍具有原来的概率分布。即对任何t,0,(8.5),(8.6),排队论的基本概念,这个性
10、质称为无后效性或马尔科夫性。可以证明,凡是具有这个性质的随机变量,必须服从负指数分布。对于负指数分布,其期望和方差分别为:这就是说,表示在单位时间中可以为多少个顾客服务完毕,称为服务率。现举一例。设一个顾客到达服务机构后,有c个服务率都为的服务台同时为其服务,只要有一个服务台完成服务过程,那么整个服务就结束。例如c个命中率相同的射手对一个目标进行射击,只要有一名射手射中,那么目标就被消灭。由于,(8.7),排队论的基本概念,这个结果表明参加工作的服务台越多,平均所需要的服务时间越短。四、排队系统的分类D.G.Kendall 在1953年提出一个分类方法,按照上述各部分特征中最主要的,影响最大的
11、三个,即:(1)相继顾客到达间隔时间的分布;(2)服务时间分布;,排队论的基本概念,(3)服务台个数。按照这三个特征分类,并利用一定符号表示,称为Kendall记号。这只对并列的服务台(如果服务台多于一个的话)的情形,他使用的符号形式是X/Y/Z其中,X处填写表示相继到达的间隔时间分布的记号:Y处填写表示服务时间分布的记号;Z处填写并列的服务台数目。表示相继到达间隔时间和服务时间的各种分布符号是:M负指数分布(M是Markov的字头,因为负指数分布具有无记忆性,即Markov性);,排队论的基本概念,D确定型(Deterministic)Ekk阶爱尔朗(Erlang)分布;GI一般相互独立(G
12、eneral Independent)的时间间隔的分布;G一般(General)服务时间的分布。后来,在1971年一次关于排队论符号标准化会议上,又将Kendall符号扩充变为 X/Y/Z/A/B/C其中前三项意义不变,而A处填写系统容量限制N,B处填写顾客源数目m,C处填写服务规则,例如先到先服务FCFS,后到先服务LCFS等,并约定,如约去后三项,即指X/Y/Z/FCFS的情形。,排队论的基本概念,五、主要的数量指标经常运用以下几个数量指标来评价一个排队系统。1.队伍长度在排队系统中的平均顾客数,称为队伍长度,简称队长,这是顾客和设计人员都关心的问题。队长的大小直接关系到顾客的利益,也关系
13、到服务机构的利用率。2.逗留时间w和等待时间wq的分布这是顾客最关心的指标,但各个顾客关心的角度不同。例如就诊病人对等待时间比较关心,对诊断时间却不希望太快。3.服务台的利用率服务台工作的时间占总时间的比例,可以衡量服务台的劳动强度及服务成本的大小。这是服务部门所关心的。,排队论的基本概念,4.顾客损失率对于消失制和混合制的排队系统,必须考虑因服务能力不足导致顾客消失的比例,因为这直接关系到经济利益。,单服务台系统,本节将讨论输入过程服从泊松分布过程、服务时间服从负指数分布、单服务台的排队系统。现将其分为:标准的M/M/1模型(M/M/1/FCFS)标准的M/M/1是指符合下列条件的排队系统:
14、(1)输入过程顾客源是无限的,顾客单个到来,相互独立,一定的到达时间服从泊松分布,到达过程平稳。(2)排队规则单队,且队长没有限制,先到先服务。(3)服务机构单服务台,各顾客的服务时间相互独立,服从相同的负指数分布。此外,还假定到达间隔时间和服务时间相互独立。,单服务台系统,在分析标准的M/M/1模型时首先要求出系统在任意时刻t的状态为n(系统中有n个顾客)的概率Pn(t),它决定了系统运行的特征。因为已知到达规律服从参数为的泊松过程,服务时间服从参数为的负指数分布,所以在t,t+t时间区间内分为:(1)有1个顾客到达的概率为t+(t);没有顾客到达的概率是1-t+(t)。(2)当顾客在接受服
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第八 排队

链接地址:https://www.31ppt.com/p-2348360.html