《运筹学》课程教学讲义（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(Z<△)=1-e=1-[-uM+o(-△)=u△-o(-△)=u△+o(M),M→0 p(A|B2)=p{在时刻t+M时,排队系统内有n个顾客|在时刻t时,排队系统内有n个顾客} p{在时间[t,+△门]内,既无顾客到达,也无顾客接受完服务后离开} =p(A|B1)∪(A|B3)=1-p(A|B1)∪(A|B3)=1-p(A|B1)-p(A|B3) 1-[λMt+o(△)]-[u△+o(△n=1-(+)△t-2o(△) 1-(2+山)△t+o(△),△t→>0. 注意,此处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），得