排隊論（queueing theory），或稱隨機服務系統理論，是數學運籌學的分支學科。它是研究服務系統中排隊現象隨機規律的學科。廣泛套用於計算機網路、生產、運輸、庫存等各項資源共享的隨機服務系統。
排隊論研究的內容有3個方面：統計推斷，根據資料建立模型；系統的性態，即和排隊有關的數量指標的機率規律性；系統的最佳化問題。其目的是正確設計和有效運行各個服務系統，使之發揮最佳效益。
歷史與表示法
厄朗（Agner Krarup Erlang）一個在丹麥哥本哈根電話局工作的工程師，研究人們打電話的行為模式，發展出人們需等待多久的公式，並於1909年出版了關於排隊理論的第一篇論文。
1953年大衛·坎達（David G. Kendall）提出了 A/B/C 等候表示法。
坎達等候表示法A/B/X/Y/Z
－A代表到達的規則；
－B代表服務規則，即指服務時間（相當於報文傳送時間）的長短服從什麼規律；
－X代表模型中平行的佇列（即服務通道或傳送信道）數目；
－Y代表系統容量限制；
－Z代表排隊紀律，即指採用先到先服務或其他的規則（如有優先等級）。
最基本的排隊模型：
·M/G/1模型
M/G/1表示到達規律是負指數機率密度，服務規則是任意的，而輸出信道只有一個。M也代表泊松過程（Poisson）。
·M/M/1模型
M/M/1模型實際上是M/G/1模型的一個特例，即報文傳送時間也是泊松過程，或者說，報文處理時間具有負指數的機率密度函式。
·M/D/1模型
在分組交換網中，若每個分組的長度是固定的，那么每個分組的傳送時間是相同的。這就要用到M/D/1模型。其中D表示確定值。
排隊論在電話學中的套用
公共電話交換網絡的設計，實現了在儘可能減少通訊損失的前提下滿足通訊量。在通訊能力不足，電話請求被拒絕而遺失的前提假設下，系統損失的程度是由服務等級來量化的。即使這些系統的承載能力是有限的，擁擠的通訊系統會利用備選路徑來分流電話請求。
然而，在公共電話交換網路中套用排隊理論使得該系統在通訊能力缺乏時為其顧客排列隊伍。這就意味著如果通訊載荷量等級超越了現有能力，顧客的電話請求將不會丟失；相反，他們的請求將會等待被服務。在下一代操作員系統中，此方法將為顧客排隊。
排隊網路
泊松分布和指數分布的作用
數學方法的局限性
經典的排隊理論由於數學上的限制性而難以塑造所有真實世界的情況。這局限的產生是由於這理論的潛在構想不常包含在真實世界。
舉一個例，數學模型經常假設有無限個顧客或隊伍的容量或無限制的抵達間隔或服務時間，但非常明顯地，這些限制不一定在真實世界中存在。很多的時候，雖然這些限制真的存在，它們卻可以安全地被忽略，因為真實世界和理論之間的分別並不在統計學上有意義，其原因是發生那么邊緣的情況的機率跟期望的正常情況相差很遠。所以理論的解答可以把棘手的或不充分的情報證明到有用。
參看
- 系統工程
- 運籌學
- 中國國家自然科學基金學科分類目錄/G
參考文獻
Kleinrock,L.,Queueing Systems,Vol.1:Theory,1975;Vol.2:Computer Applications,Wiley-Interscience,1976.
外部連結
- Myron Hlynka's Queueing Theory Page (英文)
- Queueing Theory Basics (英文)
- spreadsheet-based software to solve queueing models (英文)
