排队模型(掌握mm1,mmc,mm1k)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,排队模型,凯里学院,余英,模型要点,1,、掌握排队模型的基本概念,2,、了解常见的分布函数及生灭过程,3,、掌握典型排队系统模型的结构及应用,排队模型的基本概念,1,、什么是排队模型（排队论）？,排队论是研究拥挤现象的一门学科。,它是在研究各种排队系统概率规律性的基础上，解决有关排队系统的最优化设计（静态）和最优控制（动态）问题。,一、引言,现实生活中的排队系统,序号,到达的顾客,要求服务内容,服务机构,1,不能运转的机器,修理,修理技工,2,修理技工,领取修配零件,发放修配零件的管理员,3,病人,诊断或做手术,医生,(,或包括手术台,),4,电话呼唤,通话,交换台,5,文件搞,打字,打字员,6,提货单,提取存货,仓库管理员,7,驶入港口的货船,装,(,卸,),货,装,(,卸,),货码头,(,泊位,),8,上游河水进入水库,放水，调整水位,水闸管理员,2,、排队论的起源与应用领域,1,）、,20,世纪初,Bell,电话公司为减少用户呼叫， 研究电话线路合理配置问题；,2,）、,1909,年丹麦工程师,A.K.Erlang,受热力学统计平衡概念启发发表论文,概率论与电话交换,，解决上述问题；,3,）、应用于：通讯系统、交通运输、机器维修、库存控制、计算几设计等领域。,二、排队系统的特征及其组成,1,、排队系统的特征即拥挤现象的共性,1,）、有请求服务的人或物,2,）、有为顾客服务的人或物,3,）、具有随机性,4,）、服务的数量超过服务机构的容量,2,、排队系统的三大基本组成部分,1,）、输入过程,(,顾客到达的方式,),a,、顾客的总体（顾客源）的组成可能是有限的，也可能是无限的；,b,、顾客相继到达的时间间隔可以是确定的，也可以是随机的，对于随机的情形，要知道单位时间内的顾客到达数或相继到达的间隔时间的概率分布；,c,、输入过程可以是平稳的（描述相继到达的间隔时间分布和所含参数（如期望值、方差等）都是与时间无关的），否则成为非平稳的，我们研究平稳的。,2,、排队系统的三大基本组成部分,2,）、排队规则,a,、顾客到达时，如所有服务台都被占用，在这种情形下，顾客可以随即离去，也可以排队等待，前者成为损失制，后者成为等待制，我们研究后者；其次还有混合制，它是介于等待制和损失制之间的；,b,、从占有的空间来看，有的系统要规定容量（即允许进入排队系统的顾客数）的最大限，有的没有这种限制,2,、排队系统的三大基本组成部分,3,）、服务过程,a,、可以是没有服务员，单个的，多个的，对于多个的，它们之间可以是平行排列（并列）的，也可以是前后排列（串列）的，也可以是混合的；,b,、服务时间可以是确定的，也可以是随机的，对于后者要知道它的概率分布；,c,、服务时间可以是平稳的，也可以是非平稳的，我们研究前者；,d,、对于等待制，服务规则又可以分为先到先服务（,FCFS,），后到先服务（,LCFS,），随机服务和有优先权的服务。,三、排队模型的分类（符号表示）,我们采用,Kendall,记号,顾客相继到达时间间隔分布,/,服务时间分布,/,服务台数目,/,排队系统允许的最大顾客容量（系统容量）,/,顾客总体数量（顾客源数量）,/,排队规则,说明：如果,Kendall,记号中略去后,3,项，表示,x/y/z/,/FCFS,相继到达时间间隔和服务时间分布的符号如下：,M,负指数分布,D,确定型,Ek,k,阶爱尔朗分布,GI,一般相互独立的时间间隔分布,G,一般服务时间分布,四、排队模型的数量指标,1,、平均队长,(Ls),：,指在系统中的顾客数（包括正被服务的顾客 和排队等待的顾客）的期望值。,2,、平均排队长,(,L,q,),：,指系统中排队等候服务的顾客数,的期望值,。,3,、,平均,逗留时间,(W,s,),：,指一个顾客在系统中的停留时间,期望值。,4,、,平均,等待时间,(,W,q,),：,指一个顾客在系统中排队等待的时间的,期望值。,L,s,=,L,q,+,正被服务的顾客数,W,s,=,W,q,+,服务时间,5,、忙期：,指从顾客到达空闲服务机构起到服务机构再次空闲止 这段时间长度，即服务机构连续繁忙的时间长度。,6,、系统的状态概率,P,n,( t ),：,指系统中的顾客数为,n,的概率。,7,、稳定状态：,limP,n,(t),P,n,四、排队模型的数量指标,8,、,n,系统有,n,个顾客时的平均到达率,9,、,n,系统有,n,个顾客时的平均服务率,10,、,对任何,n,都是常数的平均,到达,率,11,、,对任何,n,都是常数的平均服务率,12,、,服务强度，或称使用因子，平均到达率与服务台与平均服务率的乘积的比值,13,、系统的状态,系统中的顾客数，如果系统中有,n,个顾客，就说系统的状态是,n,，,系统的状态是随着时间在变化的,14,、,p,n,(t,):,时刻,t,系统状态为,n,的概率，稳态时系统状态为,n,的概率用,p,n,表示。,五、,常见的分布函数及生灭过程,1,、,poisson,流,定义：设,N,（,t,）为时间,0,，,t,内到达系统的顾客数，如果满足下面三个条件：,a,、平稳性：在,t,t+,t,内有一个顾客到达的概率为,t+o(,t,);,b,、独立性（无后效性）：任意两个不相交区间内顾客到达情况相互独立；,c,、普遍性：在,t,t+,t,内多于一个顾客到达的概率为,o(,t,);,则称,N,（,t,），,t,0,为,poisson,流。,2,、,poisson,分布,设,N,（,t,）为时间,0,，,t,内到达系统的顾客数，则,N,（,t,），,t,0,为,poisson,流的充要条件是：,五、,常见的分布函数及生灭过程,3,、负指数分布,定理：设,N,（,t,）为时间,0,，,t,内到达系统的顾客数，则,N,（,t,），,t,0,为参数为,的,poisson,流的充要条件是：相继到达时间间隔服从相互独立的参数为,的负指数分布。,4,、,k,阶爱尔朗分布,设,v,1, v,2,.,v,k,是,k,个相互独立的随机变量，服从相同参数,k,的负指数分布，那么,T=,v,1,+v,2,+.+,v,k,服从,k,阶爱尔朗分布。,五、,常见的分布函数及生灭过程,5,、生灭过程,定义：设,N,（,t,），,t,0,为一随机过程，若,N,（,t,）的概率分布具有以下性质：,a,、假设,N,（,t,）,=n,则从时刻,t,起到下一个顾客到达时刻止的时间服从参数为,n,的负指数分布，,n=0,1,2,b,、假设假设,N,（,t,）,=n,则从时刻,t,起到下一个顾客离去时刻止的时间服从参数为,n,的负指数分布，,n=0,1,2,c,、同一时刻时只有一个顾客到达或离去。,则称,N,（,t,），,t,0,为一个生灭过程。,五、,常见的分布函数及生灭过程,根据系统平稳状态时“流入,=,流出”原理，得到如下任一状态下的平衡方程：,0,1,p,1,=,0,p,0,1,0,p,0,+,2,p,2,=,（,1,+,1,）,p,1,2,1,p,1,+,3,p,3,=,（,2,+,2,）,p,2,n-1,n-2,p,n-2,+,n,p,n,=,（,n-1,+,n-1,）,p,n-1,n,n-1,p,n-1,+,n+1,p,n+1,=,（,n,+,n,）,p,n,生灭过程中,C,n,与,p,0,的推导及应用,五、,常见的分布函数及生灭过程,由上述方程可求得,0 p,1,= p,0,0/,1,1 p,2,=,1,p,1,/,2,+(,1,p,1,- p,0,0,)/,2,=p,0,0,1,/(,2,1,),2 p,3,=,2,p,2,/,3,+(,2,p,2,- p,1,1,)/,3,=p,0,2,1,0,/(,3,2,1,),n-1,p,n,=,n-1,p,n-1,/,n,+(,n-1,p,n-1,- p,n-2,n-2,)/,n,=p,0,n-2,n-1,0,/(,n,n-1,1,),n p,3,=,n,p,n,/,n+1,+(,n,p,n,- p,n-1,n-1,)/,n+1,=p,0,n,n-1,0,/(,n+1,n,1,),五、,常见的分布函数及生灭过程,记,则平稳状态的分布为,p,n,=c,n,p,0,。,由此可得,生灭过程排队系统的各项指标，即,6,、经验分布,例,1,某服务机构单服务台，先到先服务，对,41,顾客记录到达时刻,和服务时间,s,（,单位：分钟）如下表，表中第,1,号顾客到达时刻为,0,。全部服务时间为,127,（分钟）。,(1),i,(2),i,(3),s,i,(4),t,i,(5),w,i,(1),i,(2),i,(3),s,i,(4),t,i,(5),w,i,(1),i,(2),i,(3),s,i,(4),t,i,(5),w,i,1,0,5,2,0,5,12,2,7,10,9,36,1,2,0,2,2,7,4,3,6,19,4,3,5,10,38,2,7,0,3,6,1,5,6,7,22,3,4,6,11,45,5,2,0,4,11,9,1,2,8,26,3,10,5,12,47,4,2,3,五、,常见的分布函数及生灭过程,(1),i,(2),i,(3),s,i,(4),t,i,(5),w,i,(1),i,(2),i,(3),s,i,(4),t,i,(5),w,i,(1),i,(2),i,(3),s,i,(4),t,i,(5),w,i,13,49,1,3,5,23,86,6,2,2,33,117,4,4,7,14,52,2,9,3,24,88,5,4,6,34,121,2,6,7,15,61,1,1,0,25,92,1,3,7,35,127,1,2,3,16,62,2,3,0,26,95,3,6,5,36,129,6,1,2,17,65,1,5,0,27,101,2,4,2,37,130,3,3,7,18,70,3,2,0,28,105,2,1,0,38,133,5,2,7,19,72,4,8,1,29,106,1,3,1,39,135,2,4,10,20,80,3,1,0,30,109,2,5,0,40,139,4,3,8,21,81,2,2,2,31,114,1,2,0,41,142,1,9,22,83,3,3,2,32,116,8,1,0,到达间隔分布表,服务时间分布表,平均间隔时间：,=142/40=3.55(,分钟,/,人,),平均到达率：,41/142=0.28(,人,/,分钟,),平均服务率：,41/127=0.32(,人,/,分钟,),平均服务时间：,127/41=3.12(,分钟,/,人,),到达间隔,(,分钟,),次数,1,2,3,4,5,6,7,8,9,10,以上,6,10,8,6,3,2,2,1,1,1,合计,40,服务时间,(,分钟,),次数,1,2,3,4,5,6,7,8,9,以上,10,10,7,5,4,2,1,1,1,合计,41,六、典型排队系统模型的结构及应用,M/M/C,等待制排队模型研究要点：,a,、系统意义,b,、状态转移速度图与状态转移速度矩阵,c,、状态概率方程,d,、系统的基本数量指标,Passion,分布,设,N(,t,),表示在时间,0, t),内到达顾客数；,令,P,n,(,t,1,t,2,),表示在时间区间,t,1,t,2,),（,t,2,t,1,）,内有,n,（,0,）,个顾客到达的概率，即,P,n,(,t,1,t,2,)=P N(,t,2,) N(,t,1,)=,n,（,t,2,t,1,，,n,0,）,Passion,分布的三条件：,(1),无后效性：不相重叠的时间区间内顾客到达数相互独立,P,n,(,t,+,t,)=,P,n,(,t,) ( 1-,t,+o(,t,),+ P,n,-1,(,t,),t,+,o(,t,),情况,0,t,),t,t,+,t,),0,t,+,t,),个数,概率,个数,概率,个数,概率,(A),(B),(C),n,n,-1,n,-2,n-,3,0,P,n,(,t,),P,n,-1,(,t,),P,n,-2,(,t,),P,n,-3,(,t,),P,0,(,t,),0,1,2,3,n,1-,t,+o(,t,),t,o(,t,),n,n,n,n,n,P,n,(,t,) ( 1-,t,+o(,t,),P,n,-1,(,t,),t,o(,t,),在上述条件下，研究顾客到达数,n,的概率分布,P,n,(,t,+,t,)= P,n,(,t,)(1-,t,)+P,n,-1,(,t,),t,+,o(,t,),P,n,(,t,+,t,)-P,n,(,t,)/,t,=-,P,n,(,t,)+,P,n,-1,(,t,)+o(,t,)/,t,令,t,0,d,P,n,(,t,)/d,t,= -,P,n,(,t,) +,P,n,-1,(,t,),P,n,(0)=0,（,n,1）,d P,0,(,t,)/d,t,= -,P,0,(,t,),P,0,(0)=1,（,n,=0）,P,0,(,t,)=,e,-,t,P,n,(,t,)=(,t,),n,e,-,t,/,n,t,0,n,=0,，,1,，,2,负指数分布,f,T,（,t,）,=,e,-,t,，,t,0,0,，,t0,一、,M/M/1,模型,1,、假设,（,1,）顾客到达的间隔时间满足参数为,的负指数分布,（,2,）服务时间满足参数为,的负指数分布（,）,（,3,）服务机构是单服务台,（,4,）顾客源是无限的，顾客相互独立,（,5,）单队排列，且对队长没有限制,第三节 单服务台负指数分布排队系统的分析,2,、,P,n,的计算,O,表示发生（,1,个） ，,表示没有发生,P,n,(,t,+,t,)= P,n,(,t,)(1-,t,)(1-,t,),+ P,n,+1,(,t,)(1-,t,),t,+ P,n,-1,(,t,),t,(1-,t,),+,P,n,(,t,),t,t,情况,在时刻,t,顾客数,在区间（,t,t,+,t,）,在时刻,t,+,t,顾客数,到达,离去,(A),(B),(C),(D),n,n,+1,n,-1,n,O,O,O,O,n,n,n,n,整理得：,P,n,(,t,+,t,)=P,n,(,t,)(1-,t,-,t,)+P,n,+1,(,t,),t,+P,n,-1,(,t,),t,+o(,t,),P,n,(,t,+,t,)-P,n,(,t,)/,t,=,P,n,-1,(,t,)+,P,n,+1,(,t,)-(,+,),P,n,(,t,) (1),t,0,dP,n,(,t,)/d,t,=,P,n,-1,(,t,)+,P,n,+1,(,t,)(,+,),P,n,(,t,),考虑,P,0,(,t,),的情况：,P,0,(,t,+,t,)=P,0,(,t,)(1-,t,)+P,1,(,t,)(1-,t,),t,t,0, dP,0,(,t,)/d,t,=-,P,0,(,t,)+,P,1,(,t,) (2),由,dP,n,(,t,)/d,t,=0,得到,-,P,0,+,P,1,=0 (3),P,n,-1,+,P,n,+1,-(,+,)P,n,=0 (4),由式,(3),得,通过求解可得,单位时间内到达的平均顾客数,单位时间内服务的平均顾客数,服务强度,参数意义：,3,、,M/M/1,参数计算,（,1,）系统中平均顾客数（,L,s,）,记,（,2,）队列中等待的平均顾客数（,L,q,）,（,3,）顾客逗留时间（,W,s,）,（,4,）队列中顾客等待时间（,W,q,）,它们的相互关系如下：,其中,称为,little,公式，它是排队论中的一个重要公式。,例,3,100,个工作小时内每小时来就诊的病人数,n,出现次数如下,100,个完成手术的病例所用时间,v,(,小时,),出现的次数如下,到达的病人数,n,出现次数,t,n,0,1,2,3,4,5,6,10,28,29,16,10,6,1,合计,100,为病人完成手术时间,v,(,小时,),出现次数,t,v,0.0-0.2,0.2-0.4,0.4-0.6,0.6-0.8,0.8-1.0,1.0-1.2,1.2,以上,38,25,17,9,6,5,0,合计,100,解：,假定系统最大容量为,N,，单服务台情形排队等待的顾客最多为,N-1,，,下面只考虑稳态情形：,二、,M/M/1/N/,模型,解得：,根据上式我们可以推导出系统的各项指标：,有效到达率,e,=,(1-P,N,),可以验证：,1-P,0,=,e,/,(4),顾客等待时间,(3),顾客逗留时间,(1),队长,(2),队列长,例,4,单人理发馆有六个椅子接待客人。当,6,个椅子都坐满时，后来的顾客不进店就离开。顾客平均到达率为,3,人,/,小时，理发需时平均,15,分钟。则：,N=7,为系统中最大的顾客数，,=3,人,/,小时，,=4,人,/,小时,（,1,）求某顾客一到达就能理发的概率。,（,2,）求需要等待的顾客数的期望值。,（,3,）求有效到达率。,（,4,）求一顾客在理发馆内逗留的时间。,（,5,）在可能到达的顾客中有百分之几不等待就离开。,（人,/,小时）,一、,M/M/c,第四节 多服务台指数分布排队系统的分析,规定各服务台工作相互独立且平均分配服务率相同，即,1,=,2,=,c,=,整个服务机构的平均服务率为,c,(,n,c,),n,(,n,c,),用递推法解上述差分方程，可求得状态概率。,根据上式我们可以推导出系统的各项指标：,例,6,某售票所有三个窗口，顾客到达服从,Passion,过程，平均到达率每分钟,=0,.9(,人,),服务,(,售票,),时间服从负指数分布,平均服务率每分钟,=0.4(,人,).,=0.9,窗口,(1),=0.4,窗口,(2),=0.4,窗口,(3),=0.4,代入公式得,(1),整个售票所空闲的概率,（,2,）平均队长,（,3,）平均等待时间和逗留时间,（,4,）顾客到达后必须等待（即系统中顾客数已有,3,人）的概率,M/M/c,型系统和,c,个,M/M/1,系统的比较,上例中，排队方式不变，但顾客到达后在每个窗口前各排一队，且进入队列后坚持不换，这就形成,3,个队列，如下图二每个队列平均到达率为,=0,.9/3=0.3,（,每分钟），这样原来的系统就变成,3,个,M/M/1,型的子系统。,窗口,(1),=0.4,窗口,(2),=0.4,窗口,(3),=0.4,=0.9,=0.3,=0.3,=0.3,现按,M/M/1,型解决这个问题，并与上表比较：,从表中各指标的对比可以看出单队比三队有显著的优越性,模型,指标,(1)M/M/3型,(2)M/M/1型,服务台空闲的概率,顾客必须等待的概率,平均队列,平均队长,平均逗留时间,平均等待时间,0.0748,P(,n,3,)=0.57,1.70,3.95,4.39(,分钟,),1.89(,分钟,),0.25(,每个子系统,),0.75,2.25(,每个子系统,),9.00(,整个系统,),10(,分钟,),7.5(,分钟,),