排队论之简单排队系统
5.2.4 无限源的简单排队系统
所谓无限源的简单排队系统是指顾客的来源是无限的，输入过程是简单流，服务时间是负指数分布的排队系统。本节我们讨论一些典型的简单排队系统。
1.//1/M M ∞排队系统
//1/M M ∞排队系统是单服务台等待制排队模型,可描述为：假设顾客以Poisson 过程（具有速率λ）到达单服务员服务台，即相继到达时间间隔为独立的指数型随机变量，具有均值1λ，若服务员空闲，则直接接受服务，否则，顾客排队等待，服务完毕则该顾客离开系统，下一个排队中的顾客（若有）接受服务。相继服务时间假定是独立的指数型随机变量，具有均值μ。两个M 指的是相继到达的间隔时间和服务时间服从负指数分布，1指的是系统中只有一个服务台，∞指的是容量为无穷大，而且到达过程与服务过程是彼此独立的。
为分析之，我们首先确定极限概率0,1,2,n p n •••=，，为此，假定有无穷多房间，标号为 0,1,2,•••，并假设我们指导某人进入房间n （当有n 个顾客在系统中），则其状态转移框图如图5.8所示。
图5.8 //1/M M ∞排队系统状态转移速率框图
由此，我们有
状态 离开速率＝进入速率
0 01p p λμ=
,1n n ≥ ()11n n n p p p λμλμ-++=+
解方程组，容易得到
00,1,2,i
i p p i λμ•••⎛⎫
== ⎪⎝⎭
，
再根据
001
1()1n n n n p p p λμ
λμ
∞
∞
===
==
-∑∑
得到：
01p λμ
=-
，
()(1),1n
n p n λλ
μ
μ
=-
≥ 令/ρλμ=，则ρ称为系统的交通强度（traffic intensity ）。值得注意的是这里要求
1ρ<，因为若1ρ>，则0n p =，且系统中的人数随着时间的推移逐渐增多直至无穷，因
此对大多数单服务排队系统，我们都假定1ρ<。
于是，在统计平衡的条件下（1ρ<），平均队长为
,1,1j j L jp λρ
ρμλ
ρ
∞
==
=
=
<--∑
（5-52）
由于a λλ=，根据式（5-2）、（5-3）以及上式，可得： 平均逗留时间为：
1
,1L
W ρλ
μλ
=
=
<- （5-53） 平均等待时间为：
1
[],1()(1)
Q W W E S W λρ
ρμ
μμλμρ=-=-
=
=<-- （5-54）
平均等待队长为：
22
,1()1Q Q L W λρλρμμλρ
===<-- （5-55）
另外，根据队长分布易知，01ρρ=-也是系统空闲的概率，而ρ正是系统繁忙的概率。显然，ρ越大，系统越繁忙。
队长()N t 由0变成1的时刻忙期即开始，此后()N t 第一次又变回0时忙期就结束。由简单流与负指数分布的性质，显见忙期的长度与忙期的起点无关。可以证明，闲期的期
望值为1λ，令忙期平均长度为b ， 则在统计平衡下，有：平均忙期：平均闲期＝(1)ρρ-：
，因此平均忙期长度为：
1
11b ρμλρ⎧<⎪
-=⎨⎪∞≥⎩
，， （5-56）
一个忙期中所服务的平均顾客数为
1
111b ρρ
μρ⎧<⎪
-⋅=⎨⎪∞≥⎩
，， （5-57） 不难看出，在忙期内相继输出的间隔时间是独立、同参数(0)μ>的随机变量，即为参数μ的Poisson 流。但是，当系统空闲后，从开始空闲时刻起，到下一个顾客服务完毕离去时之间的间隔时间显然不与服务时间同分布。
下面简要推导一下//1/M M ∞排队系统的输出过程特征。
令n T +
表示第n 个顾客服务完毕的离去时刻，则1n n T T ++
+-表示离去的间隔时间，1n ≥，于是，对0t ≥，
11{}{0}{|0}n n n n n n P T T t P N P T T t N ++++++
++->==⋅->=
1{1}{|1}n n n n P N P T T t N ++++
++≥⋅->≥ 1!ˆ{0}{}n n n P N P S t τ+++==⋅+> 1{1}{},n n P N P S t +
++≥⋅>
其中1ˆn τ+表示剩余到达间隔时间，与1n S +（服务时间间隔）独立，而n N +
表示第n 个离去顾客服务完毕离开系统时的队长。
由于
11,lim {0}01,n n P N ρρρ+
→∞
-<⎧==⎨≥⎩
，
，
而1!ˆ{}n n P S t τ
+++>＝t t e e λμμλμλ
μλ
---
--（根据两独立随机变量和的分布计算公
式计算），所以
1{}(1)t t t n n P T T t e e e λμμμλρρμλμλ++
---+⎡⎤->=--+⎢⎥--⎣⎦
（5-58） 此式表示在统计平衡下，相继输出的间隔时间服从参数(0)λ>的负指数分布。
例5.5 某通信团电话维修站，有1个维修技师，每天工作10小时。待维修电话的到来服从Poisson 分布，每天平均有90部电话到来，维修时间服从指数分布，平均速率为10μ=部/小时。试求排队等待维修的平均电话数；等待维修电话的多于2部的概率；如果使等待
维修的电话数平均为2部，维修速率应提高多少？
解：这是一个//1/M M ∞模型
已知9λ=，10μ=，则0.9λ
ρμ
=
= ① 2
8.11Q L ρρ
=
=- ② 2
0121()1(1)(1)(1)0.729p p p ρρρρρ-++=------=
③ 9929Q L λλμλ
μμμ
==
-
=---，解得：12.29μ= 所以，接待速率应提高：10 2.29μ-=。
例5.6 假设顾客以Poisson 速率为每12分钟1人到达，服务时间是指数型的且服务速率是每8分钟服务1个人，L 和W 分别是多少？
解：因为112λ=
（人／分），18
μ=（人／分），我们得到： 2L =，24W =
因此，系统中顾客的平均个数为2，顾客在系统中平均花费的时间是24分钟。 现假设到达速率提高20％到1
10
λ=
，重新计算L 和W 得到 4L =，40W =
因此，到达速率20％的增加导致系统中平均顾客数增加了1倍。 事实上，从式（5-52）和式（5-53）可以清楚看到，当λμ趋于1时，λ
μ
的一个微小的增加都会导致L 和W 大的增加。
例5.7 战时，集团军通信团的通信设备以指数速率每小时6台损坏，有一个维修技师，其维修速率是指数速率每小时8台，设备损坏而没有得到及时维修造成的损失是每台设备每小时100次通话，问：由于损坏的设备引起的平均通话损失率是多少？
解：该问题是一个//1/M M ∞排队模型，其中6λ=，8μ=。则 平均通话损失率＝每台设备每小时100次⨯损坏设备的平均数 而损坏设备的平均数就是L
3L λμλ
=
=-
因此，平均通话损失率等于每小时300次。 2. ///M M c ∞排队系统
///M M c ∞排队系统是一种多服务等待制系统,指的是：有(1)c c ≥个服务台独立地
并行服务。当顾客到达时，若有空闲服务台便立刻接受服务，若没有空闲的服务台，则排
队等待，直到有空闲的服务台时再接受服务。假定顾客单个到达，相继到达时间间隔服从
参数(0)λ>的负指数分布，每个服务台服务时间独立、服从相同参数(0)μ>的负指数分布，系统容量为无穷大，而且到达与服务是彼此独立的。
设()N t 表示系统中的顾客数，则{()0}N t ≥，是无限状态{0,1,2,}E •••=上的生灭过程，其参数为
10,1,i i i i c i c c i μλλμμ•••≤<⎧===⎨
≤<∞⎩
，
，；， （5-59） 其分布{}()()()0,1,2,n p t P N t n n •••===的平稳状态分布记为0,1,2,n p n •••=，，则
与无限源生灭过程分析类似，考虑有c 个服务台，对任一状态，在统计平衡下，其平衡方程
为：
状态 离开速率＝进入速率
0 01p p λμ=
1 ()1022p p p λμλμ+=+
2 ()21323p p p λμλμ+=+
。。。
1c - ()12(1)c c c c p p c p λμλμ--+-=+
c ()11c c c c p p c p λμλμ-++=+
。。。
1n c ≥+
()11n n n c p p c p λμλμ-++=+
。。。
若记λρμ=
，c c λ
ρμ
=，则当1c ρ<时，解上述平衡方程组，可得： 00
111,!
1,
!
j
j j j c p j c j p p j c c c ρρ-⎧≤≤-⎪⎪=⎨
⎪≥⎪⋅⎩， ， （5-60） 再由概率分布的要求：01n n p ∞
==∑，解得上式中的1
100!!()j c c j c p j c c ρρρ--=⎡⎤
=+⎢⎥-⎣⎦
∑。
由于系统中有c 个服务台，所以顾客到达时需要等待的概率为
,111j c c j c
c p p p c λ
ρρμ
∞
===
=<-∑ （5-61）
其中，0!
c
c p p c ρ=
。
式（5-61）称为Erlang 等待公式，它给出了顾客到达系统时需要等待的概率。
在统计平衡下，等待队长Q L 显然有分布
{0}{}1,2,c
Q j Q c k j P L p P L k p k •••+======∑，， （5-62）
所以当c p 时，有
01()()
!
j Q j j c j c
j c
L j c p j c p c c ρ∞∞
-===-=-⋅∑∑
0()!
c
c
j c
j c
p j c c ρρ∞
-==
-∑02
1
()|!
(1)
c c
j c c
x c j c p x p c ρρρρρ∞
=='=
=
⋅-∑ （5-63） 又令c L 表示系统平衡时，正在被服务的顾客数，则
{}0,1,2,,1{}c k c j
j c
P L k p k c P L c p
•••∞
====-==∑，
； （5-64）
所以正在接受服务的顾客的平均数C L 为：
10
[]c c c j j j j c
L E L jp c p -∞
====+∑∑
1
00101(1)!(1)!c j c
j c j j p p j c ρρρ-∞
===+--∑∑
1
{1}(1)(1)!c
j
j c c
p p c ρρρ∞
=-=-
+--∑
10{1}(1)(1)!
c
c j j c
c p p p c ρρρ∞
-==--+
--∑
ρ
=
（5-65）
上式表明，平均在忙的服务台的个数与服务台个数c 无关。 平均队长L 为
2
1(1)c
Q c c c c L L L p ρρρρ=+=+
⋅<-， （5-66）
可以验证，c →∞时，即化为系统//M M ∞结果（讨论略），1c =时即化为
//1/M M ∞的有关结果。
对多服务台系统，Little’s 公式依然成立，即有： 平均等待时间为
2
,(1)Q c
Q c c L W p ρλρλ
=
⋅=- （5-67） 而平均逗留时间为
1
Q L
W W μ
λ
=+
=
（5-68）
和//1/M M ∞类似，若令T 表示平衡下相继离去的间隔时间，可以证明其分布函数为
{}10t P T t e t λ-≤=-≥，
这表明在统计平衡下相继离去的间隔时间服从参数(0)λ>的负指数分布。因此，统计平衡下///M M c ∞排队系统的输出过程与到达过程相同。
例5.8 工件按Poisson 流到达服务台，平均间隔时间为10分钟，假设对每一工件的服
务（加工）所需时间服从负指数分布，平均服务时间为8分钟。求：
① 工件在系统内等待服务的平均数和工件在系统内平均逗留时间；
② 若要求有90％的把握使工件在系统内的逗留时间不超过30分钟，则工件的平均服务时间最多是多少？
③ 若每一工件的服务分两段，每段所需时间服从负指数分布，平均都为4分钟。在这种情况下，工件在系统内的平均数是多少？
解：该问题属于//1/M M ∞模型
依题意知 110λ=
，1
8
μ=，0.8λρμ==
① 4Q L λμλ
=
=-（个） 1
40W μλ
=
=-（分钟） ② 由90%30W ⨯≤，1
10
λ=
，解得17.69μ≤，故工件的平均服务时间最多是7.69
分钟。
③ 系统已变为//2/M M ∞模型，2c =。
1
4
μ=
，0.4ρ=，c c λρμ==0.2，于是
1
1002!!()3j c c j c p j c c ρρρ--=⎛⎫=+= ⎪-⎝⎭
∑，1
02
0.417(1)!()c Q L L p c c ρρρρ+=+=+≈-- 以上结果表明，采用多服务员、单队列的排队系统方案，其各项运行指标都优于多队
列的排队系统。事实上，该结论是一般性的，其证明过程如下。
例5.9 设//1/M M ∞排队模型中到达速率为λ，服务速率为2μ；//2/M M ∞排队模型中到达速率为λ，服务速率为μ。证明：//1/M M ∞排队模型中的逗留时间少于//2/M M ∞排队模型中的逗留时间，
给出一个直观解释。对排队等待时间有类似结论吗？ 证明： 对//2/M M ∞排队模型，建立平衡方程
01p p λμ=（每个服务台服务速率为μ）
()1022p p p λμλμ+=+
()11
222n n n p p p n λμλμ-++=+≥
方程有解：1
02n n n p p ρ-=，其中λρμ
=
。 又因为
1n n p ∞
==∑，可解得022p ρ
ρ
-=
+，n p 也即可得。因此 0
4(2)(2)
n n L np μλ
μλμλ∞
==
=
+-∑
由L W λ=，我们得到
4(//2)(2)(2)
W W M M μ
μλμλ==
+-
而对具有服务速率为2μ的//1/M M ∞排队系统，有
1
(//1)2W M M μλ
=
-
要使//1/M M ∞排队系统是稳定的，则2μλ>，即有
(//2)(//1)W M M W M M >
直观的解释是：如果一个人发现在//2/M M ∞情形中系统是空的，那么有两个服务台没有什么益处。而具有一个更快的服务台会更好。
记1(//1)Q Q W W M M =，2
(//2)Q Q W W M M =，则 1
(//1)122(2)
Q W W M M λμμμλ=-=
-，
2
2(//2)1(2)(2)
Q
W W M M λμμμλμλ=-=-+
那么
12122Q Q W W λ
μλ
>⇔
>+ 即2μλ>，而这正是//1/M M ∞排队系统稳定的要求。故对于排队等待时间也有类似结论。
3. ///M M c K 混合制排队系统
///M M c K 排队系统是一种多服务混合制排队系统，系统有K 个位置，独立平行工作的服务台数有c 个，c K ≤。当系统中有空位置时，新到的顾客就进人系统排队等待服务，反之，若K 个位置已被顾客全部占用，则新到的顾客自动离开。顾客的相继到达时间间隔服从参数为(0)λ>的负指数分布（即按Poisson 流到达），每个服务台的服务时间独立、服从参数为μ的负指数分布，到达与服务相互独立。
与///M M c ∞排队系统分析类似，假定()N t 表示在时刻t 系统中的顾客数，则
{()0}N t t ≥，是有限状态{0,1,2,,}E K •••=上的生灭过程，其参数为
,0,1,,1i i K λλ•••==-； ,1,
,i i i c c c i K μμμ≤<⎧=⎨≤≤⎩
（5-69）
其分布{}()()()0,1,2,
n p t P N t n n ===的平稳分布记为,0,1,2,
n p n •••
=，对任一
状态，在统计平衡下，其平衡方程为：
状态 离开速率＝进入速率
0 01p p λμ=
1 ()1022p p p λμλμ+=+
2 ()21323p p p λμλμ+=+
。。。
1c - ()12(1)c c c c p p c p λμλμ--+-=+
c ()11c c c c p p c p λμλμ-++=+
11c n K +≤≤- ()11n n n c p p c p λμλμ-++=+
于是对一切()λ
ρρμ
=
，有
00
1,11,!
1,,
!
j
j j j c p j c j p p c j K c c ρρ-⎧≤≤-⎪⎪=⎨⎪≤≤⎪⋅⎩ （5-70）
其中，1
100!!j j c K j c j j c p j c c ρρ---==⎡⎤
=+⎢⎥
⎣⎦
∑∑。 ///M M c K 是损失制，当系统处于状态K 时，顾客不能进入系统，即顾客可进入系
统的概率为1K p -，而顾客损失的概率为
01!K
K K c
p p p c c
ρ-==
（5-71） 单位时间内平均损失的顾客数为
e K p λλ= （5-72）
单位时间内平均进入系统的顾客数为
(1)e K p λλ=- （5-73）
由平稳分布记为,0,1,2,n p n •••=，可得平均等待队长为
001()()()()!!c K
K K n n
Q n n c n
n c
n c n c p p n c n c c L n c p c c c c λρμ-===+--=-==⋅∑∑∑ 10011()()!!c
c
K
K
n
n c c c c n c n c p c p n c n c c c ρρρρ--=+=+=-⋅=-⋅∑∑ 0102()(1)12!1(1)(1)1
!(1)
c
c c
K c K c c c c c c c K c K c p c p K c c ρρρρρρρρρ-+-⎧--+=⎪⎪=⎨⎪⎡⎤----+≠⎣⎦⎪-⎩，
， （5-74）
其中，c c λ
ρμ
=
。 以c L 表示平衡时正在被服务的顾客数，则
{}c j P L j p ==，0,1,,1j c •••=-；{}K
c j j c
P L c p ===∑
于是正在被服务的平均顾客数（或平均被占用的服务台数）为
10
c K
c n n n n c
L np c p -===+∑∑
1
0001
11
(1)!
(1)!
!n
c
j
c K
j c n n c p p p n c c c
ρρρ---==+=+
+
--∑
∑
11000!!j j
c K j c
j j c p p j c c ρρρ---==⎧⎫=+⎨⎬⎩⎭
∑∑ []1K p ρ=- （5-75）
于是得平均队长
[]1Q c Q K L L L L p ρ=+=+- （5-76）
再由Little’s 公式，得到
e
L
W λ=
， 1
Q
Q e
L W W λμ
=
=-
（5-77）
特别地，对一些特殊排队系统的运行指标，有：
(1) //1/M M K 排队系统：
1
(1)110111j
K j p j K K ρρρρρ+⎧-≠⎪⎪-=≤≤⎨⎪=⎪⎩+，， （5-78）
1
112
(1)111K K K L K ρρρρρρ++⎧=⎪⎪=⎨+⎪-≠⎪--⎩，， （5-79） 21
1(1)
12(1)()111Q K K K K K L K ρρρρρρ
ρ++-⎧=⎪+⎪=⎨+⎪-≠⎪--⎩，
， （5-80） (1)e K p λλ=- （5-81）
(1)e
K L
L W p λλ=
=
-， 1
(1)Q Q Q e K L L W W p λλμ
===-- （5-82）
对//1/1M M 单服务台损失制系统，读者可自行推导相关数量指标。 (2) ///M M c c 多服务台损失制系统： ①
()
!0,1,,!i
c
j
j i p j j c i ρρ
•••===∑，
（5-83）
这就是著名的Erlang （埃尔朗）公式。
②c 个服务台均忙的概率（或顾客损失的概率）
()
!!
i
c
c
c i p c i ρρ==∑ （5-84）
这就是著名的Erlang （埃尔朗）损失公式，它在通信网规划与设计中有重要作用。
③因为不允许排队，故有
0,(1)c
Q c n
c n L L L np
p ρ====
=-∑，
1
0,Q e
L
W W λμ
==
=
（5-85）
其中(1)e c p λλ=-为有效到达率，在损失制系统中，还常用(1)c A p λ=-表示系统的绝对通过能力，用1c Q p =-表示系统的相对通过能力，它们分别表示单位时间内系统实际可完成的服务次数和被服务的顾客数与请求服务的顾客数的比值。服务台利用率（或信道利用率）为：
c
L c
η=
（5-86） 此外，也可以将///M M c ∞系统、//1/M M ∞系统、//M M ∞等系统看作是
///M M c K 排队系统的特例，如令1,c K =→∞即为//1/M M ∞系统。
例5.10某通信维修站，目前只有一个维修技师。假设需要维修通信设备的到来的规律服从Poisson 流，平均每4小时到来一台，而设备修理的时间服从负指数分布，平均每3小时1台。如果要求等待维修的通信设备数占要维修设备数的比例为7％，维修站应安排几个位置供待维修通信设备逗留？
解：属于//1/M M K 模型
依题意知 14λ=
（台/时），1
3
μ=（台/时），34λρμ==
因为 11(1)11K K K L ρ
ρρρ+++=---，0(1)Q L L p =--，01
11K p ρ
ρ
+-=-， 令
7%Q L L
=，解得 1.67K ≈。
例5.11 设有一个信息交换中心，信息流为Poisson 流，每分钟到达240份，线路输出
率是每秒800个字符，信息长度（包括控制字符）近似负指数分布，平均长度176个字符。要使在任何瞬间缓冲器充满的概率不超过0.005，问缓冲器的容量K 至少应取多大？
解：信息平均到达率λ=240份／分＝4份／秒， 800
4.546176
μ=
=份／秒，λρμ==
0.88。显然按系统//1/M M K 处理，于是缓冲器充满的概率为
1
(1)1K
K K p ρρρ+-=-
要使0.005K p ≤，由于25260.009045,0.0044640.005,p p ==<所以26,K ≥即缓冲器的容量至少应为26个单位。
例5.12 设某计算机有4个终端，用户按Poisson 流到达，平均每10分钟到达1.5个用户。假定每个用户平均用机时间为20分钟，用机时间服从负指数分布，如果4个终端已被占用，则用户到其它计算机处接受服务，求此系统的各种指标。
解：此为//4/4M M 损失制系统，λ=9人/小时，3μ=人/小时，λ
ρμ
==3， 顾客损失的概率为
()
4
4
40
4!0.235
!i
i p i ρρ===∑，
单位时间内实际进入系统的平均顾客数为
4(1) 6.885e p λλ=-=（人/小时），
平均忙的终端数为
[]41c L p ρ=-＝2.295（个）
。 4. 具有可变到达率和可变服务率的//1/M M ∞排队模型
在实际中，顾客的到达率和服务率是依系统状态的变化而变化的。一般来说，是状态n 的函数。例如，系统中人数较多时，后来的顾客可能不愿意再进入系统；而服务台的服务效率在顾客人数较多时则有可能提高。因此，对单服务台系统，可假设实际的到达率和服务率为：
1
,01,2,(1)
a n n b
n n n λλμμ•••=
==+
而对于多服务系统，实际的到达率和服务率可假设为：
00
11b n n k k n k n λλλ≤-⎧⎪=⎨⎛⎫≥⎪⎪+⎝⎭
⎩，1
1a n n n k n k n k k μμμ≤⎧⎪=⎨⎛⎫≥⎪⎪⎝⎭⎩
例如，考虑一个参数为1
n n λ
λ=
+，,01,2,n n μμ•••==的到达依赖状态的单服务台
等待制//1/M M ∞排队系统，其相关的运行指标见下（读者可自己推导一下）：
1,2,
!
n
n p p n n ρ=
=，0p e
ρ
-=，0
n
n L np
ρ∞
==
=∑，
(1)1Q n n L n p e
ρ
ρ∞
-==-=+-∑，有效到达率()0
11
e n n p e n ρλ
λμ∞
-===-+∑
，
e
L
W λ=
，1
Q
Q e
L W W λμ
=
=-
，其中1λ
ρμ
=
<。 5.2.5 有限源简单排队系统
1. ////M M c m m 系统
顾客总数是有限的排队系统称为有限源排队系统，这类排队系统的典型例子就是机器维修模型。如有c 个工人共同看管m ()m c ≥台机器，当机器发生故障时即由工人进行适当的修理，修复后再投入使用，修好后的机器有可能再发生故障。或看作是有m 个顾客来到有c 个服务台的系统里接受服务，每个顾客接受服务后仍回到原来的总体，还有可能再来。设每个顾客的到达率均为λ（含义是指单位时间内该顾客来到系统请求服务的次数），且每一顾客在系统外的时间均服从参数为λ的负指数分布，每个服务台的服务时间均服从参数μ的负指数分布。服务时间和顾客到达的时间间隔相互独立。
由于在系统外的顾客的平均数为m L -，故系统的有效到达率为()e m L λλ=-。 仿前分析，设平稳状态下N 的队长分布为,0,1,2,,n p n m •••=，则状态间的转移速率为：
(),0,1,,1n m n n m λλ•••=-=-；,1,
,n n i c c c i m
μμμ≤≤⎧=⎨
<≤⎩ （5-87）
其状态转移强度图如图5.9所示。
图5.9 ////M M c m m 系统转移速率
根据生灭过程的极限定理容易得到：
记,λ
ρμ
=
则{,0}j p j m ≤≤存在,且 0011,!,
!j
j j j c m p j c j p m j p c j m j c c ρρ-⎧⎛⎫≤≤-⎪ ⎪⎪⎝⎭
=⎨
⎛⎫⎪≤≤ ⎪⎪⋅⎝⎭⎩
，
， （5-88） 其中，1
100!!c m j j j c
j j c m m j p j j c c ρρ---==⎡⎤⎛⎫⎛⎫=+⎢⎥ ⎪ ⎪⎝⎭⎝⎭⎣⎦
∑∑。
特别地，当1c =时，有
0!
1,,()!
j j m p p j m m j ρ•••=
=-， （5-89）
其中，1
00!
()!m j j m p m j ρ-=⎡⎤=⎢⎥-⎣⎦
∑
。 用L 与
Q
L 分别表示在统计平衡下系统平均顾客数和等待服务的顾客数，则有
()m
Q j j c
L j c p ==-∑ （5-90）
1
0001!!(1)!()!!()!j m
c m j
j j c j j j c
m m j L jp p p j m j c c m j ρρ--=====+--⋅-∑∑∑ （5-91）
或
()e
Q Q L L L m L λρμ
=+
=+- （5-92） e
L
W λ=
， Q
Q e
L W λ=
（5-93）
另外，系统运行的其它一些重要指标如下 平均忙的服务台数为
11
c m
c j j j j c
L jp c p -===+⋅∑∑ （5-94）
不需接受服务的顾客平均数为
0()m
m j
j L m j p
m L ==
-=-∑ （5-95）
统计平衡下单位时间内需要服务的顾客平均数为
()()m
e j
j m j p
m L λλ
λ==-=-∑ （5-96）
统计平衡下单位时间内平均忙的服务台数为
11c m j j c j j c jp c p L μλμμ-==⎛⎫
=+⋅=⋅ ⎪⎝⎭
∑∑ （5-97）
统计平衡下单位时间内平均忙的服务台数等于单位时间内需要服务的顾客平均数，即
e μλλ= （5-98）
特别地，对单服务台（1c =）系统，读者可自己推出相关指标。
2.////M M c c m 损失制系统
假定有m 个顾客，c 个服务台，当c 个服务台都在忙时，这时需要服务的顾客不等待而离开，其它有关假定条件与////M M c m m 系统相同。
假定()N t 表示时刻t 系统中需要服务的顾客数，类似于////M M c m m 系统的分析易知{()0}N t t ≥，是有限状态{0,1,2,,}E c •••=上的生灭过程，其状态转移速率图如图5.10
所示。参数为()0,1,,11,2,,i i m i i c i i c λλμμ••••••=-=-==，
；，。
图5.10 ////M M c c m 系统状态转移速率
记lim {()}0,1,
,j t p P N t j j c λ
ρμ
•••
→∞=
===，，，则根据生灭过程的极限定理易知：
00,1,2,,j
j c k k m j p j c m k ρρ•••=⎛⎫ ⎪⎝⎭==⎛⎫ ⎪⎝⎭
∑， （5-99） 该分布{0}j p j c ≤≤，
称为恩格塞特（Engset ）分布，而 0()c
c c k k m c
p m m k ρρ=⎛⎫ ⎪⎝⎭=⎛⎫ ⎪⎝⎭
∑ （5-100）
称为恩格塞特损失公式，这是损失的概率。特别地，当m c =时，
0,1,2,,(1)
j j m m j
p j m ρρ•••⎛⎫ ⎪⎝⎭==+， （5-101）
平均需服务顾客数为
1m
j j m L jp ρ
ρ
===
+∑ （5-102） 5.2.6 其它排队系统
前面讨论的内容都是按Poisson 流到达与负指数服务时间的生灭过程排队系统，其主要特点是马尔可夫性，能比较容易地得到队长分布的平稳解。但如果输入过程不是Poisson
流或服务时间不服从负指数分布时，仅知道系统当前的顾客数是不足以推断系统未来状态的。在这一部分里，主要介绍一些特殊排队模型，对有的模型只给出基本运行指标，而不再给出详细的推导。
1. //1/M G ∞排队系统
//1/M G ∞排队系统是一种在通信网设计中经常遇到一般服务的排队系统， 它是指顾客按参数(0)λ>的Poisson 流到达，即相邻到达的间隔时间序列{}1i i τ≥，独立、同负
指数分布()10t
F t e t λ-=-≥，
；服务时间序列{}1i S i ≥，独立，分布为同一般分布()0G t t ≥，，记平均服务时间为0
01()tdG t μ∞
<=⎰。系统中只有一个服务台，容量为无
穷大。顾客到达时，若服务台空闲就立即接受服务，否则就排队等待，并按到达的顺序接
受服务，服务完毕后就离开系统，到达与服务彼此独立。
我们首先引入概念－工作量，然后用这个概念来帮助分析//1/M G ∞排队系统。 对任一排队系统，定义任意时间t 系统的工作量为系统中所有顾客在时间t 的剩余服务时间总和。比如：假设系统中有3个顾客，1个顾客已经接受3个时间单位服务，而其所需服务时间是5个时间单位，还有2个在排队，各需6个时间单位的服务时间，则此时的工作量是2＋6＋6＝14。
记V 为系统的（时间）平均工作量，回忆一下我们在（5-1）给出的基本代价方程，并考虑下面花费规则：若顾客的剩余服务时间是y ，则该顾客以速率为y 单位时间花费，而无论他是在排队或是正在接受服务。则基本代价方程变为：
a V E λ=[一个顾客花费量]
以S 和Q W *
分别表示某个顾客的服务时间和花费在排队上的等待时间，由于等待时该顾客的花费速率为常数S ，而在接受服务时花费速率为S x -（服务用去时间x 后），因此，有：
E [一个顾客花费量] 0()S
Q
E SW S x dx *
⎡⎤+-⎢⎥⎣⎦
⎰＝ 所以
2[]
[]2
a a Q
E S V E SW λλ*
=+ （5-103）
需要特别指出的是，上述等式是一个基本排队恒等式（和5-2～5-4一样），并对几乎所有的模型有效。另外，若顾客的服务时间和等待时间独立，则由式（5-103）得到：
2[]
[]2
a a Q E S V E S W λλ=+
（5-104）
对//1/M G ∞排队系统中任一顾客，由于服务台只有一个，故有：
顾客在系统中的等待＝他到达时系统的工作量 （5-105）
对上式两边同时取数学期望，得
Q W =到达者所看到的系统的工作量的平均值
又由于是Poisson 到达，所以，对//1/M G ∞模型，有：
Q W V =
再结合式（5-104），a λλ=，解得：
22[][]12(1[])2(1)Q E S E S W E S λλλ
ρλρμ
===<--， （5-106）
而队长L ，等待队长Q L ，以及平均逗留时间W 可以由式（5-106）得到：
2222222222[][]
,
2(1[])2(1)
[][]1
[][]2(1[])2(1)[][]
[]2(1[])2(1)
Q Q Q E S E S L W E S E S E S W W E S E S E S E S E S L W E S E S λλλλρλλλρμ
λλλλρ
λρ===--=+=+=+--==+=+--，1λρμ=< （5-107）
系统是以闲期和忙期交替出现的，以n I 和n B 分别表示第n 个闲期和第n 个忙期的长度，1n ≥，因此，在第一个
1
()n
n
n j I
B =+∑单位时间里，服务台的空闲时间为1
n
n j I =∑，所以服
务台空闲的时间比例，即0p ，可以表示为：
12012
12lim
n
n n n
I I I p I I I B B B →∞+++=+++++++
显然，上式中的n I ，n B （1n ≥）相互独立，将分子和分母同除以n ，并利用大数定律，我们得到：
1201212()lim
()()n n n n I I I n
p I I I n B B B n
→∞
+++=++
++++
+
[]
[][]
E I E I E B =
+ （5-108）
其中I 和B 表示空闲和繁忙时间随机变量。
I 表示的是顾客离开系统且系统为空到下一个顾客到达的时间，由于是Poisson 到达，所以
1
[]E I λ
=
（5-109）
由式（5-4），知：忙服务台平均数＝[]E S λ，而忙服务台平均数又等于01p -，所以有
01[]p E S λ=- （5-110）
这样，由（5-108）～（5-110），解得：
[]1[]1[]E S E B E S λμλ=
=--，1λ
ρμ
=< （5-111）
另一个有意思的量是忙期中被服务的顾客数C ，显然
11[][]1[]1E C E B E S μλρ==
=--，1λ
ρμ
=< （5-112）
另外，一些特殊的//1/M G ∞排队系统指标有： (1)//1/M M ∞排队系统：即()1,0t
G t e
t μ-=-≥，当1ρ<时，有
(1)0,1,2,j j p j ρρ•••=-=， （5-113）
(2)//1/M D ∞排队系统：即服务时间分布为定长
1
μ
的定长分布 10,,()11,,
t G t t μμ⎧
<⎪⎪
=⎨
⎪≥⎪⎩
则当1ρ<时，有
011
0101(1)1!!i i j j k j j k
i k i p p e p e j i i ρρρ
ρρρ---====-⎧⎪
⎡⎤⎡⎤
⎨=--+-≥⎢⎥⎢⎥
⎪⎣⎦⎣
⎦⎩
∑∑∑， 而且
2
(2)2(1)2(1)
Q L L ρρρρρ-==--，
22(1)2(1)
Q W W ρρ
μρμρ-=
=--， （5-114）
(3)//1/r M H ∞排队系统：即服务时间分布1
()1i r
t i
i G t e μα
-==-
∑为超指数分布，则
当1
1r
i i
i ραρ
==
<∑时，有
011
111111,
(1)1
111j k j r r
r i i i j i j k
i i i k i i i i p p p j ραρρρααρρρ-+--=====-⎧⎪⎪⎧⎫⎡⎤⎡⎤⎛⎫⎛⎫⎨⎪
⎪⎢⎥=-+≥⎨⎬ ⎪ ⎪⎢⎥⎪+++⎢⎥⎣⎦⎝⎭⎝⎭⎪⎪⎪⎣⎦⎩⎭
⎩
∑∑∑∑，
其中，1,2,,i i
i r λ
ρμ•••
==，，0i α>，且1
1r
i i α==∑，而且
22
1
1
11r
r
i i
i i
i i Q L L αρ
αρ
ρρ
ρ
===+
=
--∑∑，
22
1
1
1
(1)
(1)
r
r
i i
i i
i i Q W W αρ
αρ
μ
λρλρ===
+
=
--∑∑， （5-115）
(4)//1/k M E ∞排队系统：即服务时间分布为参数k μ的k 阶埃尔朗分布
1
()()1!i k k t
i k t G t e
i μμ--==-∑，则当1λ
ρμ=<时，有 011110101,
(1)(1)1(1)1i j j k m i k i j
i j j m i k i j k i m i p p C p C j ρρρρρρρ--+--+-+-====-⎧⎪⎪⎡⎤⎛⎫⎨=-++-≥⎢⎥ ⎪⎪++⎝⎭⎢⎥⎪⎣⎦⎩
∑∑∑， 其中，k
ρ
ρ=
，而且
22
(1)(1)2(1)2(1)
Q k k L L k k ρρρρρ++=+=--，
1(1)(1)2(1)(1)2(1)
Q k k W W k k ρρρ
μλμρμρμρ--=
-=-----， （5-116）
而对多服务台的//M G k 系统，目前还没有精确的计算公式计算Q W ，但有一个近似公式：
21
1
20
[]([])([])([])
2(1)!([])!
(1)!([])k k Q n k
k n E S E S W E S E S k k E S n k k E S λλλλλ--=≈
⎡
⎤--+
⎢⎥--⎣⎦
∑
例 5.13 考虑一个//1/M G ∞系统：忙期中的第一个顾客的服务时间服从分布1G ，其它顾客有服务分布2G 。以C 表示忙期中的顾客数，S 表示任意顾客的服务时间。试证明：
① 001[]a p E S λ==-；
排队论模型
排队论模型 随机服务系统理论是研究由顾客、服务机构及其排队现象所构成的一种排队系统的理论，又称排队论。排队现象是一种经常遇见的非常熟悉的现象，例如：顾客到自选商场购物、乘客乘电梯上班、汽车通过收费站等。随机服务系统模型已广泛应用于各种管理系统，如生产管理、库存管理、商业服务、交通运输、银行业务、医疗服务、计算机设计与性能估价，等等。随机服务系统模拟，如存储系统模拟类似，就是利用计算机对一个客观复杂的随机服务系统的结构和行为进行动态模拟，以获得系统或过程的反映其本质特征的数量指标结果，进而预测、分析或估价该系统的行为效果，为决策者提供决策依据。 排队论模型及其在医院管理中的作用 每当某项服务的现有需求超过提供该项服务的现有能力时，排队就会发生。排队论就是对排队进行数学研究的理论。在医院系统内，“三长一短”的现象是司空见惯的。由于病人到达时间的随机性或诊治病人所需时间的随机性，排队几乎是不可避免的。但如何合理安排医护人员及医疗设备，使病人排队等待的时间尽可能减少，是本文所要介绍的。 一、医院系统的排队过程模型 医院是一个复杂的系统，病人在医院中的排队过程也是很复杂的。如图1中每一个箭头所指的方框都是一个服务机构，都可构成一个排队系统，可见图2。 图1 医院系统的多级排队过程模型 二、排队系统的组成和特征 一般的排队系统都有三个基本组成部分： 1. 输入过程其特征有：顾客源（病人源）的组成是有限的或无限的；顾客单个到来或成批到来；到达的间隔时间是确定的或随机的；顾客的到来是相互独立或有关联的；顾客相继到达的间隔时间分布和所含参数（如期望值、方差等）都与时间无关或有关。 2. 排队规则其特征是对排队等候顾客进行服务的次序有下列规则：先到先服务，后到先服务，有优先权的服务（如医院对于病情严重的患者给予优先治疗，在此不做一般性的讨论），随机服务等；还有具体排队（如在候诊室）和抽象排队（如预约排队）。排队的列数还分单列和多列。 3. 服务机构其特征有：一个或多个服务员；服务时间也分确定的和随机的；服务时间的分布与时间有关或无关。
排队论
11.排队论 11.1基本概念 排队现象是指到达服务机构的顾客数量超过服务机构提供服务的容量,也就是说顾客不能够立即得到服务而产生的等待现象。顾客可以是人,也可以是物,比如说,在银行营业部办理存取款的储户,在汽车修理厂等待修理的车辆,在流水线上等待下一到工序加工的半成品,机场厂上空等待降落的飞机,以及等待服务器处理的网页等,都被认为是顾客。服务机构可以是个人,像理发员和美容师,也可以是若干人,像医院的手术小组。服务机构也还可以是包装糖果的机器,机场的跑道,十字路口的红绿灯,以及提供网页查询的服务器等等。 11因为顾客到达,服务时间具有不确定性,排队系统又称随机服务系统,它的基本结构如图1.所示: 商业服务理发店,银行柜台,机场办理登机手续的柜台,快餐店的点餐柜台 运输行业城市道路的红绿灯,等待降落或起飞的飞机,出租车 制造业待修理的机器,待加工的材料,生产流水线 社会服务法庭,医疗机构 为了描述一个排队系统,我们需要说明输入(到达)和输出(服务)过程,及其他基本特征。表2. 11列举了一些排队系统的到达和服务过程。 表11.2: 排队系统举例 )1(到达过程 通常,我们假设顾客的相继到达间隔时间是相互独立并且都具有相同概率分布。在许多实际 (Poisson流,或指数分布。顾客源可能是有限的,也可情况中,顾客的相继到达间隔是服从泊松) 能是无限的。顾客到来方式可能是一个接一个的,也可能是批量的。比如,到达机场海关的旅行团就是成批顾客。 一般来说,我们假设到达过程不受排队系统中顾客数量的影响。以银行为例,无论银行内有3位顾客还是300位顾客,顾客来到银行的到达过程是不会受到影响的。但是在两种情况下到达过程与排队系统中的顾客数量相关。第一种情况发生在顾客源是有限的系统,比如某工厂共有五台机床,若在维修部中已有两台机床,接下来到达维修部的最大量是三台。另一种情况是当顾客到达排队系统时,如果服务机构的设施都被占用,顾客可能耐心等待,也可能选择离开。比如,当一家航空公司的电话订票中心出现排队时,如果顾客等待时间太长,他就可能挂断电话。顾客就会选择另外一家航空公司。
运筹学 第8章 排队论
第八章 排队论 排队是日常生活和经济管理经常遇到的问题，如医院等待看病的病人、加油站等待加油的汽车、工厂等待维修的机器、港口等待停泊的船只等。在排队论中把服务系统中这些服务的客体称为顾客。由于系统中顾客的到来以及顾客在系统中接受服务的时间等均是随机的，因此排队现象是不可避免的。 对于随机服务系统，若扩大系统设备，会提高服务质量，但会增加系统费用。若减少系统设备，能节约系统费用，但可能使顾客在系统中等待的时间加长，从而降低了服务质量，甚至会失去顾客而增加机会成本。因此，对于管理人员来说，解决排队系统中的问题是：在服务质量的提高和成本的降低之间取得平衡，找到最适当的解。 排队论是优化理论的重要分支。排队论是1909年由丹麦工程师爱尔郎（A.K.Erlang ）在研究电话系统时首先提出，之后被广泛应用于各种随机服务系统。 第一节 排队论的基本概念及所研究的问题 一、基本概念 （一）排队系统的组成 一般的排队系统有三个基本组成部分：顾客的到达（输入过程）、排队规则和服务机构，如图8—1所示。 1．输入过程 输入过程指顾客按什么样的规律到达。包括如下三个方面的内容： （1）顾客总体（顾客源） 指可能到达服务机构的顾客总数。顾客总体数可能是有限的，也可能是无限。如工厂内出现故障而等待修理的机器数是有限的，而到达某储蓄所的顾客源相当多，可近似看成是无限的。 （2）顾客到达的类型 指顾客的到达是单个的还是成批的； （3）顾客相继到达的时间间隔分布 即该时间间隔分布是确定的（定期运行的班车、航班等）还是随机的，若是随机的，顾客相继到达的时间间隔服从什么分布（一般为负指数分布）； 2．排队规则 排队规则指顾客接受服务的规则（先后次序），有以下几种情况。 （1）即时制（损失制） 当顾客来到时，服务台全被占用，顾客随即离去，不排队等候。这种排队规则会损失许多顾客，因此又称为损失制。 （2）等待制 当顾客来到时，若服务台全被占用，则顾客排队等候服务。在等待制中，又可按顾客 顾客达到 排队系统 图8—1
排队论及其应用
排队系统的符号表述 描述符号：①/②/③/④/⑤/⑥ 各符号的意义： ①——表示顾客相继到达间隔时间分布，常用以下符号： M——表示到达的过程为泊松过程或负指数分布； D——表示定长输入； EK——表示K阶爱尔朗分布； G——表示一般相互独立的随机分布。 ②——表示效劳时间分布，所用符号与表示顾客到达间隔时间分布一样。 ③——表示效劳台(员)个数：“1〞表示单个效劳台，“s〞(s>1)表示多个效劳台。 ④——表示系统中顾客容量限额，或称等待空间容量。如系统有K个等待位子，那么，0 数学建模排队论模型 排队论模型是一种数学建模方法，用于研究排队系统中的等待时间、服务效率和资源利用率等问题。排队论模型可以应用于各种领域，如交通运输、医疗服务、银行业务等。本文将介绍排队论模型的基本概念和应用。 一、排队论模型的基本概念 排队论模型的基本概念包括：顾客到达率、服务率、队列长度、等待时间、系统利用率等。 顾客到达率是指单位时间内到达系统的顾客数量，通常用λ表示。服务率是指单位时间内一个服务员能够完成服务的顾客数量，通常用μ表示。队列长度是指系统中正在等待服务的顾客数量。等待时间是指顾客在队列中等待服务的时间。系统利用率是指系统中所有服务员的利用率之和。 排队论模型可以分为单队列模型和多队列模型。单队列模型是指系统中只有一个队列，多个服务员依次为顾客提供服务。多队列模型是指系统中有多个队列，每个队列对应一个服务员，顾客可以选择任意一个队列等待服务。 二、排队论模型的应用 排队论模型可以应用于各种领域，如交通运输、医疗服务、银行业 务等。下面以银行业务为例，介绍排队论模型的应用。 在银行业务中，顾客到达率和服务率是两个重要的参数。顾客到达率受到银行营业时间、银行位置、顾客数量等因素的影响。服务率受到银行服务员数量、服务质量、服务时间等因素的影响。 为了提高银行的服务效率和资源利用率，可以采用排队论模型进行优化。首先需要确定银行的顾客到达率和服务率，然后根据排队论模型计算出等待时间、队列长度、系统利用率等指标。根据这些指标，可以制定相应的服务策略，如增加服务员数量、优化服务流程、提高服务质量等。 例如，如果银行的顾客到达率较高，服务员数量较少，导致顾客等待时间较长，可以考虑增加服务员数量或优化服务流程，以缩短顾客等待时间。如果银行的服务率较低，导致服务员利用率较低，可以考虑提高服务质量或增加服务时间，以提高服务员利用率。 三、排队论模型的局限性 排队论模型虽然可以应用于各种领域，但也存在一些局限性。首先，排队论模型假设顾客到达率和服务率是稳定的，但实际情况中这些参数可能会发生变化。其次，排队论模型假设顾客到达和服务时间是独立的，但实际情况中这些参数可能会相互影响。最后，排队论模型假设顾客在队列中等待服务的时间是无限制的，但实际情况中 5.2.4 无限源的简单排队系统 所谓无限源的简单排队系统是指顾客的来源是无限的，输入过程是简单流，服务时间是负指数分布的排队系统。本节我们讨论一些典型的简单排队系统。 1.//1/M M ∞排队系统 //1/M M ∞排队系统是单服务台等待制排队模型,可描述为：假设顾客以Poisson 过程（具有速率λ）到达单服务员服务台，即相继到达时间间隔为独立的指数型随机变量，具有均值1λ，若服务员空闲，则直接接受服务，否则，顾客排队等待，服务完毕则该顾客离开系统，下一个排队中的顾客（若有）接受服务。相继服务时间假定是独立的指数型随机变量，具有均值μ。两个M 指的是相继到达的间隔时间和服务时间服从负指数分布，1指的是系统中只有一个服务台，∞指的是容量为无穷大，而且到达过程与服务过程是彼此独立的。 为分析之，我们首先确定极限概率0,1,2,n p n •••=，，为此，假定有无穷多房间，标号为 0,1,2,•••，并假设我们指导某人进入房间n （当有n 个顾客在系统中），则其状态转移框图如图5.8所示。 图5.8 //1/M M ∞排队系统状态转移速率框图 由此，我们有 状态 离开速率＝进入速率 0 01p p λμ= ,1n n ≥ ()11n n n p p p λμλμ-++=+ 解方程组，容易得到 00,1,2,i i p p i λμ•••⎛⎫ == ⎪⎝⎭ ， 再根据 001 1()1n n n n p p p λμ λμ ∞ ∞ === == -∑∑ 得到： 01p λμ =- ， ()(1),1n n p n λλ μ μ =- ≥ 令/ρλμ=，则ρ称为系统的交通强度（traffic intensity ）。值得注意的是这里要求 1ρ<，因为若1ρ>，则0n p =，且系统中的人数随着时间的推移逐渐增多直至无穷，因 此对大多数单服务排队系统，我们都假定1ρ<。 于是，在统计平衡的条件下（1ρ<），平均队长为 ,1,1j j L jp λρ ρμλ ρ ∞ == = = <--∑ （5-52） 由于a λλ=，根据式（5-2）、（5-3）以及上式，可得： 平均逗留时间为： 1 ,1L W ρλ μλ = = <- （5-53） 平均等待时间为： 1 [],1()(1) Q W W E S W λρ ρμ μμλμρ=-=- = =<-- （5-54） 平均等待队长为： 22 ,1()1Q Q L W λρλρμμλρ ===<-- （5-55） 另外，根据队长分布易知，01ρρ=-也是系统空闲的概率，而ρ正是系统繁忙的概率。显然，ρ越大，系统越繁忙。 队长()N t 由0变成1的时刻忙期即开始，此后()N t 第一次又变回0时忙期就结束。由简单流与负指数分布的性质，显见忙期的长度与忙期的起点无关。可以证明，闲期的期 望值为1λ，令忙期平均长度为b ， 则在统计平衡下，有：平均忙期：平均闲期＝(1)ρρ-： ，因此平均忙期长度为： 1 11b ρμλρ⎧<⎪ -=⎨⎪∞≥⎩ ，， （5-56） 一个忙期中所服务的平均顾客数为 排队论 一、引言： 日常生活中存在大量有形和无形的排队或拥挤现象，如旅客购票排队，食堂买饭排队，列车调用，计算机进程调用，市内电话占线等现象。凡是具有公共服务性质的事业和工作，凡是出现拥挤现象的领域，都是排队论的用武之地。 排队论是研究服务系统中排队现象随机规律的学科，广泛应用于计算机网络、生产、运输、库存等各项资源共享的随机服务系统，其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。排队论研究的内容有3个方面：统计推断，根据资料建立模型；系统的性态，即和排队有关的数量指标的概率规律性；系统的优化问题。 二、排队论的起源与历史： 排队论起源于20世纪初的电话通话。 1909年丹麦电话工程师 A.K.埃尔朗：话务理论，导出著名的埃尔朗电话损失率公式，自20世纪初以来，电话系统的设计一直在应用这个公式。 20世纪30年代苏联数学家А.Я.欣钦把处于统计平衡的电话呼叫流称为最简单流，瑞典数学家巴尔姆又引入有限后效流等概念和定义。 20世纪50年代初美国数学家关于生灭过程的研究，英国数学家D.G.肯德尔提出嵌入马尔可夫链理论，以及对排队队型的分类方法， L.塔卡奇等人又将组合方法引进排队论，使它更能适应各种类型的排队问题。 20世纪70年代以来人们开始研究排队网络和复杂排队问题的渐近解等，成为研究现代排队论的新趋势。 三、排队论的定义： 排队论(queuing theory), 或称随机服务系统理论, 是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。 排队论模型 排队论也称随机服务系统理论。它涉及的是建立一些数学模型，藉以对随机发生的需求提供服务的系统预测其行为。现实世界中排队的现象比比皆是，如到商店购货、轮船进港、病人就诊、机器等待修理等等。排队的内容虽然不同，但有如下共同特征： ?有请求服务的人或物，如候诊的病人、请求着陆的飞机等，我们将此称为“顾客”。 ?有为顾客提供服务的人或物，如医生、飞机跑道等，我们称此为“服务员”。 由顾客和服务员就组成服务系统。 ?顾客随机地一个一个（或者一批一批）来到服务系统，每位顾客需要服务的时间不一定是确定的，服务过程的这种随机性造成某个阶段顾客排长队，而某些时候服务员又空闲无事。 排队论主要是对服务系统建立数学模型，研究诸如单位时间内服务系统能够服务的顾客的平均数、顾客平均的排队时间、排队顾客的平均数等数量规律。 一、排队论的一些基本概念 为了叙述一个给定的排队系统，必须规定系统的下列组成部分： ?输入过程 即顾客来到服务台的概率分布。排队问题首先要根据原始资料，由顾客到达的规律、作出经验分布，然后按照统计学的方法（如卡方检验法）确定服从哪种理论分布，并估计它的参数值。我们主要讨论顾客来到服务台的概率分布服从泊松分布，且顾客的达到是相互独立的、平稳的输入过程。所谓“平稳”是指分布的期望值和方差参数都不受时间的影响。 ?排队规则 即顾客排队和等待的规则，排队规则一般有即时制和等待制两种。所谓即时制就是服务台被占用时顾客便随即离去；等待制就是服务台被占用时，顾客便排队等候服务。等待制服务的次序规则有先到先服务、随机服务、有优先权的先服务等，我们主要讨论先到先服务的系统。 ?服务机构 服务机构可以是没有服务员的，也可以是一个或多个服务员的；可以对单独顾客进行服务，也可以对成批顾客进行服务。和输入过程一样，多数的服务时间都是随机的，且我们总是假定服务时间的分布是平稳的。若以ξ n 表示服务员为 第n个顾客提供服务所需的时间，则服务时间所构成的序列{ξ n }，n=1，2，… 所服从的概率分布表达了排队系统的服务机制，一般假定，相继的服务时间ξ 1 ， ξ 2，……是独立同分布的，并且任意两个顾客到来的时间间隔序列{T n }也是独立 的。 如果按服务系统的以上三个特征的各种可能情形来对服务系统进行分类，那么分类就太多了。因此，现在已被广泛采用的是按顾客相继到达时间间隔的分布、服务时间的分布和服务台的个数进行分类。 研究排队问题的目的，是研究排队系统的运行效率，估计服务质量，确定系统参数的最优值，以决定系统的结构是否合理，设计改进措施等。所以，必须确 排队论 在日常生活和工作中，人们常常会为了得到某种服务而排队等候。比如顾客到商店购买东西，病人到医院看病，汽车进加油站加油，轮船进港停靠码头等，都会因为拥挤而发生排队等候的现象。这时，商店的售货员和顾客，医院的医生和病人，加油站的加油泵和待加油的汽车，码头的泊位和停泊的轮船等，形成了各自的排队服务系统，简称排队系统。 在一个排队系统中，通常包括一个或多个“服务设施”，服务设施可以指人，如售货员，医院大夫等。也可以是物，如加油泵、码头泊位等。同时还包括许多进入排队系统要求得到服务的“顾客”。这里的顾客是指请求服务的人或物。如到医院看病的病人，或等待加油的汽车等。作为顾客总希望一到系统马上就能得到服务，但客观情况并非如此。由于顾客的到达和服务机构对每个顾客的服务时间具有随机性，因此出现排队现象几乎是不可避免的。当然，为了方便顾客减少排队时间，排队系统可以多开设服务设施。但那将增加系统的投资和运营成本，还可能发生空闲浪费。 排队论（Queueing Theory）是为解决上述问题而发展起来的一门学科。排队论起源于上世纪初，当时的美国贝尔（Bell）电话公司发明了自动电话后，满足了日益增长的电话通讯的需要。但另一方面，也带来了新的问题，即如何合理配置电话线路的数量，以尽可能减少用户的呼叫次数。如今，通讯系统仍然是排队论应用的主要领域。同时在运输、港口泊位设计、机器维修、库存控制等领域也获得了广泛的应用。 6. 1 排队系统的基本概念 6. 1. 1排队系统的一般表示 一个排队系统可以抽象描述为：为了获得服务的顾客到达服务设施前排队，等候接受服务。服务完毕后就自行离开。其中把要求得到服务的对象称为顾客，而把服务者统称为服务设施或服务台。 在排队论中，把顾客的到达和离开称为排队系统的输入和输出。而潜在的顾客总体又称为顾客源或输入源。因此任何一个排队系统是一种输入－输出系统，其基本结构如图6-1所示。 排队系统 图6-1 6. 1. 2排队系统的特征 由排队系统的基本结构可知，任何一个排队系统的特征可以从以下三个方面加以描述。1，系统的输入：是指顾客到达排队系统的情况。主要内容包括 （1）相继到达系统的时间间隔是确定性的还是随机性的。如自动装配线上待装配的部件到达各个工序的间隔时间是确定的，而到银行自动取款机前取款的客户的间隔时间则是随机的。事实上多数排队系统的顾客到达都是随机的。若是随机的，则必须研究顾客相继到达的间隔时间所服从的概率分布，或者研究在一定的时间间隔内到达k（k＝1，2 ）个顾客 体检排队系统设计 附件4： 排队论(queuing theory), 或称随机服务系统理论 是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。它是数学运筹学的分支学科。也是研究服务系统中排队现象随机规律的学科。广泛应用于计算机网络, 生产, 运输, 库存等各项资源共享的随机服务系统。排队论研究的内容有3个方面：统计推断，根据资料建立模型；系统的性态，即和排队有关的数量指标的概率规律性；系统的优化问题。其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。 1、排队模型的表示 X/Y/Z/A/B/C X—顾客相继到达的间隔时间的分布； Y—服务时间的分布； M—负指数分布、D—确定型、Ek —k阶爱尔兰分布； Z—服务台个数； A—系统容量限制（默认为∞）； B—顾客源数目（默认为∞）； C—服务规则（默认为先到先服务FCFS)。 2、排队系统的衡量指标 服务队长Ls—服务中的顾客数； 排队长Lq—队列中的顾客数； 总队长L=Ls+Lq 系统中的顾客总数； 逗留时间Ws—顾客在服务中的等待时间； 等待时间Wq—顾客在队列中的等待时间； 总时间W=Ws+Wq 顾客在系统中的总停留时间； 忙期—服务机构两次空闲的时间间隔； 服务强度ρ； 稳态—系统运行充分长时间后，初始状态的影响基本消失，系统状态不再随时间变化。 3、评价一个排队系统的好坏要以顾客与服务机构两方面的利益为标准。就顾客来说总希望等待时间或逗留时间越短越好，从而希望服务台个数尽可能多些但是，就服务机构来说，增加服务台数，就意味着增加投资，增加多了会造成浪费，增加少了要引起顾客的抱怨甚至失去顾客，增加多少比较好呢？顾客与服务机构为了照顾自己的利益对排队系统中的3个指标：队长、等待时间、服务台的忙期（简称忙期）都很关心。因此这3个指标也就成了排队论的主要研究内容。 4、排队论的应用非常广泛。它适用于一切服务系统。尤其在通信系统、交通系统、计算机、存贮系统、生产管理系统等方面应用得最多。排队论的产生与发展来自实际的需要，实际的需要也必将影响它今后的发展方向。 5、统计数据的分布判断。 6、排队规则 排队规则分为等待制、损失制和混合制三种。当顾客到达时，所有服务机构都被占用，则顾客排队等候，即为等待制。在等待制中，为顾客进行服务的次序可以是先到先服务，或后到先服务，或是随机服务和有优先权服务（如医院接待急救病人）。如果顾客来到后看到服务机构没有空闲立即离去，则为损失制。有些系统因留给顾客排队等待的空间有限，因此超过所能容纳人数的顾客必须离开系统，这种排队规则就是混合制。 数学的统计排队论 在现实生活中，我们经常会遇到需要排队等候的情况，比如买票、 办理业务等。而数学中的统计排队论就是研究这些排队问题的一门学科。统计排队论主要涉及到排队的平均等待时间、服务设备的利用率 以及排队系统的稳定性等问题。本文将介绍统计排队论的基本理论和 应用，以及一些与排队相关的数学模型。 1. 排队系统的基本模型 在排队论中，有三个基本模型被广泛应用，它们分别是M/M/1模型、M/M/c模型和M/M/c/c模型。 M/M/1模型指的是具有泊松到达率和指数服务率的单一服务通道排 队系统。在这个模型中，到达时间和服务时间都符合泊松分布和指数 分布，即到达时间和服务时间是随机的。M/M/1模型的特点是排队系 统的平均等待时间可以通过使用里特方程（也称为相关公式）进行计算。 M/M/c模型是指具有泊松到达率和指数服务率，且有c个并行服务 通道的排队系统。这意味着在该系统中，可以同时有多个顾客被服务。M/M/c模型的特点是可以通过使用平稳分析法计算出顾客的平均等待 时间和系统设备的利用率。 M/M/c/c模型是指具有泊松到达率和指数服务率，同时还考虑了顾 客有限等待区域的排队系统。在M/M/c/c模型中，顾客在进入排队系 统之前需要在一个有限的等待区域等待。该模型的特点是可以通过使用排队论的边界理论计算出系统性能指标。 2. 统计排队论的应用 统计排队论的研究成果可以应用于各个领域，比如交通运输、通信网络、医疗服务等。以下是一些典型的应用场景： 2.1 公共交通系统 公共交通系统中的排队问题很常见，比如地铁站的进站口、公交车站的上车口等。统计排队论可以帮助交通管理者合理设置服务通道和优化乘客的等待时间，提高公共交通系统的效率。 2.2 电话交换系统 电话交换系统中的呼叫中心是一个典型的排队系统。通过使用统计排队论的模型和理论，电话交换系统的设计者可以合理设置服务通道数量和系统容量，以提供更好的服务质量和用户体验。 2.3 服务行业 在一些服务行业，比如银行、医院等，排队问题也是一个重要的考虑因素。通过应用统计排队论的模型，服务行业可以优化服务设备的利用率，减少顾客的等待时间，提高服务质量和效率。 3.其他排队相关的数学模型 除了以上介绍的基本模型之外，统计排队论还涉及到其他一些相关的数学模型。比如排队论中的博弈模型可以研究顾客的行为策略对排 实用排队论 排队论又称随机服务系统，它应用于一切服务系统，包括生产管理系统、通信系统、交通系统、计算机存储系统。它通过建立一些数学模型，以对随机发生的需求提供服务的系统预测。现实生活中如排队买票、病人排队就诊、轮船进港、高速路上汽车通过收费站、机器等待修理等等。 一、排队论的基本构成 （1）输入过程 输入过程是描述顾客是按照怎样的规律到达排队系统的。包括①顾客总体：顾客的来源是有限的还是无限的。②到达的类型：顾客到达是单个到达还是成批到达。③相继顾客到达的时间间隔：通常假定是相互独立同分布，有的是等间隔到达，有的是服从负指数分布，有的是服从k 阶Erlang 分布。 （2）排队规则 排队规则指顾客按怎样的规定的次序接受服务。常见的有等待制，损失制，混合制，闭合制。当一个顾客到达时所有服务台都不空闲，则此顾客排队等待直到得到服务后离开，称为等待制。在等待制中，可以采用先到先服务，如排队买票；也有后到先服务，如天气预报；也有随机服务，如电话服务；也有有优先权的服务，如危重病人可优先看病。当一个顾客到来时，所有服务台都不空闲，则该顾客立即离开不等待，称为损失制。顾客排队等候的人数是有限长的，称为混合制度。当顾客对象和服务对象相同且固定时是闭合制。如几名维修工人固定维修某个工厂的机器就属于闭合制。 (3)服务机构 服务机构主要包括：服务台的数量；服务时间服从的分布。常见的有定长分布、负指数分布、几何分布等。 二、排队系统的数量指标 (1)队长与等待队长 队长（通常记为s L ）是指系统中的平均顾客数（包括正在接受服务的顾客）。等待队长（通常记为q L ）指系统中处于等待的顾客的数量。显然，队长等于等待队长加上正在服务的顾客数。 (2)等待时间 等待时间包括顾客的平均逗留时间（通常记为s W ）和平均等待时间（通常记为q W ）。顾客的平均逗留时间是指顾客进入系统到离开系统这段时间，包括等待时间和接受服务的时间。顾客的平均等待时间是指顾客进入系统到接受服务这段时间。 (3)忙期 从顾客到达空闲的系统，服务立即开始，直到再次变为空闲，这段时间是系统连续繁忙的时期，称之为系统的忙期。它反映了系统中服务机构工作强度，是衡量服务系统利用效率的指标，即 服务强度=忙期/服务总时间=1─闲期/服务总时间 闲期与忙期对应的系统的空闲时间，也就是系统连续保持空闲的时间长度。 排队论 排队论(Queuing Theory) ，是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法，又称随机服务系统理论，为运筹学的一个分支。 1.定义 排队论(queuing theory), 或称随机服务系统理论，是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。 1、排队模型的表示 X/Y/Z/A/B/C X—顾客相继到达的间隔时间的分布； Y—服务时间的分布； M—负指数分布、D—确定型、Ek —k阶爱尔兰分布； Z—服务台个数； A—系统容量限制（默认为∞）； B—顾客源数目（默认为∞）； C—服务规则（默认为先到先服务FCFS)。 2、排队系统的衡量指标 队长Ls—系统中的顾客总数； 排队长Lq—队列中的顾客数； 逗留时间Ws—顾客在系统中的停留时间； 等待时间Wq—顾客在队列中的等待时间； 忙期—服务机构两次空闲的时间间隔； 服务强度ρ； 稳态—系统运行充分长时间后，初始状态的影响基本消失，系统状态不再随时间变化。 3、到达间隔时间与服务时间的分布 泊松分布； 负指数分布； 爱尔兰分布； 统计数据的分布判断。 排队系统的构成及应用前景 排队系统由输入过程与到达规则、排队规则、服务机构的结构、服务时间与服务规划组成。 一般还假设到达间隔时间序列与服务时间均为独立同分布随机变量序列，且这两个序列也相互独立。 评价一个排队系统的好坏要以顾客与服务机构两方面的利益为标准。就顾客来说总希望等待时间或逗留时间越短越好，从而希望服务台个数尽可能多些但是，就服务机构来说，增加服务台数，就意味着增加投资，增加多了会造成浪费，增加少了要引起顾客的抱怨甚至失去顾客，增加多少比较好呢？顾客与服务机构为了照顾自己的利益对排队系统中的3个指标：队长、等待时间、服务台的忙期（简称忙期）都很关心。因此这3个指标也就成了排队论的主要研究内容。 2.组成部分 排队系统又称服务系统。服务系统由服务机构和服务对象（顾客）构成。服务对象到来的时刻和对他服务的时间（即占用服务系统的时间）都是随机的。 输入过程 输入过程考察的是顾客到达服务系统的规律。它可以用一定时间内顾客到达数或前后两个顾客相继到达的间隔时间来描述，一般分为确定型和随机型两种。例如，在生产线上加工的零件按规定的间隔时间依次到达加工地点，定期运行的班车、班机等都属于确定型输入。随机型的输入是指在时间t内顾客到达数 n（t）服从一定的随机分布。如服从泊松分布,则在时间t内到达n个顾客的概率为或相继到达的顾客的间隔时间T 服从负指数分布，即 式中λ为单位时间顾客期望到达数，称为平均到达率；1/λ为平均间隔时间。在排队论中，讨论的输入过程主要是随机型的。 排队规则 排队规则分为等待制、损失制和混合制三种。当顾客到达时，所有服务机构都被占用，则顾客排队等候，即为等待制。在等待制中，为顾客进行服务的次序可 排队是日常生活和工作中常见的现象，例如：上下班坐公交车，等待公交车的排队；顾客到商店购物形成的排队；病人到医院看病形成的排队；往售票处购票形成的排队等；另一种排队是物的排队，例如文件等待打印或发送；路口红灯下面的汽车、自行车通过十字路口。排队现象是由两个方面构成，一方面得到服务，另一方面给予服务。我们把要求得到服务的人或物（设备）统称为顾客，给予服务的服务人员或服务机构或服务台（有时服务员专指人，而服务台是指给予服务的设备）。顾客与服务台就形成一个排队系统，或称为随机服务系统，显然，缺少个或服务台任何一方都不会形成排队系统。 排队现象有的是以有形的形式出现，例如上下班坐公交车等，这种排队我们称为有形排队，而有的是以无形的形式出现的，例如有许多顾客同时打电话到订购处订购机票，当其中一个顾客正在通话时，其他顾客就不得不在各自的电话机旁边等待，他们可能分散在各个地方，但却形成一个无形的队列等待通话，这种排队现象称为无形排队。 在各种排队系统中，随机性是它们的一个共性，而且起着根本性的作用。顾客的到达间隔时间与顾客所需的服务时间中，至少有一个具有随机性，否则问题就太简单了。排队论主要研究描述系统的一些主要指标的概率分布，分为三大部分： 1）排队系统的性态问题 研究排队系统的性态问题就是研究各种排队系统的概率规律，主要包括系统的队长、顾客的等待时间和逗留时间，以及忙期等的概率分布，包括它们的瞬时性质和统计平衡下的性态。排队系统的性态问题是排队论研究的核心，是排队系统的统计推断和最优化问题的基础。从应用方面考虑，统计平衡下的各个指标的概率性质尤为重要。 2）排队系统的统计推断 为了了解和掌握一个正在运行的排队系统的规律，就需要通过多次观测、搜集数据，然后利用数理统计的方法对得到的数据进行加工处理，推断所观测的排队系统的概率规律，从而应用相应的理论成果来研究和解决排队系统的有关问题。排队系统的统计推断是已有理论的成果应用实际系统的基础性工作，结合排队系统的特点，发展这类特殊随机过程的统计推断方法是非常必要的。 3）排队系统的最优化问题 排队系统的最优化问题包括系统的最优设计和已有系统的最优运行控制，前者是在服务系统设置之前，对未来运行的情况有所估计，使设计人员有所依据。后者是对已有的排队系统寻求最优运行策略，例如库房领取工具，当排队领取工具的工人太多，就增设服务员，这样虽然增加了服务费用，但另一方面却减少了 实验一：M/M/1排队系统 一、实验目的 M/M/1是最简单的排队系统，其假设到达过程是一个参数为λ的Poisson 过程，服务时间是参数为μ的负指数分布，只有一个服务窗口，等待的位置有无穷多个，排队的方式是FIFO 。 M/M/1排队系统的稳态分布、平均队列长度，等待时间的分布以及平均等待时间，可通过泊松过程、负指数分布、生灭过程以及Little 公式等进行理论上的分析与求解。 二、实验原理 根据排队论的知识我们知道，排队系统的分类是根据该系统中的顾客到达模式、服务模式、服务员数量以及服务规则等因素决定的。 1、 顾客到达模式 设到达过程是一个参数为λ的Poisson 过程，则长度为t 的时间内到达k 个 呼叫的概率)(t P k 服从Poisson 分布，即e t k k k t t p λλ-= ! )()(，⋅⋅⋅⋅⋅⋅⋅⋅⋅=,2,1,0k ， 其中λ>0为一常数，表示了平均到达率或Poisson 呼叫流的强度。 2、 服务模式 设每个呼叫的持续时间为i τ，服从参数为μ的负指数分布，即其分布函数为 {}1,0t P X t e t μ-<=-≥ 3、 服务规则 先进先服务的规则（FIFO ） 4、 理论分析结果 在该M/M/1系统中，设λρμ = ，则稳态时的平均等待队长为1Q ρλ ρ =-， 顾客的平均等待时间为T ρμλ= -。 三、 实验内容 1、 采用语言 MATLAB 语言，其源代码如下： %总仿真时间 Total_time = 30; %队列最大长度 N = 10; %到达率与服务率 lambda = 0.8; mu = 5; %平均到达时间与平均服务时间 arr_mean = 1/lambda; ser_mean = 1/mu; %可能到达的最大顾客数（round：四舍五入求整数） arr_num = round(Total_time*lambda*2); %顾客事件表初始化 events = []; %按负指数分布产生各顾客达到时间间隔 events(1,:) = exprnd(arr_mean,1,arr_num); %各顾客的到达时刻等于时间间隔的累积和 events(1,:) = cumsum(events(1,:)); %按负指数分布产生各顾客服务时间 events(2,:) = exprnd(ser_mean,1,arr_num); %计算仿真顾客个数，即到达时刻在仿真时间内的顾客数 len_sim = sum(events(1,:)<= Total_time); %***************************************** % 计算第1 个顾客的信息 %***************************************** %第1 个顾客进入系统后直接接受服务，无需等待 events(3,1) = 0; %其离开时刻等于其到达时刻与服务时间之和 events(4,1) = events(1,1)+events(2,1); %其肯定被系统接纳，此时系统内共有1 个顾客，故标志位%置1 events(5,1) = 1; %其进入系统后，系统内已有成员序号为1 member = [1]; %***************************************** % 计算第i 个顾客的信息 %***************************************** for i = 2:arr_num M/G/1型排队系统分析与仿真 一、排队系统 排队论(queuing theory), 或称随机服务系统理论, 是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。它是数学运筹学的分支学科。也是研究服务系统中排队现象随机规律的学科。广泛应用于计算机网络, 生产, 运输, 库存等各项资源共享的随机服务系统。排队论研究的内容有3个方面：统计推断，根据资料建立模型；系统的性态，即和排队有关的数量指标的概率规律性；系统的优化问题。其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。 一般的排队过程为：顾客由顾客源出发，到达服务机构（服务台、服务员）前，按排队规则排队等待接受服务，服务机构按服务规则给顾客服务，顾客接受完服务后就离开。排队过程的一般过程可用下图表示。我们所说的排队系统就是指图中虚线所包括的部分。排队系统又称服务系统。服务系统由服务机构和服务对象（顾客）构成。服务对象到来的时刻和对他服务的时间（即占用服务系统的时间）都是随机的。描述一个排队系统一般需要分析其三个组成部分：输入过程、排队规则和服务机构。 输入过程 输入过程考察的是顾客到达服务系统的规律。它可以用一定时间内顾客到达数或前后两个顾客相继到达的间隔时间来描述，一般分为确定型和随机型两种。例如，在生产线上加工的零件按规定的间隔时间依次到达加工地点，定期运行的班车、班 机等都属于确定型输入。随机型的输入是指在时间t内顾客到达数n（t）服从一定的随机分布。如服从泊松分布,则在时间t内到达n个顾客的概率为 或相继到达的顾客的间隔时间T 服从负指数分布，即 式中λ为单位时间顾客期望到达数，称为平均到达率；1/λ为平均间隔时间。在排队论中，讨论的输入过程主要是随机型的。 排队规则 排队规则分为等待制、损失制和混合制三种。当顾客到达时，所有服务机构都被占用，则顾客排队等候，即为等待制。在等待制中，为顾客进行服务的次序可以是先到先服务，或后到先服务，或是随机服务和有优先权服务（如医院接待急救病人）。如果顾客来到后看到服务机构没有空闲立即离去，则为损失制。有些系统因留给顾客排队等待的空间有限，因此超过所能容纳人数的顾客必须离开系统，这种排队规则就是混合制。 服务机构 可以是一个或多个服务台。多个服务台可以是平行排列的，也可以是串连排列的。服务时间一般也分成确定型和随机型两种。例如，自动冲洗汽车的装置对每辆汽车冲洗（服务）时间是相同的，因而是确定型的。而随机型服务时间v 则服从一定的随机分布。如果服从负指数分布，则其分布函数是 式中μ为平均服务率，1/μ为平均服务时间。 二、M/G/1型排队系统 1、问题描述 经典的M/G/1型排队系统 (1)到达过程的特征，M表示无记忆的泊松过程，计到达率为； (2)服务时间的概率表示为G，即一般随机分布，各位顾客的服务时间任意且 、、……之间相互独立，有相同的分布函数B(t)， ， 5。2 排队论 排队是日常生活和工作中常见的现象,它由两个方面构成，一是要求得到服务的顾客，二是设法给予服务的服务人员或服务机构（统称为服务员或服务台）,顾客与服务台就构成一个排队系统，或称为随机服务系统。如图5。5所示。 图5.5 排队系统结构 5.2.1 排队论概述 1. 排队论研究的基本问题 随机性是排队系统的共同特性，顾客的到达间隔时间与顾客所需的服务时间中,至少有一个具有随机性.排队论研究的首要问题是系统的主要数量指标（如：系统的队长（系统中的顾客数）、顾客的等待时间和逗留时间等）的概率特性，然后进一步研究系统优化问题。与这两个问题相关联的还有系统的统计推断问题。 1) 性态问题（即数量指标的研究） 研究排队系统的性态问题就是通过研究系统的主要数量指标的瞬时性质或统计平衡下的性态来研究排队系统的基本特征. 2) 最优化问题 排队系统的最优化问题涉及排队系统的设计、控制以及系统有效性的度量，包括系统的最优设计（静态最优）和已有系统的最优运行控制(动态最优），前者是在服务系统设置之前,对未来运行的情况有所估计，确定系统的参数，使设计人员有所依据；后者是对已有的排队系统寻求最优运行策略。其内容很多，有最小费用问题，服务率的控制问题等。 3) 统计推断问题 排队系统的统计推断是通过对正在运行的排队系统多次观测、搜集数据，用数理统计的方法对得到的资料进行加工处理，推断所观测的排队系统的概率规律,建立适当的排队模型。 2. 排队系统的基本组成及特征 实际中的排队系统是各种各样的，但从决定排队系统进程的因素看，它由3个基本部分组成：输入过程、排队规则和服务机构。由于输入过程、排队规则和服务机构的复杂多样性,可以形成各种各样的排队模型，因此在研究一个排队系统之前，有必要弄清楚这3部分的具体内容和结构。 1） 输入过程 输入过程是说明顾客来源及顾客是按怎样的规律到达系统.它包括3方面内容:①顾客总体（顾客源）数：它可能是有限的，也可能是无限的。②到达的方式：是单个到达还是成批到达。③顾客相继到达的时间间隔的概率分布，分布的参数怎样,到达的间隔时间之间是否独立.令 ()001n T T n =≥，表示第 n 个（批）顾客的到达时刻，则 排队论 排队论（queuing theory）是一门应用十分广泛的运筹学分支，它在各种存在等待情形的环境中都有非常成功的应用。尽管人们有时可能并不太在意等待时间的长短，但在许多商务活动中我们必须给顾客的等待时间以充分的重视。绝大多数大型零售店的设计其实就是平衡顾客方便度和企业运营效率的产物，这很好地解释了为什么一个超级市场可能会有十几个收银通道，尽管在大多数时间里可能只有两三个在运作。零售商不敢让顾客在队伍中等待太长的时间，因为时间对顾客来说可能是十分宝贵的，如果等待时间过长，他们完全有可能转向自己的竞争者。 在管理科学或运筹学中，等待的队伍被称为队列（queue），排队论作为运筹学的一个重要分支在过去的几十年里得到了长足的发展，代表特定环境的模型的数量稳步增加。作为最早的定量优化方法之一，排队论的起源可以追溯到1909年爱尔朗（A. K. Erlang, a Danish telephone engineer）发表的一篇论文，从那时起爱尔朗的名字就与概率排队模型紧密联系了在一起，该论文的发表为后来排队论的发展奠定了坚实的基础。 排队模型的目的就是要规划一种为顾客提供服务的方式以实现一定的运营效率，它并不象前面已经遇到的一些模型（如线性规划模型、存贮模型）那样追逐一个最小成本或最大收益目标。具体来讲，排队模型的目的就是要确定排队系统的各项特征，如平均等待时间、平均队长等；或者是构建一个服务系统以满足特定的顾客服务水平。这些平均值是系统对顾客服务水平的标志，在后续的成本分析中将发挥重要的作用。 §1排队系统综述 在日常生活和生产中，人们会经常碰到各种各样的排队系统，如道路红绿灯系统、超市的收银系统、电话通讯系统等。一些排队系统的构成十分明显，而另一些排队系统的构成可能很模糊。如从广州往北京打电话，由于受广州与北京之间信道通过能力的限制，同一时间通话的人数是有限的；因此，当要求通话人数超过这一限制时，就不得不等待，虽然打电话的人分散在全市的各个角落，彼此互不见面，但他们与长话台一起构成一个服务系统，他们在长话台前形成一个无形的队伍，其实这种无形的队伍与超市收银系统中的有形队伍都可以构成排队系统中的队列。 在排队系统中总是存在一组服务设施（service facility），有许多顾客（customer）随机地来到该系统要求得到服务，服务完毕后即自动离去。如果顾客到达时有服务设施空闲，则到达的顾客即刻得到服务，否则顾客将排队等待或离去。通常我们会自然地认为顾客就是来到服务系统准备接受服务的人，然而在排队系统中顾客不该受到任何限制，可以是人，也可以是物。汽车修理厂等待维修的汽车、机场等待降落的飞机都可以构成排队系统中的顾客。在排队系统中，服务设施同样可以是人、 242数学建模排队论模型
排队论之简单排队系统
排队论
(完整版)排队论模型
上海交通大学管理科学-运筹学课件排队论
排队理论
数学的统计排队论
排队论
排队论(queuingtheory)
排队系统
通信网络实验一MM1排队系统
MG1型排队系统分析与仿真
(完整)排队论
排队系统的基本构成