排队论

排队论（英语：queueing theory），或称排队理论、随机服务系统理论，是研究服务系统中排队现象随机规律的学科^[1]。排队论作为数学运筹学的分支学科广泛应用于电信，交通工程，计算机网络、生产、运输、库存等各项资源共享的随机服务系统，^[2] 和工厂，商店，办公室和医院的设计。^[3]^[4]

排队论研究的内容有3个方面：统计推断，根据资料建立模型；系统的性态，即和排队有关的数量指标的概率规律性；系统的优化问题。其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。

历史与表示法

历史

厄朗（英语：Agner Krarup Erlang）（Agner Krarup Erlang）一个在丹麦哥本哈根电话交换局工作的工程师，研究人们打电话的方式，发展出人们需要等待多久的公式，并于1909年出版了关于排队理论的第一篇论文^[5]。

表示法

1953年，大卫·坎达（David G. Kendall）提出了 A/B/C 等候表示法。

A/B/C/X/Y/Z
- A-到达的规则；
- B-服务规则，即指服务时间（相当于报文发送时间）的长短服从什么规律；
- C-服务台个数
- X-模型中平行的队列（即服务通道或发送信道）数目；
- Y-模型中的最大容量

Z的符号有以下类型

FCFS 先来先服务
LCFS 后来先服务
RSS 随机选择哪个先服务
PR 由优先权决定
GD 通用规则

排队论在电信中的应用

公共电话交换网络的设计，实现了在尽可能减少通讯损失的前提下满足通讯量。在通讯能力不足，电话请求被拒绝而遗失的前提假设下，系统损失的程度是由服务等级来量化的。即使这些系统的承载能力是有限的，拥挤的通讯系统会利用备选路径来分流电话请求。

然而，在公共电话交换网络中应用排队理论使得该系统在通讯能力缺乏时为其顾客排列队伍。这就意味着如果通讯载荷量等级超越了现有能力，顾客的电话请求将不会丢失；相反，他们的请求将会等待被服务。在下一代操作员系统中，此方法将为顾客排队。

泊松分布和指数分布的作用

排队购物可视为一种泊松分布（Poisson distribution），到商店购物，若上门顾客是完全随机，假设每分钟平均来客数是A，则在特定分钟期间有N位顾客上门的概率可以下列公式表示：

P(X=N)={\frac {e^{-A}A^{N}}{N!}}

。

所以若平均每分钟有1位顾客上门，在特定某分钟同时有4位顾客购物的排队等候（Queueing）概率约0.02，或者是2%。^[6]

数学方法的局限性

经典的排队理论由于数学上的限制性而难以塑造所有真实世界的情况。这局限的产生是由于这理论的潜在设想不常包含在真实世界。

举一个例，数学模型经常假设有无限个顾客或队伍的容量或无限制的抵达间隔或服务时间，但非常明显地，这些限制不一定在真实世界中存在。很多的时候，虽然这些限制真的存在，它们却可以安全地被忽略，因为真实世界和理论之间的分别并不在统计学上有意义，其原因是发生那么边缘的情况的概率跟期望的正常情况相差很远。所以理论的解答可以把棘手的或不充分的情报证明到有用。

参看

注释

^ Sundarapandian, V. 7. Queueing Theory. Probability, Statistics and Queueing Theory. PHI Learning. 2009. ISBN 8120338448.
^ Lawrence W. Dowdy, Virgilio A.F. Almeida, Daniel A. Menasce. Performance by Design: Computer Capacity Planning By Example: 480. 2004-01-15 [2014-02-07]. （原始内容存档于2016-05-06）.
^ Schlechter, Kira. Hershey Medical Center to open redesigned emergency room. The Patriot-News. March 2, 2009 [2014-02-07]. （原始内容存档于2016-06-29）.
^ Mayhew, Les; Smith, David. Using queuing theory to analyse completion times in accident and emergency departments in the light of the Government 4-hour target. Bayes Business School (formerly Cass). December 2006 [2008-05-20]. ISBN 978-1-905752-06-5. （原始内容存档于2021-09-07）.
^ 存档副本. [2010-05-16]. （原始内容存档于2008-10-07）.
^ [Rob Eastaway, Jeremy Wyndham 为什么公车一次来3班? 脸谱出版]

参考文献

Kleinrock,L.,Queueing Systems,Vol.1:Theory,1975;Vol.2:Computer Applications,Wiley-Interscience,1976.

延伸阅读

Gross, Donald; Carl M. Harris. Fundamentals of Queueing Theory. Wiley. 1998. ISBN 0-471-32812-X.
Deitel, Harvey M. An introduction to operating systems revisited first. Addison-Wesley. 1984: 673 [1982]. ISBN 0-201-14502-2. chap.15, pp. 380–412
Lazowska, Edward D.; John Zahorjan, G. Scott Graham, Kenneth C. Sevcik. Quantitative System Performance: Computer System Analysis Using Queueing Network Models. Prentice-Hall, Inc. 1984 [2012-11-28]. ISBN 0-13-746975-6. （原始内容存档于2012-02-06）.
Zukerman, Moshe. Introduction to Queueing Theory and Stochastic Teletraffic Models (PDF). [2012-11-28]. （原始内容存档 (PDF)于2016-08-11）.

外部链接

Queueing Theory Basics (英文)
Queueing theory calculator （页面存档备份，存于互联网档案馆）
Virtamo's Queueing Theory Course （页面存档备份，存于互联网档案馆）
Myron Hlynka's Queueing Theory Page （页面存档备份，存于互联网档案馆）
Java Modelling Tools - A GPL suite of queueing theory tools （页面存档备份，存于互联网档案馆）
Queueing Package for GNU Octave （页面存档备份，存于互联网档案馆）
A free online tool to solve some classical queueing systems

[sun-1] Sundarapandian, V. 7. Queueing Theory. Probability, Statistics and Queueing Theory. PHI Learning. 2009. ISBN 8120338448.

[2] Lawrence W. Dowdy, Virgilio A.F. Almeida, Daniel A. Menasce. Performance by Design: Computer Capacity Planning By Example: 480. 2004-01-15 [2014-02-07]. （原始内容存档于2016-05-06）.

[3] Schlechter, Kira. Hershey Medical Center to open redesigned emergency room. The Patriot-News. March 2, 2009 [2014-02-07]. （原始内容存档于2016-06-29）.

[4] Mayhew, Les; Smith, David. Using queuing theory to analyse completion times in accident and emergency departments in the light of the Government 4-hour target. Bayes Business School (formerly Cass). December 2006 [2008-05-20]. ISBN 978-1-905752-06-5. （原始内容存档于2021-09-07）.

[5] 存档副本. [2010-05-16]. （原始内容存档于2008-10-07）.

[6] [Rob Eastaway, Jeremy Wyndham 为什么公车一次来3班? 脸谱出版]

[1]

[2]

[3]

[4]

[5]

[6]

查论编概率论：随机过程
离散时间（英语：Discrete-time stochastic process）	伯努利过程分支过程中餐馆过程高尔顿-沃特森过程（英语：Galton–Watson process）独立同分布马尔可夫链莫兰过程（英语：Moran process）随机游走循环擦除随机游走（英语：Loop-erased）自避行走
连续时间	贝塞尔过程出生-死亡过程维纳过程/布朗运动布朗桥 Excursion（英语：Brownian excursion）分数布朗运动（英语：Fractional Brownian motion）几何布朗运动 Meander（英语：Brownian meander）柯西过程（英语：Cauchy process） Contact process（英语：Contact process (mathematics)） Cox process（英语：科克斯过程） Diffusion process（英语：Diffusion process） Empirical process（英语：Empirical process）费勒过程（英语：Feller process）弗莱明-维奥过程（英语：Fleming–Viot process）伽马过程（英语：Gamma process）亨特过程（英语：Hunt process） Interacting particle system（英语：Interacting particle system）s 伊藤积分伊藤过程跳跃扩散（英语：Jump diffusion）跳跃过程莱维过程 Local time（英语：Local time (mathematics)）马尔可夫加过程（英语：Markov additive process）麦基恩-弗拉索夫过程（英语：McKean–Vlasov process）奥恩斯坦-乌伦贝克过程泊松过程复合泊松过程（英语：Compound Poisson process）非齐次泊松过程泊松点过程施拉姆-勒夫纳演进半鞅 Sigma-martingale（英语：Sigma-martingale） Stable process（英语：Stable process） Superprocess（英语：Superprocess） Telegraph process（英语：Telegraph process） Variance gamma process（英语：Variance gamma process）维纳过程 Wiener sausage（英语：Wiener sausage）
离散时间与连续时间	分支过程高斯过程隐马尔可夫模型（HMM）马尔可夫过程鞅鞅差序列（英语：Martingale difference sequence）局部鞅（英语：Local martingale） Sub- Super-（英语：Super-） Random dynamical system（英语：Random dynamical system） Regenerative process（英语：Regenerative process） Renewal process（英语：Renewal process）白噪声
场及其它	狄利克雷过程（英语：Dirichlet process）高斯随机场（英语：Gaussian random field）吉布斯测度（英语：Gibbs measure）霍普菲尔德神经网络易辛模型马尔可夫网络渗流理论皮特曼-约尔过程（英语：Pitman–Yor process）点过程 Cox（英语：Point process#Cox point process）泊松过程玻茨模型随机场随机图
时间序列模型	ARCH模型 ARIMA模型自回归模型 ARMA模型广义ARCH模型移动平均模型
金融模型	布莱克-德尔曼-托伊模型（英语：Black–Derman–Toy model）布莱克-卡拉辛斯基模型（英语：Black–Karasinski model）布莱克-舒尔斯模型陈模型 Constant elasticity of variance (CEV)（英语：Constant elasticity of variance model）科克斯-英格索尔-罗斯模型 (CIR)（英语：Cox–Ingersoll–Ross model） Garman–Kohlhagen（英语：Garman–Kohlhagen model） HJM框架赫斯顿模型（英语：Heston model） Ho–Lee（英语：Ho–Lee model）赫尔-怀特模型 LIBOR市场模型（英语：LIBOR market model） SABR volatility（英语：SABR volatility model）瓦西塞克模型（英语：Vasicek model）
精算学	Bühlmann（英语：Bühlmann model） Cramér–Lundberg（英语：Cramér–Lundberg model） Risk process（英语：Risk process） Sparre–Anderson（英语：Sparre–Anderson model）
排队论	Bulk（英语：Bulk queue） Fluid（英语：Fluid queue） Generalized queueing network（英语：G-network） M/G/1（英语：M/G/1 queue） M/M/1 M/M/c（英语：M/M/c queue）
性质	右连左极函数 Continuous（英语：Continuous stochastic process） Continuous paths（英语：Sample-continuous process）遍历性 Exchangeable（英语：Exchangeable random variables） Feller-continuous（英语：Feller-continuous process） Gauss–Markov（英语：Gauss–Markov process）马尔可夫性质 Mixing（英语：Mixing (mathematics)） Piecewise deterministic（英语：Piecewise deterministic Markov process）可预测过程循序可测过程 Self-similar（英语：Self-similar process）平稳过程 Time-reversible（英语：Time reversibility）
极限定理	中心极限定理 Donsker's theorem（英语：Donsker's theorem） Doob's martingale convergence theorems（英语：Doob's martingale convergence theorems）遍历理论 Fisher–Tippett–Gnedenko theorem（英语：Fisher–Tippett–Gnedenko theorem） Large deviation principle（英语：Large deviation principle）大数定律重对数律 Maximal ergodic theorem（英语：Maximal ergodic theorem） Sanov's theorem（英语：Sanov's theorem）
不等式	Burkholder–Davis–Gundy（英语：Burkholder–Davis–Gundy inequalities） Doob's martingale（英语：Doob's martingale inequality） Kunita–Watanabe（英语：Kunita–Watanabe inequality）
工具	Cameron–Martin formula（英语：Cameron–Martin formula）随机变量的收敛 Doléans-Dade exponential（英语：Doléans-Dade exponential） Doob decomposition theorem（英语：Doob decomposition theorem） Doob–Meyer decomposition theorem（英语：Doob–Meyer decomposition theorem） Doob's optional stopping theorem（英语：Doob's optional stopping theorem） Dynkin's formula（英语：Dynkin's formula）费曼-卡茨公式右连左极函数 Girsanov theorem（英语：Girsanov theorem） Infinitesimal generator（英语：Infinitesimal generator (stochastic processes)）伊藤积分伊藤引理 Kolmogorov continuity theorem（英语：Kolmogorov continuity theorem） Kolmogorov extension theorem（英语：Kolmogorov extension theorem） Lévy–Prokhorov metric（英语：Lévy–Prokhorov metric） Malliavin calculus（英语：Malliavin calculus） Martingale representation theorem（英语：Martingale representation theorem） Optional stopping theorem（英语：Optional stopping theorem） Prohorov theorem（英语：Prohorov theorem）二次变差 Reflection principle（英语：Reflection principle (Wiener process)） Skorokhod integral（英语：Skorokhod integral） Skorokhod's representation theorem（英语：Skorokhod's representation theorem）右连左极函数 Snell envelope（英语：Snell envelope）随机微分方程 Tanaka（英语：Tanaka equation）停时随机积分 Uniform integrability（英语：Uniform integrability） Usual hypotheses（英语：Usual hypotheses）维纳空间 Classical（英语：Classical Wiener space） Abstract 漂移项
相关领域	精算学计量经济学遍历理论极值理论（EVT） Large deviations theory（英语：Large deviations theory）数理金融学数理统计学概率论排队论 Renewal theory（英语：Renewal theory） Ruin theory（英语：Ruin theory）统计学随机分析时间序列分析机器学习
分类

规范控制数据库
国际	FAST
各地	法国 BnF data 德国以色列美国日本捷克