等候理論
维基百科,自由的百科全书
排队论(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表示确定值。
[编辑] 排队论在电话学中的应用
[编辑] 排队网络
[编辑] 泊松分布和指数分布的作用
[编辑] 数学方法的局限性
经典的排队理论由于数学上的限制性而难以塑造所有真实世界的情况。這局限的產生是由於這理論的潛在設想不常包含在真實世界。
舉一個例,數學模型經常假設有無限個顧客或隊伍的容量或無限制的抵達間隔或服務時間,但非常明顯地,這些限制不一定在真實世界中存在。很多的時候,雖然這些限制真的存在,它們卻可以安全地被忽略,因為真實世界和理論之間的分別並不在統計學上有意義,其原因是發生那麼邊緣的情況的機率跟期望的正常情況相差很遠。所以理論的解答可以把棘手的或不充分的情報證明到有用。
[编辑] 参看
[编辑] 参考文献
Kleinrock,L.,Queueing Systems,Vol.1:Theory,1975;Vol.2:Computer Applications,Wiley-Interscience,1976.