运筹学第五章排队论课件

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第五章 排队论(Queuing Theory),排队论（queuing),也称随机服务系统理论，是运筹学的一个主要分支。,1909年，丹麦哥本哈根电子公司电话工程师A. K. Erlang的开创性论文“概率论和电话通讯理论”标志此理论的诞生。排队论的发展最早是与电话，通信中的问题相联系的，并到现在是排队论的传统的应用领域。近年来在计算机通讯网络系统,、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到应用。,1,第五章 排队论(Queuing Theory),1.1 排队系统的组成与特征,排队系统一般有三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。现分别说明：,1 排队系统的基本概念,2,1.1 排队系统的组成与特征1 排队系统的基本概念2,输入即为顾客的到达，可有下列情况：,1）,顾客源可能是有限的，也可能是无限的。,2）,顾客是成批到达或是单个到达。,3）,顾客到达的间隔时间可能是随机的或确定的。,4）,顾客到达可能是相互独立的或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。,5）,输入过程可以是平稳的（stationary）或说是对时间齐次的（Homogeneous in time），也可以是非平稳的。输入过程是平稳的是指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非平稳的则是与时间相关，非平稳的处理比较困难。,1. 输入过程,3,输入即为顾客的到达，可有下列情况： 1. 输入过程3,2,. 排队规则,1）,顾客到达后接受服务分为即时制（损失制）和等待制。即时制不形成队列，而对于等待制将会形成队列，顾客可以按下规则接收服务：,（1,）,先到先服务 FCFS （2）后到先服务 LCFS （3）随机服务RAND （4）有优先权服务 PR。,2）,从队列的空间可分为有容量限制和无容量限制。,3）从队列数可分为单列和多列。,4,2. 排队规则,3,. 服务机构,1）服务机构可以是单服务员和多服务员服务，这种服务形式与队列规则联合后形成了多种不同队列，不同形式的排队服务机构，如：,5,3. 服务机构 1）服务机构可以是单服务员和多服务员服务,上述特征中最主要的、影响最大的是：,顾客相继到达的间隔时间分布,服务时间的分布,服务台数,D.G.Kendall，1953提出了分类法，称为Kendall记号,(适用于并列服务台)即：X/Y/Z:A/B/C,2)服务方式分为单个顾客服务和成批顾客服务。,3)服务时间分为确定型和随机型。,4)服务时间的分布在这里我们假定是平稳的。,1,.2 排队系统的模型分类,6,上述特征中最主要的、影响最大的是： 2)服务方式分为单个顾,式中：X顾客相继到达间隔时间分布。,M负指数分布,Markov,，,D确定型分布,Deterministic,，,E,k,K阶爱尔朗分布,Erlang,， GI 一般相互独立随机分布,(,General Independent,),，,G 一般随机分布。,Y填写服务时间分布（与上同）,Z填写并列的服务台数,A排队系统的最大容量,B顾客源数量,C排队规则,如,M/M/1,:,/FCFS,即为顾客到达为泊松过程，服务时间为负指数分布，单台，无限容量，无限源，先到先服务的排队系统模型。,7,式中：X顾客相继到达间隔时间分布。7,2 排队论基本理论总廓,2,.1 排队论研究的基本问题,1.排队系统的统计推断:即通过对排队系统主要参数的统计推断和对排队系统的结构分析，判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行研究。,2.系统性态问题:即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标,包括了瞬态和稳态两种情形。,3.最优化问题：即包括最优设计(静态优化)，最优运营（动态优化）。,8,2 排队论基本理论总廓2.1 排队论研究的基本问题8,2.2 排队问题求解(主要指性态问题),求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值，以便实现对现有系统合理改进和对新建系统的最优设计等。,排队问题的一般步骤：,1,. 确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布(可实测)。,2. 研究系统状态的概率。系统状态是指系统中顾客数。状态概率用P,n,(t)表示,即在t时刻系统中有n个顾客的概率，也称瞬态概率。,9,2.2 排队问题求解(主要指性态问题) 求解一般排队系,求解状态概率P,n,(t)方法是建立含P,n,(t)的微分差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此我们常常使用它的极限,(如果存在的话)：,稳态的物理意义见右图，系统的稳态一般很快都能达到，但实际中达不到稳态的现象也存在。值得注意的是求稳态概率,P,n,并不一定求,t的极限,而只需求,P,n,(t)=0,即可。,过渡状态,稳定状态,p,n,t,图3 排队系统状态变化示意图,称为稳态,(,steady state)解，,或称统计平衡状态,(,Statistical Equilibrium State),的解。,10,求解状态概率Pn(t)方法是建立含Pn(t)的微分差,3,.,根据排队系统对应的理论模型求出用以判断系统运行优劣的基本数量指标的概率分布或特征数。 数量指标主要包括:,(1),平均队长（L,s,）,:系统中的顾客数。,平均队列长（L,q,）,:系统中排队等待服务的顾客数。,系统中顾客数L,s,=系统中排队等待服务的顾客数L,q,+正被服务的顾客数,c,(2),平均逗留时间(Ws),:指一个顾客在系统中的停留时间。,平均等待时间(Wq),:指一个顾客在系统中排队等待的时间。,(3),忙期,：指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度）,4,.排队系统指标优化,含优化设计与优化运营。,问题1,系统中顾客数=平均队列长（L,q,）+1？,11,3.根据排队系统对应的理论模型求出用以判断系统运行优劣的基,2,.3 排队论主要知识点,排队系统的组成与特征,排队系统的模型分类,顾客到达间隔时间和服务时间的经验分布与理论分布,稳态概率P,n,的计算,标准的M/M/1模型(,M/M/1,:,/FCFS),系统容量有限制的,模型,M/M/1:N,/FCFS,顾客源有限模型,M/M/1,/M,/,FCFS,标准的M/M/C模型,M/M/C:,/FCFS,12,2.3 排队论主要知识点排队系统的组成与特征12,M/M/,C型系统和C个M/M/1型系统,系统容量有限制的多服务台模型(M/M/C/N/,),顾客源为有限的,多服务台模型,(M/M/C/M),一般服务时间的（M/G/1）模型,Pollaczek-Khintchine(P-K) 公式,定长服务时间 M/D/1模型,爱尔朗服务时间M/E,k,/1模型,排队系统优化,M/M/1 模型中的最优服务率u,标准的M/M/1Model,系统容量为N的情形,M/M/C模型中最优服务台数C,13,M/M/C型系统和C个M/M/1型系统13,3 到达间隔时间分布和服务时间的分布,一个排队系统的最主要特征参数是顾客的到达间隔时间分布与服务时间分布。要研究到达间隔时间分布与服务时间分布需要首先根据现存系统原始资料统计出它们的,经验分布,（见P315319），然后与理论分布,拟合,，若能照应，我们就可以得出上述的分布情况。,14,3 到达间隔时间分布和服务时间的分布 一个排队系统的,3.1 经验分布,经验分布是对排队系统的某些时间参数根据经验数据进行统计分析，并依据统计分析结果假设其统计样本的总体分布，选择合适的检验方法进行检验，当通过检验时，我们认为时间参数的经验数据服从该假设分布。,分布的拟合检验一般采用,2,检验。由数理统计的知识我们知：若样本量,n,充分大(,n50)，,则当假设,H,0,为真时，统计量总是近似地服从自由度为,k-r-1,的,2,分布，其中,k为分组数，r,为检验分布中被估计的参数个数。,15,3.1 经验分布 经验分布是对排队系统的某些,3.2,理论分布,式中,为常数,(,0)，称X服从参数为的泊松分布，若在上式中引入时间参数t，即令t代替，则有：,1,.泊松分布,在概率论中，我们曾学过泊松分布，设随机变量为X，则有：,n=0,1,2, （1）,与时间有关的随机变量的概率,，是一个,随机过程,，即,泊松过程,。,t0，n=0,1,2, （2）,16,3.2 理论分布 式中为常数(0)，,（t,2,t,1,，n,0）,若设N(t)表示在时间区间0,t)内到达的顾客数(t0),P,n,(t,1,t,2,)表示在时间区间t,1,t,2,)(t,2,t,1,)内有n(0)个顾客到达的概率。即：,在一定的假设条件下 顾客的到达过程就是一个泊松过程。,当P,n,(t,1,t,2,)符合下述三个条件时，顾客到达过程就是泊松过程(,顾客到达形成普阿松流,)。,17,（t2t1，n0） 若设N(t)表示在时间区间0,无后效性：,各区间的到达相互独立,即Markov性。,也就是说过程在t+t所处的状态与,t,以前所处的状态无关。,平稳性：,即对于足够小的t，有：,普阿松流具有如下特性：,在t,t+t内有一个顾客到达的概率与t无关,而与t成正比。,18, 无后效性：各区间的到达相互独立,即Markov性。 也,普通性：,对充分小的,t,在时间区间（,t,t+,t）内有2个或2个以上顾客到达的概率是一高阶无穷小.,由此知，在(t，t+,t)区间内没有顾客到达的概率为：,令,t,1,=0,t,2,=t,则P(t,1,t,2,)=P,n,(0,t)=P,n,(t),0 是常数，它,表示单位时间到达的顾客数，称为概率强度。,即,P,0,+P,1,+P,2,=1,在上述假设下，t时刻系统中有n个顾客的概率p,n(t),：,19, 普通性：对充分小的t,在时间区间（t,t+,(1),(2),当n=0时，则,(3),（没有顾客到达的概率）,（,n个顾客到达的概率）,（4）,瞬态方程,（1）、（2）两式求导并令导数为0，得稳态概率：,20,(1)(2)当n=0时，则(3)（没有顾客,级数,令k=n-1，则：,同理方差为：,顾客到达过程是一个,泊松过程(泊松流)。,期望,21,级数令k=n-1，则：同理方差为：顾客到达过程是一个泊松过,表示单位时间内顾客平均到达数。,1/,表示顾客到达的平均间隔时间。,对顾客的服务时间,：,系统处于忙期时,两顾客相继离开系统的时间间隔,，一般地也服从负指数分布，,接受服务，然后离开,服务时间的分布：,2.负指数分布,可以证明,当输入过程是泊松流时，两顾客相继到达的时间间隔T,独立且服从负指数分布。（等价）,，则,22,表示单位时间内顾客平均到达数。对顾客的服务时间：,其中：,表示单位时间内能被服务的顾客数，即平均,服务率。,1/,表示一个顾客的平均服务时间。,3.爱尔朗(Erlang)分布,设v,1, v,2,，, v,k,是k个独立的随机变量，服从相同参数,k,的负指数分布，那么：,，则,令,，则,称为服务强度,。,23,其中：表示单位时间内能被服务的顾客数，即平均 3.爱,串联的k个服务台,，每台服务时间相互独立，服从相同的负指数分布（参数k,），那么一顾客走完k个服务台总共所需要服务时间就服从上述的k阶Erlang分布。,则称T服从k阶,爱尔朗分布。其特征值为：,其概率密度是,1/ k,表示一个顾客的一个服务台的平均服务时间。,24,串联的k个服务台，每台服务时间相互独立，服从相同的负指,例,:有易碎物品500件,由甲地运往乙地,根据以往统计资料,在运输过程中易碎物品按普阿松流发生破碎,其破损率为0.002,现求:1.破碎3件物品的概率;2.破碎少于3件的概率和多于3件的概率;3.至少有一件破损的概率.,解: ,=0.002500=1,1破碎3件物品的概率为:,P(k=3)=(,3,/3！)e,-,=(1,3,/3！)e,-1,=0.0613,即物品破碎3件的概率为6.13,2.破碎物品少于3件的概率:,25,例:有易碎物品500件,由甲地运往乙地,根据以往统计资, 破碎物品少于3件的概率为91.97,破碎物品多于3件的概率为:,3.至少有一件破碎的概率为,Pk,1=1-(1,k,/k!)e,-,=1-(1,0,/0!)e,-1,=0.632,26, 破碎物品少于3件的概率为91.973.至少有一件破碎的,对排队模型，在给定输入和服务条件下，主要研究系统的下述运行指标：,(1)系统的,平均队长Ls,(期望值)和,平均队列长Lq,(期望值)；,(2)系统中,顾客平均逗留时间Ws,与队列中,平均等待时间Wq,；,本节只研究M/M/1模型，下面分三种情况讨论：,4.M/M/1模型,27,对排队模型，在给定输入和服务条件下，主要研究系统的下,4.1 标准的M/M/1模型,系统中有n个顾客,M/M/1:,/FCFS模型,1.稳态概率P,n,的计算,在任意时刻t，状态为n的概率P,n,(t)（瞬态概率），它决定了系统的运行特征。,已知顾客到达服从参数为的泊松过程，服务时间服从参数为的负指数分布。现仍然通过研究区间,t，t+,t）的变化来求解。在时刻,t+,t，系统中有n个顾客不外乎有下列四种情况（ ,t，t+,t）内到达或离开,2个以上,没列入）。,？,28,4.1 标准的M/M/1模型 系统中有n个顾客M/,由于这四种情况是互不相容的，所以P,n,(t+,t)应是这四项之和，则有：,所有的高阶无穷小合并,29,由于这四种情况是互不相容的，所以Pn(t+t,令,t0，得关于P,n,(t)的微分差分方程：,(1),当n=0时，只有表中的（A）、（B）两种情况，因为在较小的,t内不可能发生（D）（到达后即离去），若发生可将t取小即可。,(2),生灭过程,瞬态解,30,令t0，得关于Pn(t)的微分差分方程：(1),由此可得该排队系统的,状态转移图,：,由（4）得：,其中,服务强度,将其代入（3）式并令n=1,2,(也可从状态转移图中看出状态平衡方程)得：,关于P,n,的差分方程,n-1,n,n+1,2,0,1,稳态时，,它对时间的导数为0，所以由(1)、(2)两式得：,P,n,(t)与时间无关,可以写成P,n,(3),(4),31,由此可得该排队系统的状态转移图：由（4）得：其中服务强,n=1,n=2,32,n=1n=232,以此类推，当n=n时，,(5),以及概率性质知：,(数列的极限为 ),(6),否则排队无限远,系统稳态概率,系统的运行指标,33,以此类推，当n=n时，(5)以及概率性质知：(数列,2. 系统的运行指标计算,(1) 系统中的队长L,s,（平均队长）,(01),即:,(7),期望,34,2. 系统的运行指标计算(01)即:(7)期望3,(2) 队列中等待的平均顾客数L,q,(8),(3) 顾客在系统中的平均逗留时间W,s,顾客在系统中的逗留时间是随机变量，可以证明，它服从参数为,-,的负指数分布，分布函数,35,(2) 队列中等待的平均顾客数Lq(8) (3) 顾,和密度函数为：,（,w,0）,(4)顾客在队列中的平均逗留时间W,q,等待时间,顾客在队列中的平均逗留时间应为W,s,减去平均服务时间。,考虑L,S,与W,S,的关系,36,和密度函数为：（w0） (4)顾客在队列中的平均逗留,四个指标的关系为(,Little 公式,),：,3. 系统的忙期与闲期,系统处于空闲状态的概率：,系统处于繁忙状态的概率：,服务强度,37,四个指标的关系为(Little 公式)： 3. 系统的忙期与,在繁忙状态下，队列中的平均顾客数L,b,：,顾客平均等待时间:,忙期的平均长度:,(由 来),一个忙期平均服务的顾客数为：,L,b,P,(N0),=L,q,38,在繁忙状态下，队列中的平均顾客数Lb：顾客平均等待时间:忙期,例,考虑一个铁路编组站，设待编列车到达时间间隔服从负指数分布，平均到达2列/小时，服务台是编组站，服务时间服从负指数分布，平均每20分钟可服务一组。已知编组站到达场共有2股道，当均被占用时，不能接车，再来的列车只能停在站外或前方站。求在平稳状态下系统中列车的平均数；每一列车的平均停留时间；等待编组的列车的平均数；如果列车因站中地股道均被占用而停在站外或前方站时，每列列车的费用为,元/小时，求每天由于列车在站外等待而造成的损失。,39,例 考虑一个铁路编组站，设待编列车到达时间间隔服从负指数分,