《数学建模排队论课件》由会员分享,可在线阅读,更多相关《数学建模排队论课件(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个顾客的到来时刻.,可以证明: 服从参数 为的泊松分布的充,负指