第六章 排队论

.,第六章随机服务系统理论,确定型只是随机现象的特例,QueuingTheory,.,2,6.1随机服务系统基础,系统的输入与输出是随机变量A.k.Erlang于19091920年发表了一系列根据话务量计算电话机键配置的方法，为随机服务理论奠定了基础又称为排队论(QueuingTheory)或拥塞理论(CongestionTheory),应用广泛交通行业应用：交叉口/高速收费站/机场航班,.,3,顾客来源,队列,服务机构,排队系统,顾客,服务完离开,排队系统的三个基本组成部分.输入过程(顾客按照怎样的规律到达);排队规则(顾客按照一定规则排队等待服务);服务机构(服务机构的设置,服务台的数量,服务的方式,服务时间分布等),6.1.1基本要素,.,4,输入过程,顾客源有限无限经常性的顾客来源顾客到达间隔时间:到下一个顾客到达的时间服从某一概率分布（确定型/随机型）顾客的行为假定在未服务之前不会离开当看到队列很长的时候离开从一个队列移到另一个队列,.,5,排队服务规则,队列容量有限/无限排队规则损失制等待制：先到先服务(FCFS)，后到先服务(LCFS)，随机服务(RS)，优先权服务(PS)混合制逐个到达，成批服务；成批到达，逐个服务,.,6,单通道和多通道并联服务串联服务串并联服务,服务机构的组织方式与服务方式,1,2,3,顾客到达,顾客离开,银行服务-叫号系统,机场安全检查通道,.,7,常用符号M泊松分布（负指数分布）Ekk阶爱尔朗分布D确定型分布G一般分布M/M/1/K/FCFS顾客到达服从泊松分布，顾客的服务时间服从负指数分布，单通道，系统容量有限（K）而顾客源无限，先到先服务的排队系统,顾客到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量/顾客总体数量/排队规则(扩充的Kendall符号)-Kendallsnotation,6.1.2符号表示,.,8,队长：系统中的顾客数量的期望值排队长：系统中正在等待的顾客数量期望值逗留时间：顾客在排队系统中的总时间（等待时间与被服务时间之和）的期望值排队时间：顾客的排队等待时间的期望值忙期：服务机构连续繁忙的时间长度服务强度：顾客到达率的期望值与服务率的期望值之比,6.1.3排队系统营运指标,.,9,服务系统存在来自两个矛盾方面的要求顾客希望服务质量好，如排队等待时间短，损失率低系统运营方希望设备利用率高给用户一个经济上能够承受的满意的质量哪些系统特性会影响系统的性能？服务机构的组织方式与服务方式顾客的输入过程和服务时间分布系统采用的服务规则,与服务系统性能相关的特性,6.2顾客到达分布和服务时间分布,6.2.1概述顾客的服务时间由于多种原因具有不确定性，最好的描述方法就是概率分布；同样顾客到达的间隔时间也服从一定的概率分布,.,11,若统计区间分得越细，样本越多，则经验分布的轮廓越接近曲线,经验分布一般采用直方图来表示，如下图,FrequencyDistribution,服务时间和到达间隔时间服从什么分布？可以先通过统计得到经验分布，然后再做理论假设和检验,.,12,6.3.2输入过程（顾客到达分布）,可用相继到达顾客的间隔时间描述，也可以用单位时间内到达的顾客数描述间隔时间服从定长分布（DeterministicDistribution）间隔时间服从爱尔朗分布（Erlangdistribution）二项分布（binomialdistribution）单位时间t（或时间区间t）内到达的顾客数服从泊松分布(法国数学家Poisson,1836)最简单流（泊松流）（PoissonDistribution）负指数分布（NegativeExponentialDistribution）,.,13,6.3.2.1最简单流（泊松流）-纯生过程,(1)泊松流形成条件,流的平稳性,对于任意的t0及t0，在时间区间(t,t+t)内有n个顾客到达的概率只与t有关，与时间区间的起点t无关。当t充分小时，在(t,t+t)内有一个顾客到达的概率与t成正比，即其中，O(t)是当t0时，关于t高阶无穷小；为单位时间内的顾客到达平均数。,.,14,在时间轴上，互不相交的时间区段和内，顾客的到达数是相互独立的，即前一顾客的到达不影响后一顾客的到达。,流的无后效性,当t充分小时，在t时间内到达一个顾客的概率为t+o(t)，到达两个或两个以上顾客的概率为o(t)；即两个顾客不可能同时到达,流的普遍性,设把长为t的时间区间分成m等分，每段长度为。若在dt内，有一个顾客到达，则称被“占着”，如果在dt内，没有顾客到达，则称为“空着”。被“占着”的概率近似为被“空着”的概率近似,在长为t的时间区间内，到达n个顾客的概率,根据流的无后效性，在m个dt中，有顾客到达与没有顾客到达可以看成是m次独立的试验,(2)泊松流详解,.,16,在长为t的时间区间内，到达n个顾客的概率,在m个dt中，有n个dt被顾客“占着”的概率,利用二项定律,.,17,dt0，m,.,18,符合最简单流（泊松流）的随机事件发生规律,单位时间t内有n个顾客到达的概率,顾客的平均到达率,(3)泊松分布,.,19,（4）泊松输入过程及其特点,1)平稳性：顾客到达数只与时间区间长度有关2)无后效性：不相交的时间区间内所到达的顾客数是独立的3)普遍性：在t时间内到达一个顾客的概率为t+o(t)，到达两个或两个以上顾客的概率为o(t)；即两个顾客不可能同时到达泊松过程具有可迭加性即独立的泊松分布变量的和仍为泊松分布,.,20,泊松过程的到达间隔时间为负指数分布令h代表间隔时间，则概率Pht代表时间区间t内没有顾客来的概率；由泊松分布可知：P0(ht)=Pht=et故间隔时间h的分布为Pht=1et,（1）推导,n=0,6.3.2.2负指数分布,.,21,（2）负指数分布的特点,负指数分布之所以常用，是因为它有很好的特性，使数学分析变得方便无记忆性。指的是不管一次服务已经过去了多长时间，该次服务所剩的服务时间仍服从原负指数分布,.,22,如果顾客的到达过程服从最简单流，则顾客单位时间内的到达数服从泊松分布。如果顾客的到达过程服从最简单流，则顾客到达的时间间隔服从负指数分布。从本质上看，泊松分布与负指数分布是同一个过程的不同表现形式。可适用于服务时间分布,6.3.3小结,.,23,负指数分布,泊松分布,在单位时间t内，到达n个顾客的概率,顾客到达时间间隔大于单位时间t的概率,顾客到达时间间隔小于单位时间t的概率,顾客的平均到达率,.,24,例-1,一售货员出售两种商品A和B，每日工作8小时。购买每种商品的顾客到达过程为泊松分布，到达率分别为A=8人/日，B=16人/日，试求：(1)1小时内来到顾客总数为3人的概率；(2)三个顾客全是购买B类商品的概率。解：(1)总到达率为A+B=24人/日，1小时=1/8日，故,(2)3个顾客全是购买B类商品的概率为,.,25,例-2,某铁路与公路相交的平面交叉口，当火车通过交叉口时，横木护栏挡住汽车通行。每次火车通过时，平均封锁公路3min，公路上平均每分钟有4辆汽车到达交叉口。求火车通过交叉口时，汽车排队长度超过100m的概率（即排队汽车超过12辆的概率）。,.,26,Homework,P1862,.,27,研究系统内部状态变化的过程,系统状态i,状态i+1,状态i-1,在t时刻内发生两个或两个以上事件的概率为O(t),一个事件,一个事件,t0，O(t)0,6.4生灭过程（BirthandDeathProcesses）,6.4.1定义,系统具有0,1,2,个状态。在任何时刻，若系统处于状态i，并且系统状态随时间变化的过程满足以下条件，称为一个生灭过程：,N(t)表示时刻t系统中的顾客数。N(t)，t0为一随机过程。,.,28,(1)在（t,t+t）内系统由状态i转移到状态i+1的概率为it+O(t)平稳性条件,(2)在（t,t+t）内系统由状态i转移到状态i-1的概率为it+O(t)平稳性条件,t内有一个顾客离开的概率,t内有一个顾客到达的概率,(3)在（t,t+t）内系统发生两次以上转移的概率为O(t)，即有2个以上顾客到达或离开的概率为,普遍性条件,排队系统的输入过程和服务过程符合泊松分布，则排队过程符合生灭过程,.,29,状态（Status）,顾客到达率（Birthrate）,系统服务率（Deathrate）,可以证明：t时，Pi(t)趋向于常数：系统达到稳定,6.4.2状态转移图,.,30,系统达到稳定后：每个状态转入率的期望值与转出率的期望值相等。,对于状态i：转出率的期望值为,转入率的期望值为,P0,P1,P2,Pi,6.4.3状态转移方程,.,31,则,对于S0,转入,转出,转入,转出,对于Sk,P0,P1,P2,Pi,.,32,状态转移方程,求解该方程，可以获得各状态对应的概率,.,33,对于S0,对于S1,依次类推,且有,.,34,6.4.4满足生灭过程的条件,系统的输入过程和服务过程具有平稳、无记忆性和普通性服务台是独立的、相同的、并联的波松输入过程和负指数服务时长就具有这些性质可以用马氏链来描述系统的状态转移这种系统称为生灭服务系统，一般用M/M/n表示，又称为标准服务系统；标准服务系统的形式很多，但都是基于生灭方程，关键是找出j,j的不同表达式，将它们代入生灭方程标准服务系统的表示法：(X/Y/Z:A/B/C)，X表示输入过程，Y表示服务过程，Z表示并联服务台的个数，A表示系统容量，B表示顾客源，C表示服务规则(M/M/n:m/FCFS)表示波松输入，负指数服务时长，n个并联服务台，系统容量为m,mn，顾客源无穷，先到先服务D定长分布；Ekk阶爱尔兰分布；G一般独立分布,.,35,6.4.5生灭过程推导（补充参考）,采用马氏链令N(t)代表系统在时刻t的状态，下一瞬间t+t系统的状态只能转移到相邻状态，或维持不变，如图所示三种转移是不相容的，三者必居其一只有具有无记忆性和普通性的过程(分布)才适用马氏链令Pj(t)=PN(t)=j代表系统在时刻t处于状态j的概率,.,36,生灭过程的马氏链,根据马氏链，应用全概率公式，有状态转移概率方程,另有两个边界方程,.,37,生灭方程的推导过程,将上述三个差分方程化为微分方程,上述三个方程是动态方程，当系统处于稳态时，系统处于统计平衡状态，即状态概率不随时间变化，从而状态概率导数为0；令上三个方程左侧为0，得稳态方程组,.,38,生灭过程稳态解,方程(1),(2),(3)与稳态状态转移图一一对应；递归解如下：,.,39,例：,某排队系统：M/M/1/3/FCFS，=2，=3。求解各状态对应的概率。,首先，做出相应的状态转移图,对于S0,对于S1,对于S2,.,40,6.4.6纯生过程,令生灭过程中所有消亡率j=0，即只有顾客到达，没有顾客离去令所有j=，且系统服务台无限，即n容易得到下列微分方程组,该问题没有稳态解，正是泊松过程,.,41,生灭过程求解排队系统各状态概率过程,建立状态转移图,建立状态转移方程,求解状态转移方程,各状态转入率期望值与转出率期望值相等,各状态概率,统计平衡下的“流入=流出”原理,生灭平衡,.,42,Homework：利用生灭过程求解以下排队系统各状态的概率。,S0,S1,S2,S3,2,2,3,2,4,3,.,43,第三节M/M/1排队系统,顾客到达服从泊松分布顾客到达率为服务过程服从泊松分布（负指数分布）系统服务率为单通道，先到先服务（FCFS）,最简单的M/M/1排队系统：,M/M/1/,M/M/1/m/,.,44,M/M/1/排队系统,系统容量无限、顾客源无限,最基本的排队系统,排队过程为生灭过程过程,.,45,S0,S1,S2,Si-1,Si,Si+1,P0,P1,P2,Pi,列状态转移方程组求各状态概率,.,46,M/M/1/排队系统各状态概率归结为无穷等比数列求和,1，数列发散,系统稳定,系统不稳定,称为服务强度，若服务强度大于1，说明单位时间内到达的顾客数比完成服务的顾客数多，系统中排队长度越来越大，产生阻塞。,.,47,利用排队系统各状态概率计算运行指标,1、队长系统中的顾客数量,队长,.,48,2、排队长系统中等待的顾客数量,通道数,.,49,3、逗留时间顾客在排队系统中的总时间,李太勒公式-1（LittleFormula）,前后2名顾客到达系统的平均时间间隔,适用于任何排队系统。,.,50,4、排队时间顾客在排队系统中的等待时间,李太勒公式-2,前后2名顾客到达系统的平均时间间隔,.,51,排队系统运营指标及相互关系：,.,52,.,53,例1,某医院急诊室同时只能诊治一个病人，诊治时间服从负指数分布，每个病人平均需要15分钟。病人按泊松分布到达，平均每小时到达3人。试对此排队队系统进行分析。,（1）确定参数值：,服务强度：,.,54,急诊室繁忙（需要等待）的概率:,（2）稳态概率：,这就是急诊室空闲的概率，也是病人不必等待立即就能就诊的概率。,.,55,病人平均等候时间：,急诊室内外的病人平均数：,急诊室外排队等待的病人平均数：,病人在急诊室内外平均逗留时间：,.,56,15123min即平均服务时间至少应减少3min,为使病人平均逗留时间不超过半小时，那么平均服务时间应减少多少？,代入=3，解得5，平均服务时间为：,.,57,若医院希望候诊的病人90%以上都能有座位,则候诊室至少应安置多少座位?设应该安置个座位,加上急诊室的一个座位,共有+1个。要使90%以上的候诊病人有座位，相当于使“来诊的病人数不多于+1个”的概率不少于90%，即,.,58,两边取对数（x2）lglg0.1因1，故,所以6即候诊室至少应安置6个座位。,.,59,例：,某修车店只有一个修理工，来修理的顾客到达过程服从Poisson流，平均4人/小时；修理时间服从负指数分布，平均需要6分钟，试求：1）修理店空闲的概率；2）店内恰有3个顾客的概率；3）店内至少有1个顾客的概率；4）在店内的平均顾客数；5）每位顾客在店内的平均逗留时间；6）等待服务的平均顾客数；7）每位顾客平均等待服务时间；8）顾客在店内等待时间超过十分钟的概率。,.,60,M/M/1/m/排队系统,系统容量有限、顾客源无限,.,61,列状态转移方程组求各状态概率,S0,S1,S2,Si-1,Si,Si+1,P0,P1,P2,Pi,.,62,并不要求1。,特别地，当=1时，P0=1/(m+1),(1),.,63,利用排队系统各状态概率计算运行指标,1、队长系统中的顾客数量,队长,.,64,2、排队长系统中等待的顾客数量,通道数,.,65,3、逗留时间顾客在排队系统中的总时间,李太勒公式,前后2名顾客到达系统的平均时间间隔,.,66,有效到达率e,当排队长度未满容量时，平均到达率为当排队容量已满容量时，平均到达率为0,逗留时间,.,67,4、排队时间顾客在排队系统中的等待时间,李太勒公式,前后2名顾客到达系统的平均时间间隔,.,68,.,69,作业-1,汽车通过一检查站时进行验证。汽车按泊松分布到达检查站，平均间隔0.6分钟，验证时间平均为15秒（验证时间服从负指数分布）。请分析该排队系统，求该排队系统各状态对应的概率，以及队长、排队长、顾客逗留时间、顾客等待时间等运行指标。,.,70,作业-2,某汽修店只有一个修理工，且站内最多只能停放3台机器。设待修机器按Poisson流到达修理店，平均每小时到达1台；修理时间服从负指数分布，平均每1.25小时可修理1台，试求该系统的有关指标。（要求列出状态转移图）,.,鱼与熊掌兼得？,顾客的到达是服务参数的泊松分布；顾客的服务时间是服从参数为的负指数分布；有S个服务台，顾客按到达的先后次序接受服务。,第四节M/M/S排队系统,.,72,当顾客到达时，若有空闲的服务台就立即接受服务，若所有的服务台都忙着，则顾客排成一个队列等待服务。,.,73,常见的M/M/S/及M/M/S/m/两类,.,74,M/M/S/排队系统标准M/M/S系统,.,75,系统中个服务台的服务率均为，于是整个服务机构的最大服务率为S。与M/M/1/系统类似，只有当时，才能使服务系统达到稳态而不排成无限的队列。,系统的服务强度,.,76,当系统中只有一个顾客时，则有S-1个服务台空闲着，仅一个服务台在服务，这时的服务率为，当系统有2个顾客时，就有2个服务台工作，其服务率为2，当系统中有S个顾客时，则服务率达到最大值S，当系统中的顾客数超过S时，由于个服务台都忙着，其余顾客必须排队，这时的服务率仍为S,.,77,M/M/1系统,M/M/S系统,.,78,M/M/S系统,.,79,根据正则条件,.,80,利用排队系统各状态概率计算运行指标,1、排队长,.,81,2、平均等候时间,.,82,3、逗留时间,、平均顾客数,.,83,系统容量受限制、顾客源无限、先到先服务的M/M/S系统。该系统共有m-S个位置可供顾客排队。当顾客到达时，若系统饱和，即服务台都忙着，排队位置已排满，则后到的顾客立即离去，另求服务。因此，该系统中只可能有m+1个状态。,M/M/S/m/排队系统,.,84,与M/M/S/系统的推导类似，可得M/M/S/m/系统的状态指标及运行指标。,.,85,假设医院增强急诊室的服务能力，使其同时能诊治两个病人，且平均服务率相同，试分析该系统工作情况，并且，例1、例2的结果进行比较。,解这相当于增加了一个服务台，故有：S=2,=3人/h，=4人/h,例1-Continued,.,86,病人必须等候的概率,即系统状态N2的概率：,.,87,两系统运营指标对比,.,88,例某储蓄所内，已知忙时顾客到达率=40人/小时，窗口营业员服务率为=16人/小时，要求：(1)工时利用率不低于60%；(2)顾客平均等待时间不超过5分钟；问：设几个窗口适当。解：系统是无限源M/M/s等待制。=/=40/16=2.5Erl(1)*=/s0.6，解出s4.17，故s可取值3，4(2)n=3时，p0=(