等候理論

排隊論（英語：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]