等候理論

等候理論（英語：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 德國以色列美國日本捷克