排队论
 | 此条目需要精通或熟悉相关主题的编者参与及协助编辑。 (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
