《运筹学》课程教学讲义（Operations Research）第十一章 排队论

运筹学讲义 §11排队论 本章来介绍排队论( queuing theory). 1909年,丹麦哥本哈根电话公司的A.K. Erlang对电话拥挤现象进行了研究,并发表了《概率 与电话通话理论》( Probability and Theory of Telephone),开创了排队论的研究 排队论,亦称随机服务系统理论或等待线理论,是研究因随机因素的影响而产生的排队现象,以 便对随机服务系统进行最优设计和控制的理论 关于排队,队列可能是有形的,如在火车站售票处买票,也可能是无形的,如电话订票;顾客可 能是人,如在银行等待取款的顾客,也可能是物,如等待进港的船只:服务台可能是人,如售票员 也可能是物,如机场跑道:顾客数可能有限,如等待买票的人,也可能无限,如泄洪问题中的上游来 随机服务系统又称为排队系统. 排队系统的描述:顾客到达服务台是随机的顾客到达服务台时,若服务台空闲,则立刻接受服 务:否则,顾客应等待至服务台空闲时,再接受服务.顾客接受服务后即离开服务台. 排队系统的三要素: (1)输入过程:指顾客到达的规律,如顾客数(有限或无限),顾客到达的方式(批量或单个), 相继到达的顾客之间的时间间隔的分布 (2)排队规则:包括服务台是否允许排队,顾客的排队意愿,服务顺序(先到先服务,后到先 服务,随机服务,优先权服务)等 (3)服务机制:服务台的数目,多服务台服务时的连结方式(串连或并连),服务时间的分布 平稳状态:正常的,稳定的运行状态.如当储蓄所早上开门时,顾客很少,是为过渡期:此后, 业务活动渐渐进入平稳状态 显然,当排队系统处于平稳状态时,任意时刻时的顾客的数目的变化率(导数)等于0 排队论的研究对象是平稳状态时的排队系统 1953年,D.G. Kendall引入了排队系统的符号模型: 顾客到达的时间间隔的分布/服务时间的分布/服务台的数目/排队系统允许的最大顾客容量 如排队模型M/M/1/∞,其中M表示顾客到达的时间间隔相互独立,且都服从指数分布,M 表示服务台对顾客的服务时间相互独立,且都服从指数分布,1为服务台的数目,∞表示排队系统允 许的最大顾客数无限制 排队系统的主要数量指标 (1)平均排队队长:排队等待的平均顾客数Lq (2)平均队长:平均顾客数L 显然,L=Lq+正在接受服务的顾客数如对排队模型M/M/1/∞,有L=Lq+1 (3)平均排队时间:顾客排队等待接受服务的平均时间W

运 筹 学 讲 义 1 §11 排队论 本章来介绍排队论（queuing theory）. 1909 年，丹麦哥本哈根电话公司的 A. K. Erlang 对电话拥挤现象进行了研究，并发表了《概率 与电话通话理论》（Probability and Theory of Telephone），开创了排队论的研究. 排队论，亦称随机服务系统理论或等待线理论，是研究因随机因素的影响而产生的排队现象，以 便对随机服务系统进行最优设计和控制的理论. 关于排队，队列可能是有形的，如在火车站售票处买票，也可能是无形的，如电话订票；顾客可 能是人，如在银行等待取款的顾客，也可能是物，如等待进港的船只；服务台可能是人，如售票员， 也可能是物，如机场跑道；顾客数可能有限，如等待买票的人，也可能无限，如泄洪问题中的上游来 水. 随机服务系统又称为排队系统. 排队系统的描述：顾客到达服务台是随机的.顾客到达服务台时，若服务台空闲，则立刻接受服 务；否则，顾客应等待至服务台空闲时，再接受服务.顾客接受服务后即离开服务台. 排队系统的三要素： （1）输入过程：指顾客到达的规律，如顾客数（有限或无限），顾客到达的方式（批量或单个）， 相继到达的顾客之间的时间间隔的分布. （2）排队规则：包括服务台是否允许排队，顾客的排队意愿，服务顺序（先到先服务，后到先 服务，随机服务，优先权服务）等. （3）服务机制：服务台的数目，多服务台服务时的连结方式（串连或并连），服务时间的分布. 平稳状态：正常的，稳定的运行状态.如当储蓄所早上开门时，顾客很少，是为过渡期；此后， 业务活动渐渐进入平稳状态. 显然，当排队系统处于平稳状态时，任意时刻时的顾客的数目的变化率（导数）等于 0. 排队论的研究对象是平稳状态时的排队系统. 1953 年，D. G. Kendall 引入了排队系统的符号模型： 顾客到达的时间间隔的分布/服务时间的分布/服务台的数目/排队系统允许的最大顾客容量 如排队模型 M / M /1/  ，其中 M 表示顾客到达的时间间隔相互独立，且都服从指数分布， M 表示服务台对顾客的服务时间相互独立，且都服从指数分布，1 为服务台的数目，  表示排队系统允 许的最大顾客数无限制. 排队系统的主要数量指标： （1）平均排队队长：排队等待的平均顾客数 Lq ； （2）平均队长：平均顾客数 L ； 显然， L = Lq + 正在接受服务的顾客数.如对排队模型 M / M /1/  ，有 L = Lq +1. （3）平均排队时间：顾客排队等待接受服务的平均时间 Wq ；

运筹学讲义 (4)平均停留时间:顾客在排队系统内的平均时间 显然,平均停留时间=W+顾客接受服务的时间 (5)平均停留时间:不同顾客的停留时间的平均值W 几个符号 平均到达率λ:单位时间内到达的顾客数 平均服务率:单位时间内接受服务的顾客数 服务强度ρ=一:平均到达率与平均服务率之比 本章主要来研究排队模型M/M/1/∞,其中M表示顾客到达的时间间隔相互独立,且都服从 指数分布,M表示服务台对顾客的服务时间相互独立,且都服从指数分布,1为服务台的数目,∞表 示排队系统允许的最大顾客数无限制 设顾客到达的时间间隔X相互独立,且都服从参数为λ的指数分布,即 1-e",t>0 p(X<1) 则由概率论的知识不难证明,在时间[tt+△]内到达的顾客数Y服从 t<0 参数为A△M的普哇松分布,即p(Y=k)=(2△Nny-y,k=0.2, k 由EX=→ 1,EF=A4→EY 知,美位时肉到达的平均顾数 顾客到达的平均时间间隔 设服务台对顾客的服务时间Z服从参数为4的指数分布,即p(Z<D t≤0 Ez=→pB…单位时间内接受服务的平均顾客数二平均服务时何 令pn(1)=p{在时刻t时,排队系统内有n个顾客},n=0,2…, 则P2(+△)=P(在时刻t+M时,排队系统内有n个顾客},∑p()=1 令A={在时刻t+M时,排队系统内有n个顾客}

运 筹 学 讲 义 2 （4）平均停留时间：顾客在排队系统内的平均时间. 显然，平均停留时间 =Wq + 顾客接受服务的时间. （5）平均停留时间：不同顾客的停留时间的平均值 W . 几个符号： 平均到达率  ：单位时间内到达的顾客数； 平均服务率  ：单位时间内接受服务的顾客数； 服务强度    = ：平均到达率与平均服务率之比. 本章主要来研究排队模型 M / M /1/  ，其中 M 表示顾客到达的时间间隔相互独立，且都服从 指数分布， M 表示服务台对顾客的服务时间相互独立，且都服从指数分布，1 为服务台的数目，  表 示排队系统允许的最大顾客数无限制. 设顾客到达的时间间隔 X 相互独立，且都服从参数为  的 指 数 分 布 ， 即     −   = − 0, 0 1 , 0 ( ) t e t p X t t ，则由概率论的知识不难证明，在时间 [t,t + t] 内到达的顾客数 Y 服从 参数为  t 的普哇松分布，即 , 0,1,2, ! ( ) ( ) =  = = −  e k k t p Y k t k   . 由     =  =  = =   t EY EY t EX EX , 1 1 知 ， 单位时间内到达的平均顾客数 = =  顾客到达的平均时间间隔 1 . 设服务台对顾客的服务时间 Z 服从参数为  的指数分布，即     −   = − 0, 0 1 , 0 ( ) t e t p Z t t ，则 EZ EZ 1 1 =   =  . 单位时间内接受服务的平均顾客数 = =  平均服务时间 1 . 令 pn (t) = p{ 在时刻 t 时，排队系统内有 n 个顾客 } ，n = 0,1,2, ， 则 pn (t + t) = p{ 在时刻 t + t 时，排队系统内有 n 个顾客 } ， ( ) 1 0  =  n= n p t . 令 A = { 在时刻 t + t 时，排队系统内有 n 个顾客 }

运筹学讲义 B1={在时刻t时,排队系统内有n-1个顾客}, B2={在时刻t时,排队系统内有n个顾客} B3={在时刻t时,排队系统内有n+1个顾客}, 则由Pn(1)的定义知,P(B1)=Pn=1(1),p(B2)=Pn(D),P(B3)=Pn+1(t) 由模型假设知,顾客到达的时间间隔服从参数为A的指数分布,服务时间服从参数为的指数分 布,于是 p(A|B1)=p{在时刻t+M时,排队系统内有n个顾客|在时刻t时,排队系统内有n-1个顾客} =p{在时间[t,t+△]内,有1个顾客到达,无顾客接受完服务后离开} p(Y=1=(A△M)=Me=2△1-△+o-2△ =M-A2(△r)2+AAt·o(-△r)=A△t+o(△r),M→0 川:低阶无穷小量lmO(△D)=0) (-x) p(A|B3)=p{在时刻t+△时,排队系统内有n个顾客|在时刻t时,排队系统内有n+1个顾客} p{在时间[t,t+M门]内,无顾客到达,有1个顾客接受完服务后离开} =p(Z0. 注意,此处B1,B2,B3虽不构成完备事件组,但不难证明,p(A|Bk)(k≥2)都是M的无穷小量

运 筹 学 讲 义 3 B1 = { 在时刻 t 时，排队系统内有 n −1 个顾客 } ， B2 = { 在时刻 t 时，排队系统内有 n 个顾客 } ， B3 = { 在时刻 t 时，排队系统内有 n +1 个顾客 } ， 则由 p (t) n 的定义知， ( ) ( ) 1 1 p B p t = n− ， ( ) ( ) 2 p B p t = n ， ( ) ( ) 3 1 p B p t = n+ . 由模型假设知，顾客到达的时间间隔服从参数为  的指数分布，服务时间服从参数为  的指数分 布，于是 ( | ) { p A B1 = p 在时刻 t + t 时，排队系统内有 n 个顾客|在时刻 t 时，排队系统内有 n −1 个顾客 } = p{ 在时间 [t,t + t] 内，有 1 个顾客到达，无顾客接受完服务后离开 } ( ) ( ) ( ), 0; [1 ( )] 1! ( ) ( 1) 2 2 1 =  −  +   −  =  +   → =   =  −  + −   = = = −  −  t t t o t t o t t e t e t t o t t p Y t t             （注：    = −  = − = = 0 0 ! ( ) , ! n n x n n x n x e n x e ；低阶无穷小量 0 ( ) lim 0 =    → t o t t ） ( | ) { p A B3 = p 在时刻 t + t 时，排队系统内有 n 个顾客|在时刻 t 时，排队系统内有 n +1 个顾客 } = p{ 在时间 [t,t + t] 内，无顾客到达，有 1 个顾客接受完服务后离开 } = (   ) =1− =1−[1−  + (−  )] =  − (−  ) =  + ( ), → 0; −  p Z t e t o t t o t t o t t t       ( | ) { p A B2 = p 在时刻 t + t 时，排队系统内有 n 个顾客|在时刻 t 时，排队系统内有 n 个顾客 } = p{ 在时间 [t,t + t] 内，既无顾客到达，也无顾客接受完服务后离开 } 1 ( ) ( ), 0. 1 [ ( )] [ ( )] 1 ( ) 2 ( ) (( | ) ( | )) 1 (( | ) ( | )) 1 ( | ) ( | ) 1 3 1 3 1 3 = − +  +   → = −  +  −  +  = − +  −  =  = −  = − − t o t t t o t t o t t o t p A B A B p A B A B p A B p A B       互斥 注意，此处 1 2 3 B ,B ,B 虽不构成完备事件组，但不难证明， p(A| B )(k  2) k 都是 t 的无穷小量

运筹学讲义 (M→0),故仍采用p(A|B2)=1-p(4B1)-p(A|B3)来求解p(A|B2)! 由全概率公式有 Pn (t+Ar)=P(A)=P(B,P(AI B,)+P(B,(A1 B2)+P(BP(AlB,) Pn=1(D)[△t+o(△t)+pn()[1-(+p)△t+0(△n)+Pn+1(1)[4△t+o(△) Mt·Pn1()+[1-(4+)△小Pn(1)+HMt·Pn1()+Pn1(D)+Pn(t)+Pn+1()]o(△) =2Mt·Pn1(D+-(+)△小]Pn(D)+M.Pn+1(1)+o(△)(1) 于是, Pn(t+△)-pn()Mtpn-1(D)+[1-(+p)A]Pn(1)+H△t·Pn1(t)+0(△)-Pn() Mr·Pn1()-(+山)M·Pn()+M·Pa+1()+o(Ar) =Apn()-(2+)Pn()+uPn()+4 dp,(t t+△)-Pn(1) lim[apn-(0)-(1+p,(0)+upn+(0)+ O(Ar) =lmPn1(1)-(2+p)P()+Hp1()+mO(△n) M→0 =Apn1(1)-(4+4)pn()+HPn+1(t)+0 =Apn1(1)-(2+)pn()+Pn+1(1),n≥1(2) 当n=0时,A={在时刻t+M时,排队系统内有0个顾客} B1={在时刻t时,排队系统内有-1个顾客}=d B2={在时刻t时,排队系统内有0个顾客}, B3={在时刻t时,排队系统内有1个顾客}, 则p(B1)=p(①)=0,P(B2)=P0(1),P(B3)=P1():p(AB1)=p()=0 p(A|B3)=p{在时刻t+M时,排队系统内有0个顾客|在时刻t时,排队系统内有1个顾客} =p{在时间[t,t+△]内,无顾客到达,有1个顾客接受完服务后离开}

运 筹 学 讲 义 4 （ t →0 ），故仍采用 ( | ) 1 ( | ) ( | ) p A B2 = − p A B1 − p A B3 来求解 ( | ) p A B2 ！ 由全概率公式有 ( ) [1 ( ) ] ( ) ( ) ( ) (1) ( ) [1 ( ) ] ( ) ( ) [ ( ) ( ) ( )] ( ) ( ) [ ( )] ( ) [1 ( ) ( )] ( ) [ ( )] ( ) ( ) ( ) ( | ) ( ) ( | ) ( ) ( | ) 1 1 1 1 1 1 1 1 1 1 2 2 3 3 t p t t p t t p t o t t p t t p t t p t p t p t p t o t p t t o t p t t o t p t t o t p t t p A p B p A B p B p A B p B p A B n n n n n n n n n n n n n =   + − +   +   +  =   + − +   +   + + +   =   +  +  − +  +  +   +  +  = = + + − + − + − + − +             于是， t o t p t p t p t t t p t t p t t p t o t t t p t t p t t p t o t p t t p t t p t n n n n n n n n n n n n   = − + + +    − +   +   +  =    + − +   +   +  − =  +  − − + − + − + ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) [1 ( ) ] ( ) ( ) ( ) ( ) 1 1 1 1 1 1             ( ) ( ) ( ) ( ), 1 (2) ( ) ( ) ( ) ( ) 0 ( ) lim [ ( ) ( ) ( ) ( )] lim ] ( ) lim [ ( ) ( ) ( ) ( ) ( ) ( ) lim ( ) 1 1 1 1 0 1 1 0 1 1 0 0 = − + +  = − + + +   = − + + +   = − + + +  +  − = − + − +  → − +  → − +  →  → p t p t p t n p t p t p t t o t p t p t p t t o t p t p t p t t p t t p t dt dp t n n n n n n t n n n t n n n t n n t n                 当 n = 0 时， A = { 在时刻 t + t 时，排队系统内有 0 个顾客 } ， B1 = { 在时刻 t 时，排队系统内有 −1 个顾客 } =  ， B2 = { 在时刻 t 时，排队系统内有 0 个顾客 } ， B3 = { 在时刻 t 时，排队系统内有 1 个顾客 } ， 则 p(B1 ) = p() = 0， ( ) ( ) 2 0 p B = p t ， ( ) ( ) 3 1 p B = p t ； p(A| B1 ) = p() = 0 ； ( | ) { p A B3 = p 在时刻 t + t 时，排队系统内有 0 个顾客|在时刻 t 时，排队系统内有 1 个顾客 } = p{ 在时间 [t,t + t] 内，无顾客到达，有 1 个顾客接受完服务后离开 }

运筹学讲义 =p(Z<△)=1-e=1-[1-4M+o(-△)=uM-0(-△)=△+o(△),M→0; p(A|B2)=p{在时刻t+M时,排队系统内有0个顾客|在时刻t时,排队系统内有0个顾客} =p{在时间[t,t+△门]内,无顾客到达(不可能有顾客接受完服务后离开!)} =p(Y=0) (2△n)-N 1-△t+o(-A△)=1-Mt+o(△n),△t→0 由全概率公式,有 P0(t+△)=p(A)=p(B1)p(AB1)+p(B2)P(A|B2)+p(B3)p(A|B3) =0·AM+P0(1)[1-AM+o(△)+p(1)[A△+o(△) =P0(1)(1-A△)+P1(1)M+[p0()+P1()]o(△r) =P0(D)·(1-A)+P1(1)·At+o(△) 于是 p0(t+△)-p0(1)P0(D)·(1-2△1)+Hp1()·M+o(△)-P0(t) p0()△t+HP1(D)△t+o(△) n po(+up,O O(△) dpo()= lim Po(+A)-Po(0) =lm(-p0()+P()+(4 =lm[-p0()+P1()+m4) -元P0()+4P1()+0=-P0(1)+P(D)(3) dp () 0.n≥1 在顾客流平稳状态时,有 dt p0( 即 0 dt AλPn1()-(2+p)P2()+HPn1()=0,n≥1 (4) Ap0(1)+H(1)=0 令p=二<1,代入(4),得

运 筹 学 讲 义 5 = (   ) =1− =1−[1−  + (−  )] =  − (−  ) =  + ( ), → 0 −  p Z t e t o t t o t t o t t t       ； ( | ) { p A B2 = p 在时刻 t + t 时，排队系统内有 0 个顾客|在时刻 t 时，排队系统内有 0 个顾客 } = p{ 在时间 [t,t + t] 内，无顾客到达（不可能有顾客接受完服务后离开！） } 1 ( ) 1 ( ), 0 0! ( ) ( 0) 0 = = −  + −  = −  +   →  = = = −  −  e e t o t t o t t t p Y t t       . 由全概率公式，有 ( ) (1 ) ( ) ( ). ( ) (1 ) ( ) [ ( ) ( )] ( ) 0 ( ) [1 ( )] ( ) [ ( )] ( ) ( ) ( ) ( | ) ( ) ( | ) ( ) ( | ) 0 1 0 1 0 1 0 1 0 1 1 2 2 3 3 p t t p t t o t p t t p t t p t p t o t t p t t o t p t t o t p t t p A p B p A B p B p A B p B p A B =  −  +   +  =  −  +   + +   =   +  −  +  +   +  +  = = + +        于是， . ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (1 ) ( ) ( ) ( ) 0 1 0 1 0 0 0 1 0 t o t p t p t t p t t p t t o t t p t t p t t o t p t t p t t p t   = − + +  −  +  +  =   −  +   +  − =  +  −       ( ) ( ) 0 ( ) ( ). (3) ( ) lim [ ( ) ( )] lim ] ( ) lim [ ( ) ( ) ( ) ( ) lim ( ) 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 p t p t p t p t t o t p t p t t o t p t p t t p t t p t dt dp t t t t t         = − + + = − +   = − + +   = − + +  +  − =  →  →  →  → 在顾客流平稳状态时，有      = =  0 ( ) 0, 1 ( ) 0 dt dp t n dt dp t n ，即 (4) ( ) ( ) 0 ( ) ( ) ( ) ( ) 0, 1 0 1 1 1    − + = − − + + + =  p t p t pn t pn t pn t n       令 =  1    ，代入（4），得

运筹学讲义 ∫PPn-(0)-(p+1)p,()+Pn1()=0n21(S) -pP()+P()=0(6) (6)→P1(D)=PP0(1) (5)→Ppn()-P2)=pn(0)-pn()=B1()-P2( B(=n()=O,n≥1 令an=Pn(D)-Pn=1(1),则 于是,{an}m为等比数列,且首项为a1=P1(1)-p(D)=PP0(1)-P0(1)=(p-1)P0(1),通 项为an=a1pm=(p-1)p0(1)pm,n≥1.即pn(1)-pn1(1)=(p-1)p(1)p”,n≥1 于是 pn()-pn=1(1)=(p-1)p0()p pn1(t)-pn2(t)=(p-1)p0(1)p"2, P2(D)-P1(1)=(p-1)P0(D)f P1(1)-p0(1)=(p-1)p0() 将各式两边分别加和得 p()-p0()=(p-1)p0()1+p+…+p"2+p)=(p-1)p0() NP0()(-1) Pn(D)=p"P0(,n≥1 于是,1=∑P()=∑P”P0(D)=p(0)∑p=B)、 →P0(1)=1-p pn(D)=p"(1-p),n≥1.故pn(D)=p"(1-p),n≥0 这里,Pn()为排队系统中在平稳状态时的任意时刻t时有n个人的概率,与t无关,∴在平稳状

运 筹 学 讲 义 6    − + = − − + + + =  ( ) ( ) 0 (6) ( ) ( 1) ( ) ( ) 0, 1 (5) 0 1 1 1 p t p t pn t pn t pn t n    (6) ( ) ( ) 1 0  p t =  p t ； , 1 ( ) ( ) ( ) ( ) (5) [ ( ) ( )] ( ) ( ) 1 1 1 1 =  − −  − = −  − + − + n p t p t p t p t p t p t p t p t n n n n  n n n n  . 令 ( ) ( ) 1 a p t p t n = n − n− ，则 , 1 1 =  + n a a n n  . 于是，  =1 { } an n 为等比数列，且首项为 ( ) ( ) ( ) ( ) ( 1) ( ) 1 1 0 0 0 0 a = p t − p t =  p t − p t =  − p t ，通 项为 ( 1) ( ) , 1 1 0 1 = 1 = −  − − a a p t n n n n    .即 ( ) ( ) ( 1) ( ) , 1 1 − 1 = − 0  − p t p − t p t n n n n   . 于是， 1 1 0 ( ) ( ) ( 1) ( ) − − − = − n n n p t p t  p t  ， 2 1 2 0 ( ) ( ) ( 1) ( ) − − − − = − n n n p t p t  p t  ， ……， p2 (t) − p1 (t) = ( −1) p0 (t) ， ( ) ( ) ( 1) ( ) 1 0 0 p t − p t =  − p t . 将各式两边分别加和得 ( ) ( ), 1 ( )( 1) 1 1 ( ) ( ) ( 1) ( )(1 ) ( 1) ( ) 0 0 0 2 1 0 0  =  = − − − − = − + + + + = −  − − p t p t n p t p t p t p t p t n n n n n n n           于是，      = − − =  =  =  =   =  =  = ( ) 1 1 1 1 ( ) ( ) ( ) ( ) 0 0 0 0 0 0 0 p t p t p t p t p t n n n n n n .  p (t) = (1− ), n  1 n n   .故 p (t) = (1− ), n  0 n n   . 这里， p (t) n 为排队系统中在平稳状态时的任意时刻 t 时有 n 个人的概率，与 t 无关，  在平稳状

运筹学讲义 态时,有pn=p"(1-p),n≥0 平稳状态时排队系统的若干数量指标: (1)至少有k个顾客的概率: Pn=∑p"(1-p)=(1-p (2)平均队长: 数学期望 L=∑叩n=∑叩n=∑m"(1-p)=(-p∑m=(1-p∑np o(-p2(")=p-pX∑)=m-p)(12ny p(1-p) 1-p-p·(-1) =p(1-p) (3)平均排队队长: np, Pn Pn-Po Po L-1+po=L-1+(1-p)=L-p= P PL P (4)平均停留时间: 由普哇松分布知,在平均停留时间W内到达的平均顾客数为λ·W.∴L=W.于是,平均停留 时间为/。L1-9=-4一= 11 (1--) (5)平均排队时间: 由普哇松分布知,在平均排队时间W内到达的平均顾客数为,Wq…Lq=Wq·于是,平均 排队时间为∥L。1-D1 L -(-) 关系:14=PL,W=pW.(服务质量完全取决于服务强度) 7

运 筹 学 讲 义 7 态时，有 p = (1− ), n  0 n n   . 平稳状态时排队系统的若干数量指标： （1）至少有 k 个顾客的概率： k k n k n n k n n k pn         = −  =  − = −  = −   =  =  = 1 (1 ) (1 ) (1 ) . （2）平均队长： . (1 ) 1 1 (1 ) (1 ) 1 ( 1) (1 ) ) 1 (1 ) ( ) (1 )( ) (1 ) ( (1 ) (1 ) (1 ) 2 2 1 1 1 1 0 1 1 1                            − = − = −  − − −  − = −   − = −  = −  = −  = = = − = − = −         =  =  = −  =  =  =  = n n n n n n n n n n n n n n L np np n n n 数学期望 （3）平均排队队长： . 1 1 1 1 (1 ) ( 1) ( ) (1 ) 2 0 0 0 1 1 1 0 0 L p L L L L n p np p np p p L p n n n n n n n n n q n         = − − = − = − + = − + − = − = =  − =  − =  −  − = − −  =  =  =  =  = 数学期望 （4）平均停留时间： 由普哇松分布知，在平均停留时间 W 内到达的平均顾客数为  W . L = W .于是，平均停留 时间为            − = − = − = = 1 (1 ) L 1 W . （5）平均排队时间： 由普哇松分布知，在平均排队时间 Wq 内到达的平均顾客数为 Wq   .Lq = Wq .于是，平均 排队时间为 ( ) 1 1 1 2                  − = − =  =  − =  − = = L L W q q . 关系： Lq =  L ，Wq = W .（服务质量完全取决于服务强度）

运筹学讲义 (6)服务台空闲(排队系统中在顾客到达前没有顾客:顾客到达后不需排队等待即可接受服务) 的概率:Po=1-p; 服务台繁忙(排队系统中在顾客到达前已有顾客:顾客到达后需排队等待再接受服务)的概率 ∑pn=1-po=1-(1-p)=p 例1在火车站某一售票口,顾客到达的时间间隔服从指数分布,且平均时间间隔为20分钟;售 票口对顾客的服务时间服从指数分布,且平均服务时间为15分钟.试求此排队系统在1个小时内的下 列数量指标:(1)顾客到达后,不需排队的概率;(2)顾客多于5人的概率;(3)顾客的平均人数 (4)顾客的平均排队人数:(5)顾客的平均停留时间:(6)顾客的平均排队时间. 解:显然,这是一个M/M//∞排队模型,且A6=3,∥6=4,p==0.75 (1)p{顾客到达后,不需等待}=p{排队系统内有0个顾客}=P0=1-P=1-0.75=025 (2)p{顾客多于5人}=p3=(0.75)3=02373046875: (3)顾客的平均人数L=0=3 1-p1-0.75 (4)顾客的平均等待人数Lq=PL=0.75×3=225 (5)顾客的平均停留时间W=2=3=1 (6)顾客的平均等待时间W=pW=0.75×1=0.75. 根据排队系统的这些数量指标,管理者就可采取措施改进服务,减少顾客的排队等待时间,以提 高服务质量 Ex 1.在北京大学图书馆的某一借书窗口,学生到达的时间间隔服从指数分布,且平均时间间隔为 2分钟;窗口对学生的服务时间服从指数分布,且平均服务时间为0.75分钟.试求此排队系统在1 个小时内的下列数量指标:(1)学生到达后,不需等待的概率;(2)学生的平均人数;(3)学生的平 均等待人数:(4)学生的平均停留时间:(5)学生的平均等待时间. 2.某车间只有一台打磨机,单位时间内送达打磨机的工件的个数服从普哇松分布,且每小时送达 5人:工件的打磨时间服从指数分布,且平均打磨时间为6分钟试求此排队系统在1个小时内的下 列数量指标:(1)工件送达后,需等待的概率:(2)等待打磨的工件的个数超过2个的概率:(3)等 待打磨的工件的平均个数:(4)若此打磨机损坏,需新购一打磨机.问:新购打磨机的平均打磨时间

运 筹 学 讲 义 8 （6）服务台空闲（排队系统中在顾客到达前没有顾客；顾客到达后不需排队等待即可接受服务） 的概率： p0 = 1−  ； 服务台繁忙（排队系统中在顾客到达前已有顾客；顾客到达后需排队等待再接受服务）的概率：  = − = − −  =   = 1 1 (1 ) 0 1 p p n n . 例 1 在火车站某一售票口，顾客到达的时间间隔服从指数分布，且平均时间间隔为 20 分钟；售 票口对顾客的服务时间服从指数分布，且平均服务时间为 15 分钟.试求此排队系统在 1 个小时内的下 列数量指标：（1）顾客到达后，不需排队的概率；（2）顾客多于 5 人的概率；（3）顾客的平均人数； （4）顾客的平均排队人数；（5）顾客的平均停留时间；（6）顾客的平均排队时间. 解：显然，这是一个 M / M /1/  排队模型，且 3 20 60  = = ， 4 15 60  = = ， = = 0.75    . （1） p{ 顾客到达后，不需等待 } = p{ 排队系统内有 0 个顾客 } = p0 =1−  =1− 0.75 = 0.25 ； （2） p{ 顾客多于 5 人 } (0.75) 0.2373046875 5 5 =  = = ； （3）顾客的平均人数 3 1 0.75 0.75 1 = − = − =   L ； （4）顾客的平均等待人数 Lq =  L = 0.753 = 2.25 ； （5）顾客的平均停留时间 1 3 3 = = =  L W ； （6）顾客的平均等待时间 Wq = W = 0.751 = 0.75 .▍ 根据排队系统的这些数量指标，管理者就可采取措施改进服务，减少顾客的排队等待时间，以提 高服务质量. Ex.： 1.在北京大学图书馆的某一借书窗口，学生到达的时间间隔服从指数分布，且平均时间间隔为 1.2 分钟；窗口对学生的服务时间服从指数分布，且平均服务时间为 0.75 分钟.试求此排队系统在 1 个小时内的下列数量指标：（1）学生到达后，不需等待的概率；（2）学生的平均人数；（3）学生的平 均等待人数；（4）学生的平均停留时间；（5）学生的平均等待时间. 2.某车间只有一台打磨机，单位时间内送达打磨机的工件的个数服从普哇松分布，且每小时送达 5 人；工件的打磨时间服从指数分布，且平均打磨时间为 6 分钟.试求此排队系统在 1 个小时内的下 列数量指标：（1）工件送达后，需等待的概率；（2）等待打磨的工件的个数超过 2 个的概率；（3）等 待打磨的工件的平均个数；（4）若此打磨机损坏，需新购一打磨机.问：新购打磨机的平均打磨时间

运筹学讲义 至多为多少,才能使工件的平均等待时间不超过4分钟?(0.5,0.125,1,3)

运 筹 学 讲 义 9 至多为多少，才能使工件的平均等待时间不超过 4 分钟？（0.5，0.125，1，3）