等候理論

排队论（英語：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 德国以色列美国日本捷克