第14章 排队论.pptVIP

1,第十四章排队论,1排队过程的组成部分2单服务台泊松到达、负指数服务时间的排队模型3多服务台泊松到达、负指数服务时间的排队模型4排队系统的经济分析5单服务台泊松到达、任意服务时间的排队模型6单服务台泊松到达、定长服务时间的排队模型7多服务台泊松到达、任意的服务时间、损失制排队模型8顾客来源有限制排队模型9单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型10多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型*11生灭过程及生灭过程排队系统,2,一、基本概念一些排队系统的例子排队系统顾客服务台服务电话系统电话呼叫电话总机接通呼叫或取消呼叫售票系统购票旅客售票窗口收款、售票设备维修出故障的设备修理工排除设备故障防空系统进入阵地的敌机高射炮瞄准、射击，敌机被击落或离开排队的过程可表示为：,排队,服务机构服务,服务后顾客离去,排队系统,顾客到达,1排队过程的组成部分,3,考虑要点：1、服务台（或通道）数目：单服务台（单通道）、多服务台（多通道）。2、顾客到达过程：本教材主要考虑顾客的泊松到达情况。满足以下四个条件的输入流称为泊松流（泊松过程）。*平稳性：在时间区间t,t+t)内到达k个顾客的概率与t无关，只与t有关，记为pk(t）；*无后效性：不相交的时间区间内到达的顾客数互相独立；*普通性：在足够短的时间内到达多于一个顾客的概率可以忽略；*有限性：任意有限个区间内到达有限个顾客的概率等于1。泊松分布为单位时间平均到达的顾客数P(x)=xe-/x!(x=0,1,2,),1排队过程的组成部分,4,1排队过程的组成部分,3、服务时间分布：服从负指数分布，为平均服务率，即单位时间服务的顾客数，P（服务时间t)=1-e-t。4、排队规则分类(1)等待制：顾客到达后，一直等到服务完毕以后才离去，先到先服务，后到先服务，随机服务，有优先权的服务；(2)损失制：到达的顾客有一部分未接受服务就离去。5、平稳状态：业务活动与时间无关。,5,排队系统的符号表示:一个排队系统的特征可以用五个参数表示，形式为：ABCDE其中A顾客到达的概率分布，可取M、D、G、Ek等；B服务时间的概率分布，可取M、D、G、Ek等；C服务台个数，取正整数；D排队系统的最大容量，可取正整数或；E顾客源的最大容量，可取正整数或。例如M/M/1/表示顾客到达过程服从泊松分布，服务时间服从负指数分布，一个服务台，排队的长度无限制和顾客的来源无限制。,1排队过程的组成部分,6,M/M/1/单位时间顾客平均到达数，单位平均服务顾客数()数量指标公式:1.系统中无顾客的概率P0=1/2.平均排队的顾客数Lq=2/()3.系统中的平均顾客数Ls=Lq+/4.顾客花在排队上的平均等待时间Wq=Lq/5.顾客在系统中的平均逗留时间Ws=Wq+1/6.顾客得不到及时服务必须排队等待的概率Pw=/7.系统中恰好有n个顾客的概率Pn=(/)nP0,1排队过程的组成部分,2单服务台泊松到达、负指数服务时间的排队模型,7,2单服务台泊松到达、负指数服务时间的排队模型,在上面的公式中，我们都认定,即到达率小于服务率，如果没有这个条件，则排队的长度将无限制地增加，服务机构根本没有能力处理所有到达的顾客，0.1,所以不符合要求。当c=4时，因此，设置四个电话很合适。,7多服务台泊松到达、任意的服务时间、损失制排队模型,25,M/M/1/m条件：单位时间顾客平均到达数单位平均服务顾客数关心的项目:1.系统中无顾客的概率P02.系统中平均排队的顾客数Lq3.系统中的平均顾客数Ls4.系统中顾客平均的排队等待时间Wq5.系统中顾客的平均逗留时间Ws6.系统中顾客必须排队等待的概率Pw7.系统中恰好有n个顾客的概率Pn,8顾客来源有限制的排队模型,26,M/M/1/m数量指标公式:1.系统中无顾客的概率2.平均排队的顾客数3.系统中的平均顾客数Ls=Lq+(1-p0)4.顾客在排队上的平均花费等待时间Wq=Lq/（m-Ls)5.在系统中顾客的平均逗留时间Ws=Wq+1/6.系统中有n个顾客的概率,n=0,1,2,m,8顾客来源有限制的排队模型,27,例4.某车间有5台机器，每台机器连续运转时间服从负指数分布，平均连续运转时间为15分钟，有一个修理工，每次修理时间服从负指数分布，平均每次12分钟，求该排队系统的数量指标P0,Lq,Ls,Wq,Ws,以及P5。解：这是一个M/M/1/5系统。其中，m=5,=1/15,=1/12,/=0.8。Lq=2.766;Ls=3.759Wq=33.43;Ws=45.43P5=0.2870,=0.0073,8顾客来源有限制的排队模型,28,9单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型,这种模型我们记为M/M/1/K/，这个记法中的第四位字母K表示这个系统的最大容量为N，因为这是一个单服务台的情况，所以排队的顾客服务最多为K-1，在某时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统。这个模型可简写为M/M/1/K。由于所考虑的排队子系统中最多只能容纳K个顾客（等待位置只有K-1个），因而有:,令，有：,1.系统里没有顾客的概率,2.在系统里的平均顾客数,3.平均的排队顾客数,29,9单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型,4.有效顾客到达率,5.一位顾客花在排队上的平均时间,6.一位顾客在系统中的平均逗留时间,7.在系统里正好有n个顾客的概率,30,9单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型,例5某理发店只有一个理发师，且店里最多可容纳4名顾客，设顾客按泊松流到达，平均每小时5人，理发时间服从负指数分布，平均每15分钟可为1名顾客理发，试求该系统的有关指标。解：该系统可以看成一个M/M/1/4排队系统，其中,31,9单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型,系统里平均顾客数,=,平均的排队顾客数,平均逗留时间,平均排队时间,32,10多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型,这种排队模型我们记为M/M/C/K/，这与第九节单服务台模型的区别，就在于服务台的数量为C，我们可以把这个模型简记为M/M/C/K。在此系统中到达率与服务率分别为:,1.系统里没有顾客的概率2.系统里正好有n个顾客的概率,33,10多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型,3.平均排队顾客数,4.系统里的平均排队顾客数,5.有效到达率,6.顾客花在排队上的平均时间,7.顾客在系统里的平均逗留时间,特别地，当k=c时即为第七节的M/M/C/C/的模型。,34,10多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型,例6某公司维修服务中心有两名维修工，中心内至多可以停放6台机器（包括正在维修的两台机器）。假设待修机器按泊松分布过程到达此中心。平均每小时3台。维修每台机器平均需要20分钟，试求该系统的各项性能指数。解：该子系统可看成一个M/M/2/6排队系统,35,11*生灭过程及生灭过程排队系统,1.生灭过程生灭过程是一类非常简单具有广泛应用的一类随机过程，很多排队模型中都假设其状态过程为生灭过程；这样的排队子系统如：M/M/C和M/M/C/R，我们也可称之为生灭过程的排队系统。在这样的排队系统中，一个新顾客的到达看作“生”，一个顾客服务完之后离开系统看作是“死”，设N(t)的任意时刻t排队系统的状态（即排队子系统中的总顾客数），则对M/M/C/K系统N(t)具有有限个状态0，1，,k,对M/M/C来说N(t)具有可列个状态0，1，2。一般来说，随机过程满足以下条件，称为生灭过程：1)假设N(t)=n，则从时刻t起到下一个顾客到达时刻为止的时间服从参数为的负指数分布，n=0,1,2,2)假设N(t)=n，则从时刻t起到下一个顾客离去时刻为止的时间服从参数为的负指数分布，n=0,1,2,3)同一时刻时只有一个顾客到达或离去。,36,11*生灭过程及生灭过程排队系统,2.生灭过程稳态方程,方程为：,由此可求得生灭过程的平稳状态分布：,由于,即有,即有,即有,37,11*生灭过程及生灭过程排队系统,即当,时，此生灭过程存在平稳状态分布：,38,11*生灭过程及生灭过程排队系统,M/M/C和M/M/C/K排队系统，顾客到达间隔服从参数为的负指数分布，顾客在系统中服务时间服从参数为的负指数分布，并满足生灭过程的其他条件。它们都是生灭过程的排队系统，我们都可以从生灭过程的平衡方程来推导出这些排队公式。我们以M/M/1系统为例进