第9章排队论 排队论是我们每个人都很熟悉的现象。因为人或物或是信息为了得到某种服 务必须排队。有一类排队是有形的,例如在售票处等待买票的排队,加油站前汽 车等待加油的排队等:还有一类排队是无形的,例如电话交换机接到的电话呼叫 信号的排队,等待计算机中心处理机处理的信息的排队等。为了叙述的方便,排 队者无论是人、物、或信息,以后统称为“顾客”。服务者无论是人,或事物, 例如一台电子计算机也可以是排队系统中的服务者,我们以后统称为“服务员”。 排队现象是我们不希望出现的现象,因为人的排队意味着至少是浪费时间 物的排队则说明了物资的积压。但是排队现象却无法完全消失,这是一种随即现 象。由于顾客到达间隔时间的随机性和为顾客服务时间的随机性是排队现象产生 的原因。如果上述的两个时间是固定的,我们就可以通过妥善安排来完全消除排 队现象 排队论是研究排队系统在不同的条件下(最主要的是顾客到达的随机规律和 服务时间的随机规律)产生的排队现象的随机规律性。也就是要建立反映这种随 机性的数学模型。研究的最终目的是为了运用这些规律,对实际的排队系统的设 计与运行做出最优的决策 排队论中的数学模型是根据概率和随机过程的理论建立起来的,我们先来讨 论泊松过程和生灭过程,然后,再此基础上研究排队系统的结构及其主要的数学 模型,最后研究排队系统的优化问题。 9.1泊松过程和生灭过程 911泊松过程 如果用N(1)表示在[0,n时间内顾客到达的总数,则对于每个给定的时刻 N()都是一个随机变量。随即变量族{NO)∈[O,T}称作是一个随机过程 若对1<t2<…tn<tn+,有 P(N(tn+)=i+|N(t)=i,N(t)=12…,N(t)=1n P(N(n+)=in+N(m)=im) 1 则称随即过程{N()∈,T)为马尔柯夫过程。公式(91)所标示的性质称 为“无后效性”。它的实际意义是说:如果用tn表示现在时刻,tn+表示未来时 刻,t1n2…,tn1表示过去的一系列时刻,则顾客到来的过程在tn以前所处的状态
第 9 章 排队论 排队论是我们每个人都很熟悉的现象。因为人或物或是信息为了得到某种服 务必须排队。有一类排队是有形的，例如在售票处等待买票的排队，加油站前汽 车等待加油的排队等；还有一类排队是无形的，例如电话交换机接到的电话呼叫 信号的排队，等待计算机中心处理机处理的信息的排队等。为了叙述的方便，排 队者无论是人、物、或信息，以后统称为“顾客”。服务者无论是人，或事物， 例如一台电子计算机也可以是排队系统中的服务者，我们以后统称为“服务员”。 排队现象是我们不希望出现的现象，因为人的排队意味着至少是浪费时间； 物的排队则说明了物资的积压。但是排队现象却无法完全消失，这是一种随即现 象。由于顾客到达间隔时间的随机性和为顾客服务时间的随机性是排队现象产生 的原因。如果上述的两个时间是固定的，我们就可以通过妥善安排来完全消除排 队现象。 排队论是研究排队系统在不同的条件下（最主要的是顾客到达的随机规律和 服务时间的随机规律）产生的排队现象的随机规律性。也就是要建立反映这种随 机性的数学模型。研究的最终目的是为了运用这些规律，对实际的排队系统的设 计与运行做出最优的决策。 排队论中的数学模型是根据概率和随机过程的理论建立起来的，我们先来讨 论泊松过程和生灭过程，然后,再此基础上研究排队系统的结构及其主要的数学 模型，最后研究排队系统的优化问题。 9.1 泊松过程和生灭过程 9.1.1 泊松过程 如果用 表示在[0 时间内顾客到达的总数，则对于每个给定的时刻 ， 都是一个随机变量。随即变量族 N t( ) ,t] t N t( ) { ( N t) t ∈[0,T]}称作是一个随机过程。 若对 t t 1 2 < <"t n <t n+1，有 1 111 2 2 ( ( ) ( ) , ( ) , , ( ) P N t i n n + + = = N t i N t = i " N t n = in 1 1 ( ( ) ( ) ) = = P N t i n n + + N t n = in (9-1) 则称随即过程{ ( 为马尔柯夫过程。公式（9-1）所标示的性质称 为“无后效性”。它的实际意义是说：如果用t 表示现在时刻，t 表示未来时 刻，t t 表示过去的一系列时刻，则顾客到来的过程在t 以前所处的状态 N t) t ∈[0,T)} n n+1 1 2 1 , , , " t n− n
(即顾客到达数)对预言过程在tn以后的状态不起直接作用。 若随即过程{NO∈,T}就有“独立增量性”,即对任一组 t1<12…,tn(n≥3),随即变量N(12)-N(1),N(t3)-N(t2),…,N(tn)-N(n)相互独 立,且对任意t∈[0,7]有 P(N(1)=k) k=0,1,2, (9-2) 其中参数入>0,则称这个过程为泊松过程。 独立增量性说明在互不相交的时间区间[,t2)[2,13),……,[tn-,tn)内顾客到 达情况是相互独立的。由于∑Mc=1 =0k! 所以N(t)的期望值为 E(N(1)=∑k (n-e=AE ()-I-x 入 E(N(1) (9-4) 因此,参数λ就是单位时间间隔内到达顾客的平均数,同时,我们还可以求 得随机变量N()的方差为 D(N(=At 例91某天上午,从10点30分到11点47分,每隔20秒钟统计一次来到 某汽车站的乘客数,共得230个记录数据,整理后得到如下的统计结果: 表9 乘客数目 0 2 4 频数 100 试用一个泊松过程来描述此车站乘客的到达过程,并具体写出它的概率分 布 解:要写出其概率分布,只需确定公式(9-2)中的参数λ即可。根据λ的意 义,只要先求出每20秒钟的平均数 入 (0×100+1×81+2×34+3×9+4×6)=087 230 因此可知每分钟平均到达的顾客数为
（即顾客到达数）对预言过程在t n 以后的状态不起直接作用。 ,T] ( k e − ( ) ! k t k λ i ∞ = ∑ = DNt ( ( ×34 若随即过程 { ( 就有“独立增量性”，即对任一组 ，随即变量 相互独 立，且对任意t 有 N t) t ∈[0 } T], 1 2, , ( 3) t t < " t n n ≥ ∈[0 2 1 3 2 ) ( ), ( ) ( ), , ( ) ( N N t t − − N t N t " N t n − N t n−1) , ( ) ( ( ) ) ! t t PNt k k λ λ = = k = 0,1,2,"" (9-2) 其中参数λ > 0 ，则称这个过程为泊松过程。 独立增量性说明在互不相交的时间区间[ 内顾客到 达情况是相互独立的。由于 1 2 2 3 1 , ),[ , ), ,[ , ) t t t t "" t n− t n 0 1 t k e λ ∞ − = ∑ = 所以 N t( ) 的期望值为 1 0 1 ( ) ( ) ( ( )) ! ( 1) k k t t k k t t E N t k e e t k k λ λ λ λ λ − ∞ ∞ − − = = = = ∑ ∑ ⋅ − ! 0 ( )i t t t e i λ λ λ − = =λt (9-3) E N( (t)) t λ (9-4) 因此，参数λ就是单位时间间隔内到达顾客的平均数，同时，我们还可以求 得随机变量 N t( ) 的方差为 )) =λt (9-5) 例 9.1 某天上午，从 10 点 30 分到 11 点 47 分，每隔 20 秒钟统计一次来到 某汽车站的乘客数，共得 230 个记录数据，整理后得到如下的统计结果： 表 9-1 乘客数目 0 1 2 3 4 频 数 100 81 34 9 6 试用一个泊松过程来描述此车站乘客的到达过程，并具体写出它的概率分 布。 解：要写出其概率分布，只需确定公式（9-2）中的参数λ即可。根据λ的意 义，只要先求出每 20 秒钟的平均数 1 (0 100 1 81 2 3 9 4 6) 0.87 230 λ = × + × + + × + × = 因此可知每分钟平均到达的顾客数为
入=3×0.87=261(人/分钟) 故所求的乘客到达过程所满足的概率分布为 P(N(1)=k) (261) 261t k! 一般地,有如下结论: 定理1若随机过程{No)∈0,T)满足下列三个条件 (1)独立增量性:对任一组t1<t2 <tn、n≥3),随机变量 N(t2)-N(t1),N(t3)-N(12) N(tn)-N(tn-)相互独立 (2)平稳性:对于[S,s+n][0,刀],总有 P[N(S+1)-N(s)=k]=P[N(1)-N(0)=k] 其中P(N(0)=0)=1,∑P(N()=k)=1 (3)普遍性:令y(1)=∑P(N(t)=k),有 P(o 则{N(D)p∈O,T]}是一个泊松过程。 独立增量性说明在[0,刀]中的任意区间[Ss,s+l]内来到k个顾客这一事件与 区间[0,s]内来到顾客的情况相互独立,即在[O,s内顾客来到的情况所作的任何 假定下,计算出来的在[Ss,s+η]内来到k个顾客的条件概率均相等。同时可知, 具有独立增量性的过程必然具有无后效性 平稳性说明在[s,s+n内来到的数值与区间长度t有关,而与时间起点s无 关。也就是说,过程的统计规律不随时间的推移而改变,在同样长度的时间间隔 内来到k个顾客的概率是一个常数 普遍性表明,在同一瞬间来到两个或两个以上顾客实际上是不可能的。即在 充分小的时间间隔中,最多来到一个顾客 在排队论里,常把泊松过程称为泊松流或最简单流,参数λ称为最简单流的 强度。顺便说一下,泊松过程还具有可知性。即如果{N()}和{N2()是两个泊 松过程,到达强度分别为入和x2且两个过程相互独立,则{N()}+{N2(2)仍 为一泊松过程,其到达强度为x1+A2,推广此结论,则更多个独立的泊松过程合 并后仍为一泊松过程,其到达强度为各过程到达强度之和 泊松过程在排队论中起着重要作用。因为泊松流或近似于泊松流的实际情况 经常会遇到,并且泊松流的数学处理很简单。 912负指数分布和爱尔朗分布 若用rn表示第n位顾客所需的服务时间,则{rn}是一族连续性随机变量。如
λ = ×3 0.87 = 2.61（人/分钟） 故所求的乘客到达过程所满足的概率分布为 2.61 (2.61 ) ( ( ) ) ! k t t PNt k e k − = = 一般地，有如下结论： 定理 1 若随机过程{ ( N t) t ∈[0,T)}满足下列三个条件： (1) 独立增量性：对任一组 t t ，随机变 量 相互独立； 1 2 < <""<t n(n ≥3 1 ) ( ) − N t n− ) ] k 2 1 3 2 ( ) ( ), ( ) ( ), , ( N N t t − − N t N t "" N t n (2)平稳性：对于[ ,s s +t] ⊂[0,T]，总有 P N[ ()( s+t − N s) = = k] P[N(t) ( − N 0) = k 其中 ； 0 ( (0) 0) 1, ( ( ) ) 1 k P N PNt k ∞ = = = ∑ = = (3)普遍性：令ϕ ，有 2 ( ) ( ( ) ) k t P N t ∞ = = = ∑ ϕ t 0 ( ) lim 0 t= t = 则{ ( N t) t ∈[0,T]}是一个泊松过程。 独立增量性说明在[0 中的任意区间[ , 内来到 k 个顾客这一事件与 区间[0 内来到顾客的情况相互独立，即在[0 内顾客来到的情况所作的任何 假定下，计算出来的在[ , 内来到 个顾客的条件概率均相等。同时可知， 具有独立增量性的过程必然具有无后效性。 ,T] s s + s s +t] ,s] ,s] t] k 平稳性说明在[ , 内来到的数值与区间长度 有关，而与时间起点 无 关。也就是说，过程的统计规律不随时间的推移而改变，在同样长度的时间间隔 内来到 个顾客的概率是一个常数。 s s +t] t s k 普遍性表明，在同一瞬间来到两个或两个以上顾客实际上是不可能的。即在 充分小的时间间隔中，最多来到一个顾客。 在排队论里，常把泊松过程称为泊松流或最简单流，参数λ称为最简单流的 强度。顺便说一下，泊松过程还具有可知性。即如果{ ( 和{ ( 是两个泊 松过程，到达强度分别为λ 和 ，且两个过程相互独立，则{ ( +{ ( 仍 为一泊松过程，其到达强度为λ ，推广此结论，则更多个独立的泊松过程合 并后仍为一泊松过程，其到达强度为各过程到达强度之和。 1 N t)} 2 N t) 1 t)} } } 2 1 λ2 1+ N 2 N t) λ 泊松过程在排队论中起着重要作用。因为泊松流或近似于泊松流的实际情况 经常会遇到，并且泊松流的数学处理很简单。 9.1.2 负指数分布和爱尔朗分布 若用τ n 表示第n 位顾客所需的服务时间，则{τ n }是一族连续性随机变量。如
果{rn}中各个随机变量相互独立,且服从相同的负指数分布 t>0 P(Tn≤1) (9-6) t<0 (其中参数μ>0)其概率密度函数为 P(=Jue-"u t>0 (9-7) t<0 则服务时间rn的期望值为: +∞ |+∞ H dt (9-8) 则有 于是,就是每位顾客所需要的平均服务时间,而表示单位时间内能被服 务完的顾客平均数。在排队论中通常用“平均”来表示概率论中的数学期望 同时可求得rn的方差为 D(T) (9-10) 设{N(t)}是描述顾客到达情况的随机过程,以Ln表示第n个顾客到达的时 刻,则T=tn-ln-为第n位顾客与他的前一位顾客(第n-1位顾客)到达时间 的时间间隔。显然{n}也是一族随机变量。关于到达间隔时间{}与顾客到达过 程{N(t)}之间的关系,可证得如下的结论: 定理2顾客到达过程{N(1)}是一个参数为入的泊松过程的充分必要条件为 相应的顾客到达间隔{n}是一族相互独立的随机变量,且每个随机变量都服从下 面的负指数分布: t>0 P(Tn≤1) (9-11) t<0 此定理说明,“顾客流是最简单流”与“顾客到达间隔相互独立且服从相同 的负指数分布”是等价的两种描述方法。由于上面的负指数分布的数学期望 E()=x,所以在最简单流中,顾客到达时间间隔的平均值为°
果{τ n }中各个随机变量相互独立，且服从相同的负指数分布： N t ( ) E Tn = 1 ( ) 0 t n e P t µ τ − − ≤ = (9-6) 0 0 t t ≥ < （其中参数µ > 0）其概率密度函数为 ( ) 0 t e p t µ µ − ⋅ = (9-7) 0 0 t t ≥ < 则服务时间τn 的期望值为： 0 ( ) ( ) t E n tp t dt te dt µ τ µ +∞ +∞ − −∞ = = ∫ ∫ 0 0 t t 1 te e dt µ µ µ +∞ − +∞ − =− + ∫ = (9-8) 则有 1 ( ) E n τ µ = (9-9) 于是，1 µ 就是每位顾客所需要的平均服务时间，而µ 表示单位时间内能被服 务完的顾客平均数。在排队论中通常用“平均”来表示概率论中的数学期望。 同时可求得τn 的方差为 2 1 ( ) D n τ µ = (9-10) 设{ ( 是描述顾客到达情况的随机过程，以 表示第 个顾客到达的时 刻，则 T t 为第n 位顾客与他的前一位顾客（第 位顾客）到达时间 的时间间隔。显然{ 也是一族随机变量。关于到达间隔时间{ 与顾客到达过 程{ ( 之间的关系，可证得如下的结论： N t)} = )} nt n 1 T n n n 1 t − − Tn n− } }n 定理 2 顾客到达过程{ ( 是一个参数为λ的泊松过程的充分必要条件为： 相应的顾客到达间隔{ 是一族相互独立的随机变量，且每个随机变量都服从下 面的负指数分布： N t)} } Tn 1 ( ) 0 t n e P T t −µ − ≤ = (9-11) 0 0 t t ≥ < 此定理说明，“顾客流是最简单流”与“顾客到达间隔相互独立且服从相同 的负指数分布”是等价的两种描述方法。由于上面的负指数分布的数学期望 1 λ ，所以在最简单流中，顾客到达时间间隔的平均值为 1 λ
例9.2在某座大桥桥口,观察到26辆到达桥口要过桥的汽车,其到达时刻 记录如下(开始观察时刻为0,单位为秒) 015172324253139555862636 6880828589979910311l121122123133 试用一个泊松过程描述这个到达过程,并写出具体的概率模型 解:因为泊松流中,顾客到达的时间间隔的平均值为,所以可着手求得入, 再定出概率模型。汽车到达的时间间隔依次为: 152611681634123 101110 因此,到达间隔时间的平均值为 15+2+…+10133 25=25=523(秒) 就是平均每隔532秒钟到达一辆汽车。因为顾客到达间隔平均值为、,而λ 就是泊松流的概率模型中参数,由1=532可得入=x25=0.18,即每秒钟平 均到达的汽车数约为0.188 于是可用如下的泊松分布来描述到达过程{N(): P(N(=k (0188) 0.l88t k=0.1.2 也可用如下的负指数分布来描述其到达间隔{T}: P(Tn≤1) t≥0 关于负指数分布,需要强调一个它所具有的“无记忆性”。先看一个问题, 如果顾客到达间隔时间服从负指数分布,平均间隔时间10秒,又假设在某一时 刻(任一时刻)来考察这个到达过程,发现最后一位顾客已到达了7秒,那么下 一位顾客平均还需多长时间才会到达呢?回答是出人意料之外的:还需要10秒。 看来已经过去了的7秒被遗忘了,故称“无记忆性”。下面来证明这一特性: 设到达间隔T服从负指数分布如公式(9-11)所示,而s为任一时刻,则到 达间隔T大于等于s的概率为: P(T≥s)=1-P(T≤s)= 又因为T≥s与T≥s+1(t>0)同时发生的概率等于T<s+t的概率,即 P(T≥.728+0=PT≤s+)=∫d=c 当给定条件T>s时,讨论T≥s+t的条件概率,发现
例 9.2 在某座大桥桥口，观察到 26 辆到达桥口要过桥的汽车，其到达时刻 记录如下（开始观察时刻为 0，单位为秒）： 0 15 17 23 24 25 31 39 55 58 62 63 65 68 80 82 85 89 97 99 103 111 121 122 123 133 试用一个泊松过程描述这个到达过程，并写出具体的概率模型。 解：因为泊松流中，顾客到达的时间间隔的平均值为 1 λ ，所以可着手求得λ， 再定出概率模型。汽车到达的时间间隔依次为： 15 2 6 1 1 6 8 16 3 4 1 2 3 12 2 3 4 8 2 4 8 10 1 1 10 因此，到达间隔时间的平均值为 15 2 10 133 5.23 25 25 + +⋅⋅⋅+ = = （秒） 就是平均每隔 5.32 秒钟到达一辆汽车。因为顾客到达间隔平均值为 1 λ ，而 就是泊松流的概率模型中参数，由 λ 1 5.32 λ = 可得 1 5.32 λ = ，即每秒钟平 均到达的汽车数约为 0.188。 = 0.188 于是可用如下的泊松分布来描述到达过程{ ( N t)}： 0.188 (0.188 ) ( ( ) ) ! k t t PNt k e k − = = k = 0,1,2,⋅⋅⋅ 也可用如下的负指数分布来描述其到达间隔{Tn}： 0.188 1 ( ) 0 t n e P T t − − ≤ = 0 0 t t ≥ < 关于负指数分布，需要强调一个它所具有的“无记忆性”。先看一个问题， 如果顾客到达间隔时间服从负指数分布，平均间隔时间 10 秒，又假设在某一时 刻（任一时刻）来考察这个到达过程，发现最后一位顾客已到达了 7 秒，那么下 一位顾客平均还需多长时间才会到达呢？回答是出人意料之外的：还需要 10 秒。 看来已经过去了的 7 秒被遗忘了，故称“无记忆性”。下面来证明这一特性： 设到达间隔T 服从负指数分布如公式（9-11）所示，而 为任一时刻，则到 达间隔 大于等于 的概率为： s T s ( ) 1 ( ) t s s P T s P T s e dt e λ λ λ +∞ − − ≥ = − ≤ = = ∫ 又因为T s 与T s )同时发生的概率等于 t 的概率，即 t ≥ ≥ +t(t > 0 T s ≤ + ( ) ( , ) ( ) t s s t P T s T s t P T s t e dt e λ λ λ +∞ − − + + ≥ ≥ + = ≤ + = ∫ = 当给定条件T ≥ s 时，讨论T s ≥ +t 的条件概率，发现