排队论模型（一）：基本概念、输入过程与服务时间的常用概率分布

浅夏110

排队论起源于 1909 年丹麦电话工程师 A. K．爱尔朗的工作，他对电话通话拥挤问 题进行了研究。1917 年，爱尔朗发表了他的著名的文章—“自动电话交换中的概率理 论的几个问题的解决”。排队论已广泛应用于解决军事、运输、维修、生产、服务、库 存、医疗卫生、教育、水利灌溉之类的排队系统的问题，显示了强大的生命力。
$ a6 Q0 Y9 v" b; O1 K$ S8 s
排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常 常要排队。此时要求服务的数量超过服务机构（服务台、服务员等）的容量。也就是说， 到达的顾客不能立即得到服务，因而出现了排队现象。这种现象不仅在个人日常生活中 出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机 待修，水库的存贮调节等都是有形或无形的排队现象。由于顾客到达和服务时间的随机 性。可以说排队现象几乎是不可避免的。

排队论（Queuing Theory）也称随机服务系统理论，就是为解决上述问题而发展 的一门学科。它研究的内容有下列三部分：
; p7 w! d# l$ O
（i）性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。
; I# I8 U6 B1 ~
（ii）最优化问题，又分静态最优和动态最优，前者指最优设计。后者指现有排队系统的最优运营。
6 n. C. a7 \. q2 u: k6 {& H
（iii）排队系统的统计推断，即判断一个给定的排队系统符合于哪种模型，以便 根据排队理论进行分析研究。
4 |- D0 @4 z: W6 A' K4 t! Z/ W
这里将介绍排队论的一些基本知识，分析几个常见的排队模型。
5 H* [# ^8 Y4 N2 a% i/ ~: R
1.1  排队过程的一般表示
下图是排队论的一般模型。



9 m, t/ {# a% [' W9 e图中虚线所包含的部分为排队系统。各个顾客从顾客源出发，随机地来到服务机构，按 一定的排队规则等待服务，直到按一定的服务规则接受完服务后离开排队系统。

凡要求服务的对象统称为顾客，为顾客服务的人或物称为服务员，由顾客和服务员组成服务系统。对于一个服务系统来说，如果服务机构过小，以致不能满足要求服务的 众多顾客的需要，那么就会产生拥挤现象而使服务质量降低。 因此，顾客总希望服务 机构越大越好，但是，如果服务机构过大，人力和物力方面的开支也就相应增加，从而 会造成浪费，因此研究排队模型的目的就是要在顾客需要和服务机构的规模之间进行权衡决策，使其达到合理的平衡。

2 排队系统的组成和特征
, f. k8 A0 Y6 f+ w2 q# D一般的排队过程都由输入过程、排队规则、服务过程三部分组成，现分述如下：

3 U# p, |# P( r' r+ L1 a! {2.1 输入过程
9 t, E0 n7 c4 R+ S1 Y6 s7 n5 g输入过程是指顾客到来时间的规律性，可能有下列不同情况：

2 }8 G) C" @0 Q' a（i）顾客的组成可能是有限的，也可能是无限的。

+ \. s  l) Q8 n1 h6 B（ii）顾客到达的方式可能是一个—个的，也可能是成批的。
- g) ]: D  ^) O. I2 n# L
（iii）顾客到达可以是相互独立的，即以前的到达情况对以后的到达没有影响； 否则是相关的。

（iv）输入过程可以是平稳的，即相继到达的间隔时间分布及其数学期望、方差等 数字特征都与时间无关，否则是非平稳的。

; l9 i4 `2 N' T5 i, s2.2 排队规则
1 j4 v) i6 |; A2 W8 ?! i* D- z排队规则指到达排队系统的顾客按怎样的规则排队等待，可分为损失制，等待制和 混合制三种。

（i）损失制（消失制）。当顾客到达时，所有的服务台均被占用，顾客随即离去。
" h9 p) n6 T3 M
6 @9 v+ y# t7 G! c（ii）等待制。当顾客到达时，所有的服务台均被占用，顾客就排队等待，直到接 受完服务才离去。

% l% l( z! \2 P2 H            例如出故障的机器排队等待维修就是这种情况。
7 Q8 F7 Y6 R" x6 {% U
（iii）混合制。介于损失制和等待制之间的是混合制，即既有等待又有损失。有 队列长度有限和排队等待时间有限两种情况，在限度以内就排队等待，超过一定限度就 离去。
3 i: A/ D& ?) s
9 n7 W7 N8 c* k2 S7 d排队方式还分为单列、多列和循环队列。

2.3 服务过程
% z: l. s! b) K* a（i）服务机构。
  g6 F3 w+ k$ _& e! Q- I+ ^! [主要有以下几种类型：单服务台；多服务台并联（每个服务台同 时为不同顾客服务）；多服务台串联（多服务台依次为同一顾客服务）；混合型。
) q; J0 @2 J! I4 j, l! D
（ii）服务规则。
按为顾客服务的次序采用以下几种规则：

①先到先服务，这是通常的情形。
" N; ?3 H& G9 `( C( M$ z1 {* A& g$ O
) _4 p0 S& \1 z4 Q6 g②后到先服务，如情报系统中，最后到的情报信息往往最有价值，因而常被优先处 理。

# m! A. |* a: j  u③随机服务，服务台从等待的顾客中随机地取其一进行服务，而不管到达的先后。
4 Q0 H: L# x$ ^- m( u2 {
④优先服务，如医疗系统对病情严重的病人给予优先治疗。

( B& R7 k; U' S2 X3 排队模型的符号表示
7 Q- f# z% y5 m" J  D( C排队模型用六个符号表示，在符号之间用斜线隔开，即 X /Y / Z / A/ B /C 。

第一 个符号 X 表示顾客到达流或顾客到达间隔时间的分布；

第二个符号Y 表示服务时间的 分布；           第三个符号 Z 表示服务台数目；
; p) `( T2 O) l' q) L& p6 @
& h/ c$ N; P' V% F. F) R7 J第四个符号 A 是系统容量限制；        第五个符号 B 是 顾客源数目；       第六个符号C 是服务规则，

如先到先服务 FCFS，后到先服务 LCFS 等。并约定，如略去后三项，即指 X /Y / Z / ∞ / ∞ / FCFS的情形。
$ y6 d# k5 h8 u! F0 W. r
我们只讨论先到先服务 FCFS 的情形，所以略去第六项。
+ H" J7 j( A( `" j5 l/ l
表示顾客到达间隔时间和服务时间的分布的约定符号为：

M —  指数分布（ M 是 Markov 的字头，因为指数分布具有无记忆性，即 Markov 性）；
# [) h8 U. w: ]3 H9 I
7 s4 a' x$ r4 Y' m) ]0 xD — 确定型（Deterministic）；
6 t, @- l6 w, i( J7 }
4 e- @* K. D% L% O( J$ Y! z  b   — k 阶爱尔朗(Erlang)分布；
, U$ I3 G3 o! m4 u+ P+ z& `
G —     一般（general）服务时间的分布；

GI —  一般相互独立（General Independent）的时间间隔的分布。

例如， M / M /1表示相继到达间隔时间为指数分布、服务时间为指数分布、单服 务台、等待制系统。

D / M / c 表示确定的到达时间、服务时间为指数分布、 c 个平行 服务台（但顾客是一队）的模型。

! \5 w5 X3 ~9 w5 W- e4 排队系统的运行指标
为了研究排队系统运行的效率，估计其服务质量，确定系统的最优参数，评价系统 的结构是否合理并研究其改进的措施，必须确定用以判断系统运行优劣的基本数量指标，这些数量指标通常是：
. r9 F7 h) \! J% d; j( V
(i)平均队长：指系统内顾客数（包括正被服务的顾客与排队等待服务的顾客）的 数学期望，记作 Ls 。
1 ?" y; D5 F; I" c: w" b
  q6 b8 }, k& ^5 X(ii)平均排队长:指系统内等待服务的顾客数的数学期望，记作 Lq 。

# F2 J/ K. R( n8 }* Z(iii)平均逗留时间：顾客在系统内逗留时间（包括排队等待的时间和接受服务的 时间）的数学期望，记作Ws 。

, F' y* ]- S) K3 j$ q# t: L7 G（iv）平均等待时间：指一个顾客在排队系统中排队等待时间的数学期望，记作 Wq 。
$ Q8 E& i" [2 l+ a2 h1 r
( ^! t/ c' p& [; L) E* ^* {5 e3 n（v）平均忙期：指服务机构连续繁忙时间（顾客到达空闲服务机构起，到服务机 构再次空闲止的时间）长度的数学期望，记为Tb 。

  @! Q, R" f% ?; O: j6 k  g/ C' r还有由于顾客被拒绝而使企业受到损失的损失率以及以后经常遇到的服务强度等， 这些都是很重要的指标。

计算这些指标的基础是表达系统状态的概率。所谓系统的状态即指系统中顾客数， 如果系统中有n 个顾客就说系统的状态是n ，它的可能值是





6 {- k+ J* v, S3 输入过程与服务时间的分布
6 W: K+ w7 j( D% n7 p* U排队系统中的事件流包括顾客到达流和服务时间流。由于顾客到达的间隔时间和服 务时间不可能是负值，因此，它的分布是非负随机变量的分布。最常用的分布有泊松分布、确定型分布，指数分布和爱尔朗分布。

3.1 泊松流与指数分布
0 A5 a# P$ K% m% {8 R/ \; S4 M; g
6 @6 T8 |' G9 ~8 R4 ^

. j4 n, @, h$ s) N1 t

在上述条件下，我们研究顾客到达数n 的概率分布。
& l7 [# {5 E0 r


4 A; H3 E+ V4 l! V
7 F2 A# V9 W- w/ E8 l0 w
0 X0 Y3 B- f/ P; q1 d/ C
& J% L+ {$ Z# f8 T- y/ G& P对于泊松流, λ 表示单位时间平均到达的顾客数,所以  就表示相继顾客到达平均 间隔时间，而这正和 ET 的意义相符。 对一顾客的服务时间也就是在忙期相继离开系统的两顾客的间隔时间，有时也服从 指数分布。这时设它的分布函数和密度函数分别是
0 C% n% e$ |# B( f

2 v1 j5 r' B) z& e' C  o/ R5 r
5 N+ \6 Z. y5 p& Q( p3.2 常用的几种概率分布及其产生
3.2.1 常用的连续型概率分布

我们只给出这些分布的参数、记号和通常的应用范围，更详细的内容参看专门的概 率论书籍。

（i）均匀分布
区间 (a,b) 内的均匀分布记作U(a,b) 。服从U(0,1) 分布的随机变量又称为随机 数，它是产生其它随机变量的基础。如若 X 为U(0,1) 分布，则Y = a + (b − a)X 服从 U(a,b) 。
+ V" ~- I3 k9 G# H: Q% m
& V3 b# d& `# S4 ?（ii）正态分布



正态分布还可以作为二项分布一定条件下的近似。
2 X! E  W; z. _4 @
（iii）指数分布
, ?' j8 ?  W+ g' K


（iv）Gamma 分布、爱尔朗分布
% @( ^# D4 V4 I- x( o( l+ z6 pGamma 分布又称爱尔朗分布。
% t6 J3 O8 X+ k/ N
Gamma 分布是双参数α,β 的非对称分布，记作G(α,β ) ，期望是αβ 。α = 1时蜕 化为指数分布。 n 个相互独立、同分布（参数 λ ）的指数分布之和是 Gamma 分布 （α = n, β = λ) 。Gamma 分布可用于服务时间，零件寿命等。
% n# ~3 k* B. Y- U) ?! j
（v）Weibull 分布
      Weibull 分布是双参数α,β 的非对称分布，记作W(α, β ) 。α = 1时蜕化为指数分 布。作为设备、零件的寿命分布在可靠性分析中有着非常广泛的应用。

3 m7 Y: c, N9 X/ W8 I（vi）Beta 分布
7 E$ ^! ?' [' e0 _  M4 a# bBeta 分布是区间(0,1) 内的双参数、非均匀分布，记作 B(α, β ) 。
! L! O. j  F; F  t% K
2.2.2 常用的离散型概率分布
2 k5 |" `; d! t; J$ X* k$ O
（i）离散均匀分布
6 o8 ~) C( Y8 \( i6 l（ii）Bernoulli 分布（两点分布）
Bernoulli 分布是 x = 1,0 处取值的概率分别是 p 和1− p 的两点分布，记作 Bern( p) 。用于基本的离散模型。
) o  ~. n' ]/ D) v5 K) G3 v
（iii）泊松（Poisson）分布
泊松分布与指数分布有密切的关系。当顾客平均到达率为常数 λ 的到达间隔服从 指数分布时，单位时间内到达的顾客数 K 服从泊松分布，即单位时间内到达 k 位顾客 的概率为


# h8 v2 N+ k) J* t1 u
记作 Poisson(λ) 。泊松分布在排队服务、产品检验、生物与医学统计、天文、物理等 领域都有广泛应用。

（iv）二项分布
在独立进行的每次试验中，某事件发生的概率为 p ，则 n 次试验中该事件发生的 次数 K 服从二项分布，即发生k 次的概率为
# B; W5 S+ W  S' }

( R# S9 x) N% k$ ~3 M# m  @
记作 B(n, p) 。二项分布是n 个独立的 Bernoulli 分布之和。它在产品检验、保险、生 物和医学统计等领域有着广泛的应用。
4 ?! I% o: I# i
5 y7 n; Y2 O5 Y$ `当n,k 很大时， B(n, p) 近似于正态分布 N(np,np(1− p)) ；

当n 很大、 p 很小， 且np 约为常数λ 时， B(n, p) 近似于 Poisson(λ)。

5 \2 M, h# g& |" \- s

" F6 L$ ?* O% ?) n( V' O————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/java/article/details/89735320

& ]4 O1 o, t2 F4 O