[企业管理]三2010暑期培训排队论.ppt
《[企业管理]三2010暑期培训排队论.ppt》由会员分享,可在线阅读,更多相关《[企业管理]三2010暑期培训排队论.ppt(188页珍藏版)》请在三一文库上搜索。
1、董 珺,排队论 ( Queuing theory),排队论,一.概率论及随机过程回顾 二.排队论的基本知识 三.单服务台负指数分布排队系统分析 四.多服务台负指数分布排队系统分析 五.一般服务时间M/G/1模型分析 六.经济分析_排队系统的最优化,一、概率论及随机过程回顾,随机变量 离散型随机变量 概率分布和概率分布图 数学期望和方差 常见离散型随机变量的概率分布 二点分布? 二项式分布? Poisson分布?,1.1、随机变量与概率分布,一、概率论及随机过程复习,随机变量 离散型随机变量 概率分布和概率分布图 数学期望和方差 常见离散型随机变量的概率分布 二点分布? 二项式分布? Poiss
2、on分布?,一、随机变量与概率分布,随机变量 连续型随机变量 概率密度函数 概率分布函数 数学期望和方差 常见连续型随机变量的概率分布 均匀分布 指数分布? 正态分布? k阶爱尔朗分布?,一、随机变量与概率分布,? 爱尔朗分布,为k个相互独立的随机变量; 服从相同参数 的负指数分布;,设 ,则T的密度函数为,如k个服务台串联(k个服务阶段), 一个顾客接受k个服务共需的服务时间T, T爱尔朗分布。,若顾客连续接受串联的k个服务台的服务,各服务台的服务时间相互独立,且均服从负指数分布,则顾客接受k个服务共需的服务时间Tk阶爱尔朗分布。,1.2 随机过程的有关概念,随机过程(Random proc
3、ess)的定义,设 ,是一族随机变量, T是一个实数集,对 是一个 随机变量,则称 为随机过程。,T:参数集合 当T=0,1,n,时,称为随机序列 :随机过程的一个状态 状态空间E=X(t)全体可能取值, ,随机过程的基本类型 二阶矩过程 平稳过程 平稳独立增量过程 常见随机过程 马尔可夫过程? Poisson过程? 生灭过程?,1.2 随机过程的有关概念,定义: 若满足如下性质: 对任意非负整数 ,只要 就有 则称 具有马尔可夫性,或无后效性。,马尔可夫过程 马尔可夫链,现在,将来,“将来”的情况与“过去”无关, 只是通过“现在”与“过去”发生联系,若 “现在”已知,“将来”与“过去”无关。
4、,时齐的马氏链:马氏链 若满足: 则称 为时齐马尔可夫链, 系统由状态i经过m 个时间间隔 (或m 步)转移到状态j 的转移概率,其中Poisson过程是应用最为广泛的一类随机过程,常用来描述派对系统中顾客到达的过程、城市中的交通事故、保险公司的理赔次数等。,Poisson过程,定义:设 为时间 内到达系统的顾客数,若满足下面三个条件: 独立性:在任意两个不相交的区间内顾客到 达的情况相互独立; 平稳性:在 内有一个顾客到达的 概率为 普通性:在 内多于一个顾客到达 的率为 。 则称 为Poisson过程。且N(t)服从Poisson分布。,(1)只与区间长度与 起点无关。 (2)单位时间内一
5、个 顾客到达的概率 为 。,Poisson过程与Poisson分布,数理统计方法 容易初步判断:期望=方差,Poisson过程与负指数分布,负指数分布的性质:,马尔可夫性,或无后效性,对于Poisson流: 单位时间平均到达的顾客数 顾客相继到达的平均间隔时间,定义:设 为一个随机过程,若N(t)的概率分布具有以下性质: (1)假设N(t)=n,则从时刻到下一个顾客到达时刻止的时间服从参数为 的负指数分布; (2)假设N(t)=n,则从时刻到下一个顾客离开时刻止的时间服从参数为 的负指数分布; (3)同一时刻是只有一个 顾客到达或离去。 则称 为一个生灭过程。,生灭过程,平稳生灭过程系统状态n
6、 平衡方程:“流入=流出”,系统达到平稳状态时:,的分布,系统达到平稳状态时:,平衡方程:,当 时才有意义,现实生活中的排队模型,Bank Airport Hospital Road Manufacturing Hotel Restaurant WC ,运筹学 排队模型,二、排队论的基本知识,2.1 排队模型 2.2 排队系统的组成和特征,什么是排队论,什么是 排队论?,什么是排队论,排队论是研究排队系 统的理论,又称随机服 务系统理论,它提供了 很多不同的排队模型, 通过这些排队模型能够 找到服务成本和服务水 平之间较好的平衡。,排队系统的描述,涉及的要素 顾客 队列 服务台 到达间隔时间
7、服务时间 排队规则,运筹学 排队模型,排队系统的描述,绩效测度 等待顾客数 顾客等待时间 服务台忙期 服务台闲期 服务台利用率,运筹学 排队模型,排队模型存在的问题,如何以最经济的方式控制排队系统,使其达到特定的要求? 提供过多的服务能力来控制排队系统将会造成过量的成本 提供的服务能力不足将会导致过多的等待,降低顾客满意度并造成顾客流失,减少收益,2.1、排队模型,排队系统的的一般表示 (A Basic Queuing System),下图 就是排队过程的一般模型 。 各个顾客由顾客源(总体)出发,到达服务机构(服务台、服务员)前排队等侯接受服务,服务完了后就离开。 排队结构指队列的数目和排列
8、方式,排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。 我们所说的排队系统就指图中虚线所包括的部分。,在现实中的排队现象是多种多样的,在现实中的排队现象是多种多样的,对上面所说的“顾客”和“服务员”,要作广泛地理解,它现可以是人,也可以是非生物; 队列可以是具体地排列,也可以是无形的(例如向电话交换台要求通话的呼唤); 顾客可以走向服务机构,也可以相反(如送货上门)。 下面举一些例子说明实现中形形色色的排队系统,服务机构,(a) 一个队列、单服务台(阶段),(b) 一个队列、s个服务阶段,服务机构,服务机构,(c) 一个队列、s个服务台 一个服务阶段,服务机构,(d) s
9、个队列、s个服务阶段,服务机构,(e)混合型,排队结构,(f) 一个队列,(g) s个队列,排队系统的组成和特征,一般的排队系统都有三个基本组成部分 1.输入过程; 2.排队规则; 3.服务机构。,现在分别说明各部分的特征: (1)输入过程:输入即指顾客到达排队系统。可能有下列各种不同情况,当然这些情况并不是彼此排斥的。 (a)顾客的总体(称为顾客源)的组成可能是有限的,也可能是无限的。工厂内停机待修的机器显然是有限的总体。 (b)顾客到来的方式可能是一个一个的,也可能是成批的。例如到餐厅就餐就有单个到来的顾客和受邀请来参加宴会的成批顾客,我们将只研究单个至来的情形。,(c)顾客相继到达的间隔
10、时间可以是确定型的,也可以是随机型的。 如在自动装配线上装配的各部件就必须按确定的时间间隔到达装配点,定期运行的班车、班轮、班机的到达也都是确定型的。 但一般到商店购物的顾客、到医院诊病的病人、通过路口的车辆等,它们的到达都是随机型的。 对于随机型的情形,要知道单位时间内的顾客到达数或相继到达的间隔时间的概率分布(下图),顾客到达,时间,ti-1,ti,ti+1,输入过程,(d)顾客的到达可以是相互独立的。 就是说,以前的到达情况对以后顾客的到来没有影响,否则不是有关联的。 例如,工厂内的机器在一个短的时间内出现停机(顾客到达)的概率就受已经待修或被修理的机器数目的影响。 我们主要讨论的是相互
11、独立的情形。,输入过程,(e)输入过程可以是平衡的,或称对时间是齐次的,是指描述相继到达间隔时间分布和所含参数(如期望值、方差等)都是与时间无关的,否则称为非平衡的,非平稳情形的数学处理是很困难的。,顾客到达时间间隔的分布:,:第n个顾客与第n-1个顾客到达的时间间隔;,顾客到达时间间隔的分布:,假定 是独立同分布,分布函数为 , 排队论中常用的有两种:,(2)最简流(即Poisson流)(M): 顾客到达时间间隔 为独立的, 服从负指数分布,其密度函数为,(1)定长分布(D):顾客到达时间间隔为确定的。,因为负指数分布 具有无后效性 (即Markov性),大多数排队模型假设到达间隔时间的概率
12、分布形式是指数分布 小间隔时间出现的可能性很大,而大间隔时间出现的机会则很小,这个间隔时间的特征能在实践中观察到,负指数分布,随机变量T的概率密度若是 则称T服从负指数分布,它的分布函数是 数学期望ET= ,方差DT= , 标准差T= 。,负指数分布有下列性质: (1)由条件概率公式容易证明 这性质称为无记忆性或马尔柯夫性,若T表示排队系统中顾客到达的间隔时间,那么这个性质说明一个顾客到来所需的时间与过去一个顾客到来所需时间s无关,所以说这情形下的顾客到达是纯随机的。,(2)当输入过程是普阿松流时,那么顾客相继到达的间隔时间T必服从负指数分布。这时因为对于普阿松流,在0,t)区间内至少有1个顾
13、客到达的概率是: 而这概率又可表示为,对于普阿松流,表示单位时间平均到达的顾客数,所以1就表示相继顾客到达平均间隔时间,而这正和ET的意义相符。,(2)排队规则,(a)顾客到达时,如所有服务台都正被占用,在这种情形下顾客可以随即离去,也可以排队等侯。 随即离去的称为即时制或称损失制,因为这将失掉许多顾客; 排队等侯的称为等待制。 普通市内电话的呼唤属于前者,而登记市外长途电话的呼唤属于后者。,排队规则,对于等待制,为顾客进行服务的次序可以采用下列各种规则: 先到先服务,后到先服务,随机服务,有优先权的服务等。 先到先服务(FCFS),即按到达次序接受服务,这是通常的情形。 后到先服务(LCFS
14、),如乘用电梯的顾客常是后人先出的。仓库中存放的厚钢板也是如此。在情报系统中,最后到达的信息往往是最有价值的,因而常采用后到先服务(指被采用)的规则。,排队规则,随机服务(SIRO) ,指服务员从等待的顾客中随机地选取其一进行服务,而不管到达的先后,如电话交换台接通呼唤的电话就是如此。 有优先权的服务(PR) ,如医院对于病情严重的患者将给予优先治疗。 (b)从占有的空间来看,队列可以排在具体的处所(如售票处、候诊室等),也可以是抽象的(如向电话交换台要求通话的呼唤)。 由于空间的限制或其它原因,有的系统要规定容量(即允许进入排队系统的顾客数)的最大限;有的没有这种限制(即认为容量可以是无限的
15、)。,排队规则,(c)从队列的数目看,可以是单列,也可以是多列。 在多列的情形,各列间的顾客有的可以互相转移,有的不能(如用绳子或栏杆隔开)。 有的排队顾客因等候时间过长而中途退出,有的不能退出(如高速公路上的汽车流),必须坚持到被服务为止。 我们将只讨论各列间不能互相转移、也不能中途退出的情形。,3)服务机构,从服务机构的形式和工作情况来看有以下几种情况。 (a)服务机构可以没有服务员,也可以有一个或多个服务员(服务台、通道、窗口等). 例如,在敞架售书的书店,顾客选书时就没有服务员,但交款时可能有多个服务员。,服务机构,(b)在有多个服务台的情形中,它们可以是平行排列(并列)的,可以是前后
16、排列(串列)的,也可以是混合的。下图说明这些情形。 图a是单队单服务台,图b是多队多服务台, 图c是单队多服务台(并列)的情形,图d是多服务台(串列)的情形,图e是多服务台(混合)的情形。,1,1,2,c,c,1,2,1,2,c,a,b,c,d,1,1,1,e,服务机构,(d) 服务方式可以对单个顾客进行,也可以对成批顾客进行,公共汽车对站台等候的顾客就成批进行服务,我们将只研究单个单个地服务方式。 (e)和输入过程一样,服务时间也分确定型的和随机型的。自动冲洗(服务)的时间就是确定 ,但大多数情形的服务时间是随机型的。对于随机型的服务时间,需要知道它的概率分布。 (f)和输入过程一样,服务时
17、间的分布我们总假定是平稳的,即分布的期望值、方差等参数都不受时间的影响。,服务时间分布:,设某服务台的服务时间为V,其密度函数为b(t),常见的分布有:,(1)定长分布(D):每个顾客接受服务的时间 是一个确定的常数。 (2)负指数分布(M):每个顾客接受服务时间 相互独立,具有相互的负指数分布: 其中 ,为一常数。,- 单位时间平均服务完成的顾客数 1/ - 每个顾客的平均服务时间,服务时间分布:,(3)k阶爱尔朗(Erlang)分布:每个顾客接受服务 时间服从k阶爱尔朗分布,其密度函数为:,Erlang Distribution (爱尔朗分布) 服务时间的波动量介于指数分布和常量之间 有一
18、个形状参数k决定其标准差,Erlang Distribution (爱尔朗分布),例如串列的k个服务台,每台服务时间相互独立,服从相同的负指数分布(参数ku),那么一顾客走完k个服务台总共所需要服务时间就服从上述的k阶爱朗分布。,注意:爱尔朗分布族提供更为广泛的模型类。比指数分布有更大的适应性。事实上,当k=1时,爱尔朗分布化为负指数分布,这可看成是完全随机时;当k增大时,爱尔朗分布的图形逐渐变为对称为;当k30时爱尔朗分布近似于正态分布;k时;由看出VarT0,因此这时爱尔朗分布化为确定型分布,所以一般k阶爱尔朗分布可看成完全随机与完全确定的中间型,能对现实世界提供更为广泛的适应性。,排队系
19、统的分类,D.G.Kendall在1953年提出一个分类方法,按照上述各部分的特征中最主要的、影响最大的三个,即 1相继顾客到达间隔时间的分布; 2服务时间的分布; 3服务台个数。,排队系统的分类,按照这三个特征分类,并用一定符号表示,称为Kendall记号。这只对并列的服务台(如果服务台是多于一个的话)的情形,他用的符号形式是: X/Y/Z 其中X处填写表示相继到达间隔时间的分布, Y处填写表示服务时间的分布, Z处填写并列的服务台数目。,排队系统的分类,表示相继到达间隔时间和服务时间的各种分布的符号是: M负指数分布(M是Markov的字头,因为负指数分布具有无记忆性,即Markov性)
20、D确定定型(Deterministic) Ekk阶爱尔朗(Erlang)分布 GI般相互独立(General Independent)的时间间隔的分布 G一般(General)服务时间的分布,排队系统的分类,例如: MM1表示相继到达间隔时间为负指数分布、服务时间负指数分布、单服务台的模型; DMc表示确定的到达间隔、服务时间为负指数分布、c个平行服务台(但顾客是一队)的模型。,排队系统的分类,以后,在1971年一次关于排队论符号标准化会议上决定,将Kendall符号扩充成为: XYZABC 形式,其中前三项意义不变, A处填写系统容量限制N, B处填写顾客源数目m, C处填写服务规则,如先到
21、服务FCFS,后到先服务LCFS 等。 并约定,如略去后三项,即指XYZFCFS的情形。在本节中,因只讨论先到先服务FCFS的情形,所以略去第六项。,例:M/M/s/K表示?,M/M/s/K表示相继到达间隔时间为负指数分布、服务时间负指数分布、s个服务台、系统容量为K的模型,例如 M / M / 1 / / 表示顾客到达过程服从负指数分布,服务时间服从负指数分布,一个服务台,排队的长度无限制和顾客的来源无限制。,其他模型,M/M/c/K/K 顾客来源是有限的服务系统. 例如: 一个饭店有 X 张桌子和 Y个服务生服务来源有限的顾客. M/D/1 服务时间不变的服务系统. D/M/1 确定性到达
22、模式, 及指数分布服务时间. 例如:医生赴约治病的时间表. M/E k/1 服务服从 Erlang 分布. 例如:用相同平均时间去完成一些程序。,排队问题的求解,一个实际问题作为排队问题求解时,首先要研究它属于哪个模型,其中只有顾客到达的间隔时间分布和服务时间的分布需要实测的数据来确定,其它因素都是在问题提出时给定的。解决排队问题首先要根据原始资料做出顾客到达间隔和服务时间的经验分布,然后按照统计学的方法(例如x2检验法)以确定合于那种理论分布,并估计它的参数值。,解排队问题的目的,解排队问题的目的,是研究排队系统运行的效率,估计服务质量,确定系统参数的最优值,以决定系统结构是否合理、研究设计
23、改进措施等。 所以必须确定用以判断系统运行优劣的基本数量指标,解排队问题就是首先求出这些数量指标的概率分布或特征数。,排队系统的指标,这些指标通常是: (1)队长,指在系统中的顾客数,它的期望值记作Ls; 排队长(队列长,指在系统中排队等待服务的顾客数,它的期望值记作Lq; Ls = Lq + 正在接受服务的顾客数 一般情形,Ls(或Lq)越大,说明服务率越低,排队成龙,是顾客最厌烦的。,排队系统的指标,(2)逗留时间,指一个顾客在系统中的停留时间,它的期望值记作Ws; (3)等待时间,指一个顾客在系统中排队等待的时间,它的期望值记作Wq, WS = Wq + 服务时间,排队系统的指标,在机器
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 企业管理 2010 暑期 培训 排队
![提示](https://www.31doc.com/images/bang_tan.gif)
链接地址:https://www.31doc.com/p-1999870.html