等候理論
 | 此條目需要精通或熟悉相关主题的编者参与及协助编辑。 (2015年12月14日) |
排队论（英語：queueing theory），或称排隊理論、随机服务系统理论，是研究服务系统中排队现象随机规律的学科[1]。排队论作为数学运筹学的分支学科广泛应用于電信，交通工程，计算机网络、生产、运输、库存等各项资源共享的随机服务系统，[2] 和工廠，商店，辦公室和醫院的設計。[3][4]
排队论研究的内容有3个方面：统计推断，根据资料建立模型；系统的性态，即和排队有关的数量指标的概率规律性；系统的最佳化问题。其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。
历史与表示法
[编辑]历史
[编辑]厄朗（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位顧客上門的機率可以下列公式表示：
- 。
所以若平均每分鐘有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
