第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}就有“独立增量性”,即对任一组 t10,则称这个过程为泊松过程。 独立增量性说明在互不相交的时间区间[,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 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) t0)其概率密度函数为 P(=Jue-"u t>0 (9-7) t0 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)同时发生的概率等于Ts时,讨论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 ≥ 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 的条件概率，发现
P(T≥+12小)P(T≥sT2s+)eeN=P(T20) 由结果知,此条件概率与s无关。这说明无论在泊松过程的什么时刻,即无 论取哪一时刻为起点,考察至下一位顾客到达所经过的时间,其概率(即 P(T≥s+17≥))与此时刻之前的最后一位顾客是什么时候到达的无关。它和 顾客相继到达的间隔时间都服从相同参数的负指数分布。 还可以指出的是,能满足无记忆性P(T≥s+1{T≥s)=P(T≥1)的分布,也 只能是负指数分布 下面讨论爱尔朗( Erlang)分布。 爱尔朗分布的密度函数是 ·() P()={(k-1) t>0 0,k称为阶数(k=0,12,)。 当k=1时,则爱尔朗分布也就是负指数分布。若随机变量r服从k阶爱尔朗 分布,则的期望值和方差分别为 E(r)=K, D()=k 可以证明,如果552,…5是k个相互独立具有相同的负指数分布(参数为 μ)的随机变量,则随机变量r=5+52+…+5服从k阶爱尔朗分布 在排队论中,常把顾客到达间隔时间及接受服务时间与爱尔朗分布联系起 来。如果顾客要连续接受串联的k个服务台服务,各服务台的服务时间相互独立, 且服从相同的负指数分布(参数为),那么顾客被这k个服务台服务完总共所 需的时间就服从爱尔朗分布。这里应说明的是在顾客接受连续的服务时,只有当 k个服务台都完成了对某个顾客的服务之后,下一个顾客才能进入这个串联服务 系统 913生灭过程 生灭过程也是一种马尔柯夫过程。在排队论中很多排队过程和这个过程相 仿。我们特别关心生灭过程在统计平衡时反映出来的稳态概率,并直接把这种稳 态概率应用于建立各种排队模型。 1.生灭过程的定义 一堆细菌,随时间推移,有的分裂为两个,有的死亡,经过一段时间之后, 细菌变为多少?这种细菌的分裂与死亡的过程就是典型的生灭过程的例子。设每 个细菌在△t时间内分裂成两个细菌的概率为A△r+0△n);而在△t时间内死亡
( ) ( , ) ( ) ( ) s t t s P T s T s t e P T s t T s e P T t P T s e λ λ λ − + − − ≥ ≥ + ≥ + ≥ = = = = ≥ ≥ ( ) 由结果知，此条件概率与 无关。这说明无论在泊松过程的什么时刻，即无 论取哪一时刻为起点，考察至下一位顾客到达所经过的时间，其概率（即 s P T( ≥ s +t T ≥ s)）与此时刻之前的最后一位顾客是什么时候到达的无关。它和 顾客相继到达的间隔时间都服从相同参数的负指数分布。 还可以指出的是，能满足无记忆性 P T( ≥ s +t T ≥ s) = P T( ≥t) 的分布，也 只能是负指数分布。 下面讨论爱尔朗（Erlang）分布。 爱尔朗分布的密度函数是 1 ( ) ( ) ( 1)! 0 k t t e p t k µ µ µ − − ⋅ = − t (9-12) 0 t 0 ≥ 0，k 称为阶数( 0 k = ,1,2,⋅⋅⋅) 。 当k 时，则爱尔朗分布也就是负指数分布。若随机变量τ 服从 阶爱尔朗 分布，则 =1 k τ 的期望值和方差分别为 2 ( ) , ( ) k E D τ τ µ µ = = k t (9-13) 可以证明，如果ξ ξ 是 个相互独立具有相同的负指数分布（参数为 ）的随机变量，则随机变量 服从 阶爱尔朗分布。 1 2 , , , k ⋅⋅⋅ ξ k µ τ ξ1 2 k = +ξ +⋅⋅⋅+ξ k 在排队论中，常把顾客到达间隔时间及接受服务时间与爱尔朗分布联系起 来。如果顾客要连续接受串联的 个服务台服务，各服务台的服务时间相互独立， 且服从相同的负指数分布（参数为 ），那么顾客被这 个服务台服务完总共所 需的时间就服从爱尔朗分布。这里应说明的是在顾客接受连续的服务时，只有当 个服务台都完成了对某个顾客的服务之后，下一个顾客才能进入这个串联服务 系统。 k µ k k 9.1.3 生灭过程 生灭过程也是一种马尔柯夫过程。在排队论中很多排队过程和这个过程相 仿。我们特别关心生灭过程在统计平衡时反映出来的稳态概率，并直接把这种稳 态概率应用于建立各种排队模型。 1. 生灭过程的定义 一堆细菌，随时间推移，有的分裂为两个，有的死亡，经过一段时间之后， 细菌变为多少？这种细菌的分裂与死亡的过程就是典型的生灭过程的例子。设每 个细菌在+t 时间内分裂成两个细菌的概率为λ+t +0(+ )；而在+t 时间内死亡
的概率为1△+0△n),各个细菌在任一时间内分裂或死亡都是相互独立的。若 将细菌的分裂或死亡都看成是随机事件,那么在△t时间内发生两个时间的概率 等于下面三者之一:(A△t+0(△)2,(△t+0(△n),(A△r+0A)(p△r+0(△r) 所以在△t时间内发生两个或两个以上事件的概率为0△)。又设在时刻t有i个 细菌,则在时刻t+△有i+1个细菌的概率为入△r+0(△n),在时刻t+△t内有 i-1个细菌的概率为△t+0(△)。用(1)表示这堆细菌在时刻t的个数,并考 虑在[0,T)时间内细菌数的变化情况。因为对每个固定的t,ξ()都是随机变量, 故{()p∈[07)为一个随机过程,又因为它具有无后效性,故也是一个马尔柯 夫过程,把上述细菌分裂和死亡的过程称为生灭过程。 定义:设()p∈[0r)为一个随机过程,随机变量()的取值集合为 I=0,1,2,…,m}(或可列集Ⅰ={0,1,2…}),称此集合为状态集,设在时刻t时 (1)=j,那么在时刻t+△时,(t+△)=j+1的概率为入△r+0△),其中 入>0为与t无关的常数:在时刻t+△r时,(+△n)为/中其它元素的概率为 0(△)。满足上述随机过程()∈[0,m)称为生灭过程。 从上面的定义来看,如果把状态的变化理解为排队系统顾客的到达和离去, 则在时间增量△t内,只会有一个到达,或有一个离去,或既无到达也无离去(此 种情况的概率为1-入,△t-p1△t-0△n)),除此以外的其他到达、离去情况认为 是不可能发生的。并且,在△t内到达一个顾客的概率和△t的长短有关,而与 起始时刻t无关;到达一个的概率还与t时刻的顾客到达数j有关(因入与j有 关),而和t时刻以前的状态无关。同理,可进行△t时间内离开一个顾客的概率 情况分析 2.生灭过程的稳态概率 进一步考察生灭过程中时间T=+∞的情况。对生灭过程我们更关心的是极 imP(O)=八)。可以证明下面的定理。 定理3令 A1A2"'Ai 并设生灭过程()20的状态集为=0,2,…,m或=012…},那么, 当下列条件 丌;0。当状态集为有限集/={01,2,m时
的概率为µ ，各个细菌在任一时间内分裂或死亡都是相互独立的。若 将细菌的分裂或死亡都看成是随机事件，那么在+ 时间内发生两个时间的概率 等于下面三者之一：( 。 所以在+ 时间内发生两个或两个以上事件的概率为0( 。又设在时刻t 有i 个 细菌，则在时刻t t 有 个细菌的概率为λ ，在时刻 内有 个细菌的概率为µ 。用 表示这堆细菌在时刻t 的个数，并考 虑在 时间内细菌数的变化情况。因为对每个固定的t ， 都是随机变量， 故 +t +0(+ ) λ t ++ i ) t t t 2 2 )) ,( + + + + t t + + 0( )) ,(µ+ + t t 0( λ λ +t +0( ))⋅(µ+t +0(+ )) +t) i +1 0( ) i t +t t ++t +t t +0(+ ) ξ(t) ξ(t) i−1 [0,T { ( 为一个随机过程，又因为它具有无后效性，故也是一个马尔柯 夫过程，把上述细菌分裂和死亡的过程称为生灭过程。 ξ t t ) ∈[0,T)} ξ t t ) ∈ 2, , } [0,T)} ξ( )t I {0,1, ⋅⋅⋅ m j t = ξ( )t λj > I ={0,1,2,⋅⋅⋅⋅⋅⋅} ++t ξ( ) t t + = + j 0( ) j +t + +t t ++t ) = 0 +1 (t t ++ I 0(+t) ξ t t ) ∈[0,T)} 0( ) j j − − λ + + t t µ − +t t t t t t j j j t P t( ) = t = +∞ li T=+ m (ξ ∞ j) 0 1 0 1 2 1, j j j λ λ λ π π µ µ µ ⋅⋅⋅ = = ⋅⋅⋅ j = ,2,⋅⋅⋅) ξ t t ) ≥ 0} I ={0,1,2,⋅⋅⋅,m} I ={0,1,2,⋅⋅⋅} 0 0 1 , j j j j j π λ π ∞ ∞ = = ∑ ∑ I ={0,1,2, m} 定义：设{ ( 为一个随机过程，随机变量 的取值集合为 （或可列集 ），称此集合为状态集，设在时刻t 时 ，那么在时刻t 时， 的概率为λ ，其中 为与 无关的常数；在时刻 时，ξ 为 中其它元素的概率为 。满足上述随机过程{ ( 称为生灭过程。 从上面的定义来看，如果把状态的变化理解为排队系统顾客的到达和离去， 则在时间增量+ 内，只会有一个到达，或有一个离去，或既无到达也无离去（此 种情况的概率为1 ），除此以外的其他到达、离去情况认为 是不可能发生的。并且，在+ 内到达一个顾客的概率和+ 的长短有关，而与 起始时刻 无关；到达一个的概率还与 时刻的顾客到达数 有关（因λ 与 有 关），而和 时刻以前的状态无关。同理，可进行+ 时间内离开一个顾客的概率 情况分析。 2. 生灭过程的稳态概率 进一步考察生灭过程中时间T 的情况。对生灭过程我们更关心的是极 限 。可以证明下面的定理。 定理 3 令 ( 1 并设生灭过程{ ( 的状态集为 或 ，那么， 当下列条件 满足时，对于任意正数 和任意 ，都有 。当状态集为有限集 ⋅⋅⋅, 时
Po P,=P0 P-1J=1,2,…,m 当状态集为无限集Ⅰ={0,1,}时 Po 丌 P=mB÷4 我们称P(=012…)为生灭过程在统计平衡时的概率,或称为稳态概率 对于生灭过程,因为时刻t时状态为j的概率分布P((1)=j)j∈I,将随时 间t的变化而变化,称之为瞬态解。瞬态解是很难求出的,即使求出来也难以利 用。因此,在实际应用中,我们更关心的是稳态概率P,j∈I。稳态概率的含义 是说,当运行时间t无限长时,状态的概率分将不随时间而变化,此时状态为j 的概率P是一个常数。需要指出,虽然在理论上由定理3知,生灭过程需经无限 长的时间才会进入稳态。但在实际应用中,对大多数问题来说,相应的生灭过程 总会很快达到稳态,不需要等到t→+∞之后 9.2一般排队系统结构 921排队模型结构 排队系统(或称为服务系统)可用于描述排队情况。即顾客为了获得某种服 务而到达服务台;若服务员在忙,顾客不能立即获得服务而又被允许排队等待, 则加入等待队列;获得服务之后则立即离开系统。整个过程如图9-1所示。 实际上每个具体的排队系统可能有所不同,但一般的排队系统都具有三个要 素,这就是输入过程;排队规则;服 务机构。由这三个要素便可以构造出 一个一般排队系统的结构模型。并由到达 此得到描述系统运行情况的数学模 等待线 服务台 型。下面对这三个要素再加以具体的 讨论。 图 1.输入过程
1 0 0 ( )j j p π ∞ − = = ∑ 1 0 1 j j j j j p p p λ π µ − = = − j =1,2,⋅⋅⋅,m 当状态集为无限集 I ={0,1,⋅⋅⋅}时 1 0 1 ( )j j p π ∞ − = = ∑ 1 0 1 j j j j j p p p λ π µ − = = − j =1,2,⋅⋅⋅ 我们称 P j j( 0 = ,1,2,⋅⋅⋅)为生灭过程在统计平衡时的概率，或称为稳态概率。 对于生灭过程，因为时刻t 时状态为 j 的概率分布 P t ( ( ξ ) = j) j ∈ I ，将随时 间 的变化而变化，称之为瞬态解。瞬态解是很难求出的，即使求出来也难以利 用。因此，在实际应用中，我们更关心的是稳态概率 。稳态概率的含义 是说，当运行时间t 无限长时，状态的概率分将不随时间而变化，此时状态为 t , P j j ∈ I j 的概率 是一个常数。需要指出，虽然在理论上由定理 3 知，生灭过程需经无限 长的时间才会进入稳态。但在实际应用中，对大多数问题来说，相应的生灭过程 总会很快达到稳态，不需要等到t 之后。 Pj → +∞ 9.2 一般排队系统结构 9.2.1 排队模型结构 排队系统（或称为服务系统）可用于描述排队情况。即顾客为了获得某种服 务而到达服务台；若服务员在忙，顾客不能立即获得服务而又被允许排队等待， 则加入等待队列；获得服务之后则立即离开系统。整个过程如图 9-1 所示。 实际上每个具体的排队系统可能有所不同，但一般的排队系统都具有三个要 素，这就是输入过程；排队规则；服 务机构。由这三个要素便可以构造出 一个一般排队系统的结构模型。并由 此得到描述系统运行情况的数学模 型。下面对这三个要素再加以具体的 讨论。 图 9-1 1. 输入过程 到达 等待线 1 服务台 离去
对于输入过程,我们需要了解的一个方面是顾客源的情况(顾客的总体可能 是有限集,也可能是无限集),但主要的方面是了解顾客到达服务系统的规律, 这种规律主要反映在顾客相继到达间隔时间的概率分布上。几种主要情况如下: (1)定长输入。顾客有规律的到达,每隔时间a到达一位顾客。例如自动生产 线上的装配件。顾客相继到达的间隔时间{Tn}的分布函数是 0 t0 P(Tn≤1)= t0 t<0 (4)一般独立分布。即中{n}各个T相互独立,且都具有相同的概率分布。 图92 2.服务机构 关于此要素需要明确的是:服务台的个数、服务台之间的串并联结构(图 9-2)、服务台为每位顾客服务所需的时间r的分布情况
对于输入过程，我们需要了解的一个方面是顾客源的情况（顾客的总体可能 是有限集，也可能是无限集），但主要的方面是了解顾客到达服务系统的规律， 这种规律主要反映在顾客相继到达间隔时间的概率分布上。几种主要情况如下： (1)定长输入。顾客有规律的到达，每隔时间α到达一位顾客。例如自动生产 线上的装配件。顾客相继到达的间隔时间{Tn}的分布函数是： 0 ( ) 1 P Tn t ≤ = t t α α < ≥ (2)最简单流。即{Tn}中各个Tn 相互独立且都服从同一负指数分布： 1 ( ) 0 t n e P T t −λ − ≤ = 0 0 t t ≥ < 或者说，在[0 内到达的顾客数 相应的随机过程是泊松过程，即 的 概率分布为： ,t) N t( ) N t( ) ( ) ( ( ) ) ! k t t PNt k e k λ −λ = = k = 0,1,2,⋅⋅⋅ (3) k 阶爱尔朗分布。即{ 中各个T 相互独立，且都具有相同的爱尔朗分布 密度： } Tn n 1 ( ) ( ) ( 1)! 0 k t t e p t k λ λ λ − − = − t 0 t 0 ≥ < (4)一般独立分布。即中{Tn}各个Tn 相互独立，且都具有相同的概率分布。 图 9-2 2. 服务机构 关于此要素需要明确的是：服务台的个数、服务台之间的串并联结构（图 9-2）、服务台为每位顾客服务所需的时间τn 的分布情况。 (c) (b) s 1 1 s (a) 1
下面介绍几种常见的服务时间分布: (1)定长分布每位顾客的服务时间rn均为常数,Tn的分布函数为 P(Tn≤1) 07n0 (3)k阶爱尔朗分布{rn}中各个r相互独立,且都具有相同的k阶爱尔朗分 布,其密度函数为 t0 (4)一般独立分布{rn}中各个rn相互独立,且都具有相同的概率分布 3.排队规则 排队规则可描述到达的顾客按照怎样的顺序接受服务。在不同的实际问题 中,排队规则是多样的。一般可分为损失制、等待制、混合制三类。 当一位顾客到达时,若所有的服务台均被占用,该顾客自动消失,具有这种 特点的排队规则称为损失制。例如,一位顾客到达某一旅馆,如果已经客满,他 就会离开这旅馆到别处投宿。 顾客到达时,若所有的服务台均被占用,顾客将排成队伍等待服务,具有这 种特点的排队规则称为等待制。接受服务的次序一般采用先到先服务规则。也可 以有其他规则,例如后到先服务、优先权先服务、随机服务(选取等待队列中任 一顾客进行服务)等等。后面讨论的排队模型都采用“先到先服务”的规则。 混合制是损失制和等待制兼而有之的情况。假定服务系统的容量有限,最多 只能容纳k个顾客(包括等待和正在接受服务的顾客),那么当顾客到达时,发 现服务系统已客满,该顾客将自动消失,否则就进入服务系统,这是一种情况。 此外,还可以有顾客等待服务时间有限的情况,即当超过一定时间时,顾客将自 动消失。 922排队系统的数量指标 一个服务系统,一方面是如果服务机构过小而不能满足顾客的需要。就会产 生拥挤现象并造成服务质量的下降。因此顾客希望机构大些好。另一方面,如果 服务机构过大,则人力、物力等方面的开支要增加,并有可能造成资源的浪费, 从这方面的分析来看,设置的服务机构过大未必能收到好的效果,因此希望机构 小些。研究排队系统的目的就是要在顾客的需要和服务机构的规模之间进行权衡
下面介绍几种常见的服务时间分布： (1)定长分布 每位顾客的服务时间τn 均为常数β , τn 的分布函数为 0 ( ) 1 P t n τ ≤ = n n τ β τ β < ≥ (2)负指数分布 {τn}中各个τn 相互独立，且都服从相同的负指数分布 0 ( ) 1 n t P t e µ τ − ≤ = − 0 0 t t < ≥ (3) k 阶爱尔朗分布 { 中各个 相互独立，且都具有相同的 阶爱尔朗分 布，其密度函数为 }n τ n τ k 1 0 ( ) ( ) ( 1)! k t p t t e k µ µ µ − − = − 0 0 t t < ≥ (4)一般独立分布 {τn}中各个τn 相互独立，且都具有相同的概率分布。 3. 排队规则 排队规则可描述到达的顾客按照怎样的顺序接受服务。在不同的实际问题 中，排队规则是多样的。一般可分为损失制、等待制、混合制三类。 当一位顾客到达时，若所有的服务台均被占用，该顾客自动消失，具有这种 特点的排队规则称为损失制。例如，一位顾客到达某一旅馆，如果已经客满，他 就会离开这旅馆到别处投宿。 顾客到达时，若所有的服务台均被占用，顾客将排成队伍等待服务，具有这 种特点的排队规则称为等待制。接受服务的次序一般采用先到先服务规则。也可 以有其他规则，例如后到先服务、优先权先服务、随机服务（选取等待队列中任 一顾客进行服务）等等。后面讨论的排队模型都采用“先到先服务”的规则。 混合制是损失制和等待制兼而有之的情况。假定服务系统的容量有限，最多 只能容纳 个顾客（包括等待和正在接受服务的顾客），那么当顾客到达时，发 现服务系统已客满，该顾客将自动消失，否则就进入服务系统，这是一种情况。 此外，还可以有顾客等待服务时间有限的情况，即当超过一定时间时，顾客将自 动消失。 k 9.2.2 排队系统的数量指标 一个服务系统，一方面是如果服务机构过小而不能满足顾客的需要。就会产 生拥挤现象并造成服务质量的下降。因此顾客希望机构大些好。另一方面，如果 服务机构过大，则人力、物力等方面的开支要增加，并有可能造成资源的浪费， 从这方面的分析来看，设置的服务机构过大未必能收到好的效果，因此希望机构 小些。研究排队系统的目的就是要在顾客的需要和服务机构的规模之间进行权衡
