等候理論

排队论（），或称排隊理論、随机服务系统理论，是研究服务系统中排队现象随机规律的学科。排队论作为数学运筹学的分支学科广泛应用于電信、交通工程、计算机网络、生产、运输、库存等各项资源共享的随机服务系统，
在现实中则可以指导工廠、商店、辦公室、醫院等公共设施的設計。

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

 历史与表示法 

 历史 

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

 表示法 
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位顧客上門的機率可以下列公式表示：
。
所以若平均每分鐘有1位顧客上門，在特定某分鐘同時有4位顧客購物的排隊等候（Queueing）機率約0.02，或者是2%。[Rob Eastaway, Jeremy Wyndham 為什麼公車一次來3班? 臉譜出版]

 数学方法的局限性 
经典的排队理论由于数学上的限制性而难以塑造所有真实世界的情况。這局限的產生是由於這理論的潛在設想不常包含在真實世界。

舉一個例，數學模型經常假設有無限個顧客或隊伍的容量或無限制的抵達間隔或服務時間，但非常明顯地，這些限制不一定在真實世界中存在。很多的時候，雖然這些限制真的存在，它們卻可以安全地被忽略，因為真實世界和理論之間的分別並不在統計學上有意義，其原因是發生那麼邊緣的情況的機率跟期望的正常情況相差很遠。所以理論的解答可以把棘手的或不充分的情報證明到有用。

 参看 
 埃朗單位（Erlang unit）
 马尔可夫链
 吞吐量
 工业工程学
 系统工程
 交通堵塞
 运筹学

註釋

參考文獻

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

延伸閱讀


  chap.15, pp. 380–412



 外部链接 

 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


Category:随机过程
Category:運籌學
Category:形式科學
Category:网络性能
Category:马尔可夫模型
Category:马尔可夫过程