理学排队论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019/2/2,运筹学校级重点建设课程电子教案,#,4.1,标准的,M/M/c,模型,即：,M/M/c/FCFS,标准的,M/M/C,模型与标准的,M/M/1,模型的各特征规定相同，另外，各服务台工作是相互独立且平均服务率相同，即,1,=,2,=,3,=,c,=,，,于是整个服务机构的平均服务率为：,c,(nc,时,),n(nc,时,),令,，只有当 时，才不会形成无限队列。,从上图的队列图，分析系统中的状态转移关系，状态转移图见下图。,1,2,c,队列,C,个服务台,由上图知，当,n,c,时，顾客被服务离去的速率为,n,当,n,c,时，为,c,，故可得差分方程：,(1,n,c,),(n,c),0,1,2,n=c-1,n=c,c,n=c+1,c,(c-1),.,nc,n-1,n,c,n+1,c,n,c,.,c,这里：，,1,利用递推法解该差分方程可求得状态概率为：,当,(n,=3)=0.57,P(n=1)=0.75,平均队长,L,s,3.95,9.00,（整个系统）,平均队列长,L,q,1.70,2.25,（每个子系统）,平均逗留时间,W,s,4.39min,10min,平均等待时间,W,q,1.89min,7.5min,4.3,系统容量有限制的情形（,M/M/C/N/,）,设系统的容量最大限制为,N(C,）,当系统中顾客数,n,已达到,N,（即队列中的顾客数已达,N-C,）时，再来的顾客将被拒绝，其他条件与标准的,M/M/C,型相同。,此时的状态概率为：,其中：,运行指标为：,4.4,顾客源为有限的情况（,M/M/C/m,）,设顾客源为有限,m,且,mc,，顾客到达率是按每个顾客考虑的。,在机器维修模型中，有,m,台机器，,c,个修理工，机器故障率就是每个机器单位运转时间出故障的期望次数，系统中顾客数,n,就是出故障的机器台数。,当,nc,时，无排队，有,c-n,个修理工空间；当,cnm,时，有,(n-c),台机器停机等待修理，系统处于繁忙状态。,假定：,(1),每个服务台速率均为,的负指数分布，（,2,）故障修复时间与正在生产的机器是否发生故障是相互独立的，则：,5,一般服务时间的（,M/G/1,）模型,本节我们研究服务时间任意分布的情形，我们知道，对任何情形下面的关系都正确：,L,s,=L,q,+,L,se,(L,se,-,服务机构中顾客数的期望值,),W,s,=W,q,+ET,（,ET-,服务平均时间）,L,s,=W,s,，,L,q,=W,q,当然，对于有容量限制和有限源情形,要换成,e.,这就是著名的,P-K,公式，只要知道,ET,VarT,无论,T,服从什么分布，各项运行指标都可算出来。,5,.,1 Pollaczek-Khintchine(P-K),公式,对,M/G/1,模型,只要服务时间的,ET,和,VarT,存在，其他条件与,M/M/1,相同，且,1,=,ET,则有：,5.2,定长服务时间,M/D/1,模型,该情况的服务时间是确定的常数，如一条装配线上完成一件工作的时间是常数。则,:T=1/VarT=0,L,s,=,+,2,/2(1-),L,q,=L,s,-=,2,/2(1-),W,s,=L/=(2-)/2(1-),W,q,=L,q,/=/2(1-),例,5,某售票口，顾客平均,2.5,分钟到达一个，窗口对顾客的平均服务时间是,2,分钟,顾客在售票口前至少要占用,1,分钟，且服务时间服从：,f(y)=e,1-y,y1,0 y=0,即,x,是服从均值为,1,的负指数分布。,Ey=E1+x=2,Vary=Var1+x=Varx=1,根据,P-K,公式：,人,5.3,爱尔朗服务时间,M/E,k,/1,模型,如图，若顾客必须经过,k,个服务站，在每个服务站的服务时间,T,i,相互独立，并服从相同的负指数分布（参数为,k,），那么 服从,k,阶爱尔朗分布。,.,.,k,1,2,k-1,ku,ku,ku,ku,服务机构,则,M/E,k,/1,模型的运行指标为：,6,排队系统优化,排队系统优化问题分为两类：系统设计和系统控制优化。前者称为静态问题，即研究如何使设备达到最大效益或机构最为经济；后者称为动态问题，研究如何运营可使某个目标达到最优。本节我们只讨论静态问题。,从静态考虑，排队系统主要涉及两项费用：等待损失费用和服务费用。,6.1 M/M/1,模型中的最优服务率,1,、标准的,M/M/1,模型,设：,C,s,为,=1,时服务机构的单位时间费用，,C,w,为每个顾客单位时间等待费用。则单位时间成本,z,为,:,2,、系统容量为,N,的情形,该系统中顾客到达后在系统中超过,N,个时，将被拒绝，,拒绝,概率为,P,N,，则,1-P,N,为接受概率，所以,(1-,P,N,),为单位时间内进入系统的顾客平均数，也是单位时间内实际服务的平均数。,(1-,P,N,)=(1-P,0,).,设每服务一个顾客收入,G,元，于是单位时间收入期望值为,(1-,P,N,)G,元，纯利润为：,解上式的最优解,*,6.2 M/M/C,模型中最优服务台数,C,仅讨论标准的,M/M/C,模型，且在稳态下，单位时间全部费用的期望值为：,(,包括服务成本与等待费用,),C,s,每个服务台单位服务时间成本；,C,w,每个顾客在系统中停留单位时间成本；,L,系统中顾客的平均数,L,s,或队列平均数,L,q,，,是,C,的函数。,这里,C,是,Z,的函数，且,C,只能取整数解，故不能用微分法求,C*,，而只能用边际分析法,(Marginal Analysis),：,因为,z(c*),是最小值，则有：,将,z,期望费用公式代入：,合并化简得：,由于,C,s,/,C,w,已知，依次求,C=1,，,2,，,3,，,的,L,值，即可找出符合上式的,C*,。,例,6,某检验中心，为各用户检验产品，用户每天到达按泊松流,=48,个,/,天，每个用户每天停工损失,6,元，服务时间服从负指数分布,=25,个,/,天，设一个检验台每天服务成本,4,元，其他条件为标准,M/M/C,模型，问设几个服务台费用最少？,解：,C,s,=4,元，,C,w,=6,元，,=48,，,=25,下表是服务台,C=1,2,3,时各,L,s,值：,计算,L(C,*,)-L(C,*,+1),及,L(C,*,-1)-L(C,*,),c=1 -,c=2 18.930 ,c=3 0.612 18.930,c=4 0.116 0.612,