数学建模排队论课件

《数学建模排队论课件》由会员分享，可在线阅读，更多相关《数学建模排队论课件（71页珍藏版）》请在金锄头文库上搜索。

1、Queueing Theory,第十四章 排队论,一、排队论的基本概念,二、几类排队论模型,三、模型的建立与求解,一、排队论的基本知识,2. 排队系统描述,3. 基本组成部分,4. 数量指标,5. 排队模型的记号,1. 背景介绍,1 背景介绍,有形的队伍 超市出口处排队付款 餐厅排队买饭 公共电话亭打电话 无形的队伍 114查号台等待服务 网络中数据包传输 报告等首长批示 文件等待打印或发送 某些系统也可能根本不允许排队 交换机处理呼叫,排队论研究的内容有三部分,1.性态问题：即研究排队系统中的概率分布规律,2.最优化问题：分为静态最优化和动态最优化，即 为系统的最优设计和系统的最优运营,3.

2、排队系统的统计推断： 判断一个给定的排队系统符合于哪种模型，以便于根据排队理论进行分析研究,2.排队系统描述,排队系统又称为随机服务系统，是研究服务,请求服务的人或者物顾客；,排队系统的共同特征：,顾客到达系统的时刻是随机的，为每一位顾客,有为顾客服务的人或者物，即服务员或服务台；,过程和拥挤现象的随机模型.,提供服务的时间是随机的，因而整个排队系统,的状态也是随机的.,排队模型,服务窗,服务规则,顾客源,排队系统,排队系统的几种形式：,基本排队过程：,从图66可知，每个顾客由顾客源按一定方式,到达服务系统，首先加入队列排队等待接受服务，,然后服务台按一定规则从队列中选择顾客进行服,务，获得服

3、务的顾客立即离开.,排队论所要研究解决的问题：,面对拥挤现象，人们通常的做法是增加服务设施,但是增加的数量越多，人力、物力的支出就越大，甚,至会出现空闲浪费，如果服务设施太少，顾客排队等,待的时间就会很长，这样对顾客会带来不良影响.如,何做到既保证一定的服务质量指标，又使服务设施费,用经济合理，恰当地解决顾客排队时间与服务设施费,用大小这对矛盾，就是随机服务系统理论排队论,所要研究解决的问题。,3.排队系统的基本组成部分,排队系统是由输入过程、排对规则和服务机构组成.,(1).输入过程 指要求服务的顾客是按怎样的规律,(i) 顾客总体数. 又称顾客源、输入源.这是指顾客,(ii) 顾客到达方式

4、. 这是描述顾客是怎样来到系统,到达排队系统的过程，有时也把它称为顾客流.一,般可以从3个方面来描述个输入过程.,的来源.顾客源可以是有限的，也可以是无限的.,的，是单个到达，还是成批到达.,(iii) 顾客流的概率分布.或称相继顾客到达的时间,(2).排对规则 指服务台从队列中选取顾客进行,(i)损失制 指如果顾客到达排队系统时，所有,间隔的分布.这是求解排队系统有关运行指标问题,时，首先需要确定的指标.顾客流的概率分布一般,有定长分布、二项分布、泊松流(最简单流)、爱尔,朗分布等若干种.,服务的顺序.一般可以分为损失制、等待制和混,合制等3大类.,服务台都被先到的顾客占用，那么他们就自动,

5、离开系统永不再来.,(ii)等待制 指当顾客来到系统时，所有服务台,a.先到先服务FCFS 按顾客到达的先后顺序对顾客,b.先到后服务LCFS,c.随机服务 即当服务台空闲时，不按照排队,d.优先权服务,都不空，顾客加入排队行列等待服务.等待制中，,服务台在选择顾客进行服务时常有如下四种规则：,进行服务.,序列而随意指定某个顾客接受服务.,(iii)混合制 这是等待制与损失制相结合的一种服,a.队长有限.当排队等待服务的顾客人数超,b.等待时间有限.即顾客在系统中的等待时,c.逗留时间(等待时间与服务时间之和)有限.,务规则，一般是指允许排队，但又不允许队列无限,长下去.具体说来，大致有三种：

6、,过规定数量K时，后来的顾客就自动离去，另,求服务，即系统的等待空间是有限的.,间不超过某一给定的长度T，当等待时间超,过T时，顾客将自动离去，并不再回来.,(3). 服务机构,(i)服务台数量及构成形式. 从数量上说，服务台有单,(ii)服务方式. 这是指在某一时刻接受服务的顾客数，,(iii)服务时间的分布.在多数情况下，对每一个顾客的,服务台和多服务台之分. 从构成形式上看，服务台有：,单队一-单服务台式；单队一-多服务台并联,式；多队一-多服务台并联式；单队一-多服,务台串联式；单队一-多服务台并串联混合式，,以及多队多服务台并串联混合式等等.,它有单个服务和成批服务两种.,服务时间是

7、一随机变量.,常见顾客的服务时间分布有： 定长分布D(Deterministic)、 负指数分布M(Markov)、 k阶Erlang分布(Ek)、 一般相互独立的时间间隔分布GI(General Independent)、,顾客到达时间间隔的分布:,假定 是独立同分布，分布函数为 ， 排队论中常用的有两种：,（2）最简流（即Poisson流）（M）： 顾客到达时间间隔 为独立的， 服从负指数分布，其密度函数为,（1）定长分布（D）：顾客到达时间间隔为确定的。,因为负指数分布 具有无后效性 （即Markov性）,服务时间分布:,设某服务台的服务时间为V，其密度函数为b（t），常见的分布有：,（

8、1）定长分布（D）：每个顾客接受服务的时间 是一个确定的常数。 （2）负指数分布（M）：每个顾客接受服务时间 相互独立，具有相互的负指数分布： 其中 ，为一常数。,- 单位时间平均服务完成的顾客数 1/ - 每个顾客的平均服务时间,服务时间分布:,（3）k阶爱尔朗（Erlang）分布：每个顾客接受服务 时间服从k阶爱尔朗分布，其密度函数为：,4. 排队系统的主要数量指标,排队论主要研究系统的性态，即与排队有关,(1).排队系统主要数量指标,等待时间、 忙期、 队长.,的数量指标的概率规律性；系统的优化问题；统,计推断，根据资料合理建立模型.目的是正确设,计和有效运行各个服务系统，使之发挥最佳效

9、益.,所以必须确定判断系统运行优劣的基本数量指标.,(i).等待时间 从顾客到达时刻起到他开始接受服务止这,(ii).忙期 忙期是指从顾客到达空闲着的服务机构起，到,(iii).队长 队长是指系统中的顾客数(排队等待的顾客数与,段时间称为等待时间.等待时间是个随机变量.从顾客,到达时刻起到他接受服务完成止这段时间称为逗留时,间，也是随机变量.,服务机构再次成为空闲止的这段时间，即服务机构连续忙,的时间.这是个随机变量，是服务员最为关心的指标，因,为它关系到服务员的服务强度.与忙期相对的是闲期,即,服务机构连续保持空闲的时间.在排队系统中，忙期和闲,期总是交替出现的.,正在接受服务的顾客数之和)

10、；排队长是指系统中正在排队,等待服务的顾客数.队长和排队长一般都是随机变量.,(2).数量指标的常用记号,(i).主要数量指标,Ws平均逗留时间，即(在任意时刻)进入,的所有顾客数的期望值；,等待服务的顾客数的期望值；,稳态系统的顾客逗留时间的期望值；,稳态系统的顾客等待时间的期望值.,Ls-平均队长， 即稳态系统任一时刻,平均等待时间，即(在任意时刻)进入,平均等待队长，即稳态系统任一时刻,(ii).其它常用数量指标,s 系统中并联服务台的数目；,N 稳态系统任一时刻的状态（即系统中,U 任一顾客在稳态系统中的逗留时间；,Q 任一顾客在稳态系统中的等待时间；,所有顾客数）；,平均到达率；,平

11、均到达间隔；,平均服务率；,平均服务时间；,有服务台全部空闲的概率；,繁忙程度的重要尺度.,服务强度，即每个服务台单位时间内的平,均服务时间，一般有 ，这是衡量排队系统,:稳态系统任意时刻状态为n的概率；,损失率：由于系统的条件限制，使顾客被拒绝服 务而使服务部门受到损失的概率。,5. 排队系统的描述符号,描述符号：X/Y/Z/A/B/C,X顾客相继到达的间隔时间的分布 ；常用下,M表示到达的过程为泊松过程或负指数分布；,D表示定长输入；,GI表示一般相互独立的时间间隔分布.,Y服务时间的分布；所用符号与表示顾客,列符号：,到达间隔时间分布相同.,表示K阶爱尔朗分布；,Z服务台个数 ； “1”

12、表示单个服务台，“s” (s1),A系统容量限制(默认为)；如系统有K个等待位子，则,B顾客源数目（默认为）；分有限与无限两种，表,C服务规则；,常用下列符号：,FCFS：表示先到先服务的排队规则；,LCFS：表示后到先服务的排队规则；,PR： 表示优先权服务的排队规则。,表示多个服务台.,0K，当K=0时，说明系统不允许等待，即为损失制.,K=时为等待制系统，此时一般省略不写.K为有限整数,时，表示为混合制系统.,示顾客源无限，一般也可省略不写.,例如：某排队问题为MMS/FCFS，则,某些情况下，排队问题仅用上述表达形式,如不特别说明则均理解为系统等待空间容量,表示顾客到达间隔时间为负指数

13、分布(泊松流)；,服务时间为负指数分布；有s (s1)个服务台；系,统等待空间容量无限(等待制)；顾客源无限，采,用先到先服务规则.,中的前3个符号.例如，某排队问题为MMS.,无限；顾客源无限，先到先服务，单个服务的等,待制系统.,一、相关知识回顾1、 爱尔朗分布,为k个相互独立的随机变量； 服从相同参数 的负指数分布；,设 ，则T的密度函数为,如k个服务台串联（k个服务阶段）， 一个顾客接受k个服务共需的服务时间T， T爱尔朗分布。,2、Poisson过程,定义：设 为时间 内到达系统的顾客数，若满足下面三个条件： 独立性：在任意两个不相交的区间内顾客到 达的情况相互独立； 平稳性：在 内

14、有一个顾客到达的 概率为 普通性：在 内多于一个顾客到达 的率为 。 则称 为Poisson过程。,（1）只与区间长度与 起点无关。 （2）单位时间内一个 顾客到达的概率 为 。,Poisson过程与Poisson分布,数理统计方法 容易初步判断:期望=标准差,Poisson过程与负指数分布,负指数分布的性质:,马尔可夫性，或无后效性,Poisson过程与Poisson分布的关系：,对于Poisson流： 单位时间平均到达的顾客数 顾客相继到达的平均间隔时间,定义：设 为一个随机过程，若N(t)的概率分布具有以下性质： (1)假设N(t)=n，则从时刻到下一个顾客到达时刻止的时间服从参数为 的

15、负指数分布； (2)假设N(t)=n，则从时刻到下一个顾客离开时刻止的时间服从参数为 的负指数分布； (3)同一时刻是只有一个 顾客到达或离去。 则称 为一个生灭过程。,4、生灭过程,平稳生灭过程系统状态n 平衡方程：“流入=流出”,系统达到平稳状态时：,的分布,系统达到平稳状态时：,平衡方程：,当 时才有意义,已知: 顾客到达间隔时间分布, 服务时间分布. 求: 队长: Ls - 系统中的顾客数. 排队长(队列长): Lq - 队列中的顾客数. Ls = Lq + 正在接受服务的顾客数 逗留时间: W S- 顾客在系统中的停留时间 等待时间: Wq - 顾客在队列中的等待时间. WS = W

16、q + 服务时间 忙期, 损失率, 服务强度.,排队问题的求解,三、几类排队论模型,1. M/M/S 模型,2. GI/M/n 模型,1. M/M/s排队模型,M/M/s排队模型是指s个服务员的排队系统，,顾客到来间隔时间是独立同分布的；,服务时间也是独立同分布的；,并且独立于输入过程；,排队规则是等待制；,含假定：,顾客到来间隔时间服从参数为 的指数分布，,服务时间服从参数为 的负指数分布，且有隐,按排队论的基本构成特征，来求解该排队模型,(1).基本构成,(i) 顾客到达规律,的主要数量指标：,平均到达率.,表示在 时间到达的顾客数，称为排队系统的输入过程.,其平均值为 ，即单位时间内到达的顾客数为 ，并称为,它服从参数为 的泊松分布，即：,(ii) 服务时间,服务率 .,表示顾客到达间隔时间序列，其,中 表示第n个顾客的到来时刻.,可以证明： 服从参数 为的泊松分布的充,负指