等候理論

排队论（queueing theory），或称随机服务系统理论、排隊理論，是数学运筹学的分支学科。它是研究服务系统中排队现象随机规律的学科。广泛应用于计算机网络、生产、运输、库存等各项资源共享的随机服务系统。

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

历史与表示法 [编辑]

历史 [编辑]

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

表示法 [编辑]

1953年，大衛·坎達（David G. Kendall）提出了 A/B/C 等候表示法。

A/B/C/X/Y/Z
- A-到达的规则；
- B-服务规则，即指服务时间（相当于报文发送时间）的长短服从什么规律；
- C-服务台个数
- X-模型中平行的队列（即服务通道或发送信道）数目；
- Y-系统容量限制；
- Z-排队纪律，即指采用先到先服务或其他的规则（如有优先等级）。

A與B的表示符號有以下類型

M 指數式
D 確定式
Ek 厄朗（Erlang）型，k為1,2,...
Hk 混和指數式
PH 相型
G 通用式

X的數值可為1到無限大

Y的數值可為1到無限大

Z的符號有以下類型

FCFS 先來先服務
LCFS 後來先服務
RSS 隨機選擇哪個先服務
PR 由優先權決定
GD 通用規則

排队论在电话学中的应用 [编辑]

公共电话交换网络的设计，实现了在尽可能减少通讯损失的前提下满足通讯量。在通讯能力不足，电话请求被拒绝而遗失的前提假设下，系统损失的程度是由服务等级来量化的。即使这些系统的承载能力是有限的，拥挤的通讯系统会利用备选路径来分流电话请求。

然而，在公共电话交换网络中应用排队理论使得该系统在通讯能力缺乏时为其顾客排列队伍。这就意味着如果通讯载荷量等级超越了现有能力，顾客的电话请求将不会丢失；相反，他们的请求将会等待被服务。在下一代操作员系统中，此方法将为顾客排队。

排队网络 [编辑]

泊松分布和指数分布的作用 [编辑]

数学方法的局限性 [编辑]

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

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

参看 [编辑]

註釋 [编辑]

^ http://pass.maths.org.uk/issue2/erlang/index.html

參考文獻 [编辑]

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. ISBN 0-13-746975-6.
Zukerman, Moshe. Introduction to Queueing Theory and Stochastic Teletraffic Models.

外部链接 [编辑]

[1] ttp://pass.maths.org.uk/issue2/erlang/index.html

[1]