第六章排队论模型ppt课件.ppt

《第六章排队论模型ppt课件.ppt》由会员分享，可在线阅读，更多相关《第六章排队论模型ppt课件.ppt（68页珍藏版）》请在三一办公上搜索。

1、1,第六章 排队论模型,2,排队论简介：,排队论(Queuing Theory)，又称随机服务系统理论(Random Service System Theory),是运筹学的一个主要分支，是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。主要包含以下三个方面的研究内容：,(1)性态问题，即研究各种排队系统的概率规律性，如队长、等待时间、忙期等要素满足的分布。有瞬态和稳态两种情况。,(2)最优化问题，包括最优设计下的静态最优和现有排队系统的最优运营下的动态最优。,(3)排队系统的统计推断，即判断一个给定的排队系统

2、符合何种模型，以便进一步根据排队理论进行分析研究。,前 言,3,起源于1909年在丹麦哥本哈根电子公司工作的电话工程师A. K. Erlang(A.K.爱尔朗)对电话通话拥挤问题的研究工作，其开创性论文-概率论和电话通讯理论则标志此理论的诞生。表明了排队论的发展最早是与电话，通信中的问题相联系的，并到现在也还是排队论的传统的应用领域。近年来在计算机通讯网络系统、交通运输、医疗卫生系统、各类生产服务、库存管理等等各领域中均得到广泛的应用。,排队论历史：,排队是我们在日常生活和生产中经常遇到的现象。例如：搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常

3、出现排队和等待现象。除了上述有形的排队之外，还有大量的所谓“无形”排队现象，如几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形队列在等待派车。排队的不一定是人，也可以是物：例如：通讯卫星与地面若干待传递的信息；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。,排队论具体事例：,4,上述事例中的各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或机构。排队论里把要求服务的对象统称为“顾客”,而把提供服务的人或机构称为

4、“服务台”或“服务员”。不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统。,5,模型1 单服务台排队模型,排队模型及类型,根据顾客到达和服务台数，排队过程可用下列模型表示：,模型2 单队列多服务台并联的排队模型,6,模型3 多队列多服务台的并联排队模型,模型4 单队多个服务台的串联排队模型,7,模型5 多队列多服务台混联网络模型,纵观上述排队模型，实际上都可由下面模型加以统一描述：,称该统一模型为随机聚散服务系统。由于顾客到来的时刻和服务台提供服务的时间长短都是随机的，因此任一排队系统都是一个随机

5、聚散服务系统。 “聚”表示顾客的到达,“散”表示顾客的离去。,8,面对拥挤现象，人们总是希望尽量设法减少排队，通常的做法是增加服务设施，但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。 顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。 如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾。这就是随机服务系统理论排队论所要研究解决的问题。,9,一、排队系统的组成与特征 排队系统一般有三个基本组成部分：1.输入过程；2.排队规

6、则；3.服务机构。如下图所示：,排队系统的基本概念,10,1、输入过程,输入即为顾客的到达，可有下列情况： 1）顾客源可能是有限的，也可能是无限的。 2）顾客是成批到达或是单个到达。 3）顾客到达间隔时间可能是随机的或确定的。 4）顾客到达可能是相互独立或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。 5）输入过程可以是平稳的，也可以是非平稳的。输入过程平稳的是指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非平稳的则是与时间相关，非平稳的处理比较困难。,11,这是指服务台从队列中选取顾客进行服务的顺序。可以分为损失制、等待制、混合制3大类。 (1)损失制。这是指如果顾

7、客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。 典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。,2、排队规则,12,(2)等待制。指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。 例如，排队等待售票，故障设备等待维修等。 等待制中，服务台在选择顾客进行服务时，常有如下四种规则： 先到先服务（FCFS ）。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。 后到先服务（LCFS）。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。,13,随机服务(RAND) 。即当服务

8、台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。 优先权服务(PR)。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。,14,(3)混合制这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种： 队长有限。当排队等待服务顾客人数超过规定数量时，后来顾客就自动离去，另求服务，即系统的等待空间是有限的。例如最多只能容纳N个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于N，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。再

9、如水库的库容是有限的，旅馆的床位是有限的。,15, 等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客自动离去，不再回来。 如易损坏的电子元器件的库存问题，超过一定存储时间被自动认为失效。 又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。,16, 逗留时间(等待时间与服务时间之和)有限。 例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。 不难注意到，损失制和等待制可看成是混合制的特殊情形，如记c为系统中服务台的个数，则当K=c 时，混合制即成为损失制；当K=时，混合制即成为等待制

10、。,17,3、服务台,服务台可以从以下3方面来描述：(1) 服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有：单队单服务台式； 单队多服务台并联式； 多队多服务台并联式； 单队多服务台串联式； 单队多服务台并串联混合式,以及多队列多服务台并串联混合式等等。 如之前的分类模型图所示。,18,(2) 服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。(3) 服务时间的分布。一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K阶爱尔朗分布、一般分布

11、(所有顾客的服务时间都是独立同分布的)等等。,19,排队系统的描述符号与模型分类,为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，可给出很多排队模型(见前面分析与图示)。为了方便对众多模型的描述,DG肯道尔（DGKendall）提出了一种目前在排队论中被广泛采用的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式：X/Y/Z/A/B/C 各符号的意义如下：,X-表示顾客相继到达间隔时间分布，常用下列符号： M表示到达过程为泊松过程或(负指数分布Markov)； D表示定长输入(确定型分布Deterministic)； EK表示k阶爱尔朗

12、分布； GI 一般相互独立的随机分布(General Independent) G表示一般的随机分布。,20,Y-表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。 Z-表示服务台(员)个数：“1”则表示单个服务台，“s”。(s1)表示多个服务台。A-表示系统中顾客容量限额，或称等待空间容量； 如系统有K个等待位子，则 0K，当 K=0 时，说明系统不允许等待，即为损失制。K= 时为等待制系统，此时般省略不写。K为有限整数时，表示为混合制系统。B-表示顾客源限额。 分有限与无限两种，表示顾客源无限，此时一般也可省略不写。C-表示服务规则，常用下列符号： FCFS：表示先到先服务的排队规

13、则； LCFS：表示后到先服务的排队规则； PR：表示优先权服务的排队规则。,21,例如：某排队问题为MMSFCFS，则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。 某些情况下，排队问题仅用上述表达形式中的前3个、4个、5个符号。如不特别说明则均理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系统。,22,排队问题求解(主要指性态问题),求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值，以便实现对现有系

14、统合理改进和对新建系统的最优设计等。 排队问题的一般步骤： 1、确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布(可实测)。 2、研究分析排队系统理论分布的概率特征。 3、研究系统状态的概率。系统状态是指系统中顾客数,用n表示。状态概率用Pn(t)表示,即在t时刻系统中有n个顾客的概率，也称瞬态概率。,23,求解状态概率Pn(t)方法是建立含Pn(t)的微分差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此常常使用它的极限(如果存在的话)：,稳态的物理意义图，系统的稳态一般很快都能达到，但实际中达不到稳态的现象也存在。要注意的是求

15、稳态概率Pn并不一定求t的极限,只需求Pn(t)=0 。,称为稳态解，或称统计平衡状态解。,24,4、根据排队系统对应的理论模型求用以判断系统运行优劣的基本数量指标的概率分布或特征数。 数量指标主要包括:(1)平均队长(Ls):系统中的顾客数(包括被服务和正在排队的顾客)。 平均队列长(Lq):系统中排队等待服务的顾客数。 系统中顾客数Ls =系统中排队等待服务的顾客数Lg +正被服务的顾客数c(2)平均逗留时间(Ws):指一个顾客在系统中的停留时间(含等待时间和被服务时间)。 平均等待时间(Wq):一个顾客在系统中排队等待的时间。(3)平均忙期(Tb)：指从顾客到达空闲服务机构起到服务机构再

16、次为空闲这段时间平均长度。(忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度),25,5、排队系统指标优化 含优化设计与优化运营。,与忙期相对的是闲期，即服务机构连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。 除了上述几个基本数量指标外，还会用到其他一些重要的指标，如在损失制或系统容量有限的情况下，由于顾客被拒绝，而使服务系统受到损失的顾客损失率及服务强度等，也都是十分重要的数量指标。 计算上述指标的基础是表达系统状态(系统中的顾客数n)的概率与顾客到达(输入过程)间隔时间分布与服务时间分布有关。顾客数n的可能取值是：(1)队长没有限制时，n=0，

17、1，2，(2)队长有限制、最大数为N时，n=0，1，2，N(3)损失制且服务台个数为c时，n=0，1，2，c 系统处于这些状态的概率一般是随时间t变化的，所以在时刻t、系统状态为n的瞬态概率可用Pn(t)表示，稳态概率用Pn表示。,26,输入过程与服务时间的分布,排队系统的主要数据是顾客到达流和服务时间流，而这都与时间有关且是不确定的。根据有关概率知识，与时间有关的随机变量的概率分布是一类非负的随机变量分布，是一个随机过程，即泊松过程。 常用的非负随机变量分布有泊松分布、指数分布、爱尔朗分布、确定型分布等。,现设顾客到达过程是一个随机过程。令N(t)表示在时间区间0,t)内到达的顾客数(t0)

18、,Pn(t1,t2)表示在时间区间t1,t2)(t2t1)内有n(0)个顾客到达的概率。即：,（t2t1，n0）,当Pn(t1,t2)同时符合下述三个条件时，顾客到达过程就是泊松过程(顾客到达形成泊松流)。,1、泊松分布,27,平稳性：即对于足够小的t，有：,泊松流具有如下特性：,在t,t+t内有一个顾客到达的概率与t无关,而与t成正比。,28, 普通性：对充分小的t,在时间区间（t,t+t）内有2个或2个以上顾客到达的概率是一高阶无穷小.,由此知，在(t，t+t)区间内没有顾客到达的概率为：,令t1=0,t2=t,则P(t1,t2)=Pn(0,t)=Pn(t),0 是常数，它表示单位时间到达

19、的顾客数，称为概率强度。,即,P0+P1+P2=1,下面将讨论求关键的Pn(t)。,29,在0，t+t内到达n个顾客应是上面三种互不相容的情况之一，所以有：,为了求Pn(t),即Pn(0,t)，需要研究它在（t，t+t）上的改变量,建立Pn(t)的微分方程。对于区间0,t+t)可以分成0，t)和t，t+t),其到达总数是n，不外有下列三种情况：,30,令t0取极限（并注意初始条件）得：,当n=0时，没有B，C两种情况，则：,凑微分,即：,31, C = 0,（3）式两端乘et并移项得：,两边积分得：,代入初始条件(t=0)有：,P0(0)=1,32,将n=1,2,3代入（6）得：,(6),(注

20、意利用(5)式),凑成Pn(t)et两项乘积的微分,两边积分,33,如此继续递推下去得：,（n个顾客到达的概率）,即随机变量N(t)=n服从泊松分布。它的数学期望和方差为：,34,引入级数,令k=n-1，则：,35,即：,同理方差为：,说明顾客到达过程确实是一个泊松过程(泊松流)，这也是泊松分布的数学推导。,36,2、负指数分布 当输入过程是泊松流时，我们研究两顾客相继到达的时间间隔的概率分布。 设T为时间间隔，分布函数为FT（t），则：FT（t）=PTt 此概率等价于在0,t)区间内至少有1个顾客到达的概率。,没有顾客到达的概率为： (由（5）式而来),间隔：,间隔：,间隔,对分布函数微分,

21、37,表示单位时间内顾客平均到达数。 1/表示顾客到达的平均间隔时间。 可以证明，间隔时间T独立且服从负指数分布与顾客到达形成泊松流是等价的。负指数分布是一种无记忆性的分布。,对顾客的服务时间：系统处于忙期时两顾客相继离开系统的时间间隔，一般地也服从负指数分布。,即T服从负指数分布，它的期望及方差为：,接受服务，然后离开,服务时间的分布：,即：P(Xt+s|Xt)=P(Xs),38,其中：表示单位时间内能被服务的顾客数，即平均 服务率。 1/表示一个顾客的平均服务时间。,3、爱尔朗(Erlang)分布 设v1, v2，, vk是k个独立的随机变量，服从相同参数 k 的负指数分布，那么：,，则,

22、令 ，则称为服务强度。,令,39,串列k个服务台，每台服务时间相互独立，服从相同负指数分布（参数k），那么一顾客走完k个服务台总共所需要服务时间服从上述k阶Erlang分布。,则称T服从k阶爱尔朗分布。其特征值为：,其概率密度是,1/ k表示一个顾客一个服务台的平均服务时间。,其他常用的分布参见教材P122-123，也可参见概率论与数理统计相关教程。,40,生灭过程,1、生灭过程简介,一类非常重要且广泛存在的排队系统是生灭过程排队系统。生灭过程是一类特殊的随机过程，在生物学、物理学、运筹学中有广泛的应用。,2、生灭过程的定义 设N(t),t0 为一个随机过程。如N(t)的概率分布具有以下性质：

23、 (1)假设N(t)=n，则从时刻t起到下一个顾客到达时刻止的时间服从参数为n的负指数分布，n=0，1，2，。间隔时间分布 (2)假设N(t)=n，则从时刻t起到下一个顾客离去时刻止的时间服从参数为n的负指数分布，n=0，1，2，。服务时间分布 (3)同一时刻只有一个顾客到达或离去。则称设N(t),t0 为一个生灭过程。,41,顾客到达“生”；顾客离开“灭”,生灭过程示意图：,顾客到达,顾客离去,42,一般说来，得到 是比较困难的或非理论作用不太大，因此通常是求当系统达到平稳状态后的状态分布，记为 , n=0,1,2, 为求平稳分布 ，考虑系统在 t+t 时刻可能处的任一状态n的概率。可给出状

24、态转移图如下：,说明：n状态下，排队系统中的人数稳定为n,n=0,1,2,.,即进了多少个就要出去多少个。,43,各种方式下发生概率表（保证n状态:t+t时刻稳定有n个人）,说明：状态n下，1人到达的概率约为nt，1人离去的概率约为nt，0人到达的概率约为1-nt，0人离去的概率约为1-nt。(根据泊松流的特征得到),44,又因为前述方式1，2，3，4是互不相容且完备的，因此有：,对上式展开并构造如下极限式：,，则有：,这刚好就是Pn(t)对t的导数。,事件(0,t+t)发生可看作事件(0,t）和事件(t,t+t)同时发生。因此：P(0,t+t)= P(0,t)P(t,t+t),45,当n=0

25、时，只有方式1和3，4发生，且方式1中无离去的概率为1，则:,设系统是稳态的，即与时刻t无关，于是可得：,令P0已知，可用递推方法求得：,46,记,则平稳状态的分布为：,下面求P0。,47,由概率分布的要求：,有：,即,综上述，得到各状态平衡时的概率分布递推计算式如下：,所以关键是得到各状态下单位时间到达和离开的人数：,48,例：某小型超市有一个收款台。付款顾客以每小时30人的负指数分布到达。当收款台前只有一名顾客时，有一名收款员单独服务，收款时间为平均1.5min的负指数分布；当有2名或以上顾客时，将增加一名助手共同为顾客服务，收款时间将缩短至平均1min的负指数分布。求收款台前有n名顾客的

26、概率Pn,解：这里的单位时间是1小时，所以,49,n=1,2.,则有,由,可知：,50,一般地，对排队模型，在给定输入和服务条件下，主要研究系统的下述运行指标： (1)系统的平均队长Ls(期望值)和平均队列长Lq(期望值)； (2)系统中顾客平均逗留时间Ws与队列中平均等待时间Wq；,M/M/s等待制排队模型,单服务台模型： M/M/1/ ,M/M/1/ 是指：顾客的相继到达时间服从参数为的负指数分布，服务台数为1，服务时间服从参数为的负指数分布，系统空间无限，允许无限排队。,51,1、队长的分布(参数、就是单位时间进入或被服务的人数),所以n =( n=0，1，2，)，n =( n=0，1，

27、2，)记 = / ，并设 1 (否则队列将排至无限远)， 则,n= 1,2,.,，n= 1,2,而,因此,n=0,1,2,是系统中至少有一个顾客的概率，也就是服务台处于忙的状态的概率，因而也称为服务强度，它反映了系统繁忙的程度。,即为平衡条件下系统中顾客数为n的概率。,52,2. 系统的运行指标计算 (1) 系统中的队长Ls（平均队长：排队+被服务）,(01),期望,53,(2) 队列中等待的平均顾客数Lq ：仅排队,(3) 顾客在系统中的平均逗留时间Ws 顾客在系统中的逗留时间是随机变量，可以证明，它服从参数为-的负指数分布，分布函数,54,(4)顾客在队列中的平均逗留时间Wq,等待时间,顾

28、客在队列中的平均逗留时间应为Ws减去平均服务时间。,考虑LS与WS的关系,55,四个指标的关系为(Little 公式)：,3. 系统的忙期与闲期,系统处于空闲状态的概率：,系统处于繁忙状态的概率：,服务强度,56,在繁忙状态下，队列中的平均顾客数Lb：,顾客平均等待时间:,一个忙期平均服务顾客数为：,LbP(N0)=Lq,57,例：某修理店只有一个修理工，来修理的顾客到达过程为Poisson流，平均4人/h; 修理时间服从负指数分布，平均需要6min。试求：（1）修理店空闲的概率（2）店内恰有3个顾客的概率（3）店内至少有1个顾客的概率（4）在店内的平均顾客数（5）每位顾客在店内的平均逗留时间

29、（6）等待服务的平均顾客数（7）每位顾客平均等待服务时间（8）顾客在店内等待时间超过10min的概率,58,解 本例可看成一个M/M/1/排队问题，其中,（1）修理店空闲的概率,（2）店内恰有3个顾客的概率,（3）店内至少有1个顾客的概率,59,（4）在店内的平均顾客数,（5）每位顾客在店内的平均逗留时间,（人）,（6）等待服务的平均顾客数,（人）,60,（7）每位顾客平均等待服务的时间,（8）顾客在店内逗留时间超过10min的概率,由于逗留时间服从参数 的负指数分布，即分布函数为,则,注：对于： 1小时 10 人 则 1分钟 10/60=1/6(人)。同理,61,多服务台模型： M/M/s/

30、,M/M/s/ 是指：设顾客单个到达，相继到达时间服从参数为的负指数分布，服务台数为s，每个服务台的服务时间相互独立，且服从参数为的负指数分布，系统空间无限，允许无限排队。,当考虑系统处于平稳状态后队长N的概率分布,有,1、队长的分布,62,n=1,2,s,ns,故,其中,63,上面两个式子给出了平衡条件下系统中顾客数为n的概率，当ns时，即系统中顾客数大于服务台个数，这时再来的顾客必须等待，因此记：,Erlang等待公式,它给出了顾客到达系统时需要等待的概率。,由平稳状态下队长N的概率分布，可得到平均排队长Lq:,2、几个主要数量指标,64,由平均排队长Lq，可得到平均队长Ls为：,Ls=平

31、均排队长Lq + 正在接受服务的顾客的平均数,记系统中正在接受服务的顾客的平均数为,显然 也是正在忙的服务台的平均数，故：,上式说明，平均在忙的服务台个数不依赖于服务台个数s,在求得“正在接受服务的顾客的平均数” 后,我们可求得平均队长,65,对于多服务台系统，Little公式依然成立，即有,例 某火车站售票处有三个窗口，同时售各车次的车票。顾客到达服从泊松分布，平均每分钟到达=0.9（人），服务时间服从负指数分布，平均服务率=24（人/h），分两种情况：(1)顾客排成一队，依次购票； (M/M/3/)(2)顾客在每个窗口排一队，不准串队。(M/M/1/ 三个系统并联) 求:1）售票处空闲的概

32、率。 2）平均队长和平均排队长。 3）平均等待时间和逗留时间。 4）顾客必须等待的概率。,解：(1) 根据已知，平均到达率每分钟=0.9人，平均服务率每分钟=0.4人,窗口数s=3, 单窗口服务强度=2.25，多窗口服务强度s=2.25/3=0.751.代入公式可得：1) 整个售票处空闲概率：,66,2)平均排队长：,3)平均等待时间,平均队长：,平均逗留时间,4)顾客到达后必须等待(即系统中顾客数已有3人即各服务台都没有空闲)的概率:,(2)如果其他条件不变，但顾客到达后在每个窗口前各排一队，且进入队列后坚持不换，这就形成3个队列，此时，每个队列平均到达率为,这样，原来的系统就变成3个M/M/1型的子系统，这时,=0.4,=/=0.75,p0=1-=0.25,67,代入公式可得：1) 整个售票处空闲概率： 0.25(每个子系统)2）平均队长：9.00(整个系统) 平均排队长：2.25(每个子系统)3）平均等待时间： 7.5 平均逗留时间：104）顾客必须等待的概率：0.75,从各指标的对比可以看出：单队比三队有显著优越性。,68,This is the end！,