排队论

历史

厄朗（英语：Agner Krarup Erlang）（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位顾客上门的概率可以下列公式表示：

${\displaystyle P(X=N)={\frac {e^{-A}A^{N}}{N!}}}$ 。

所以若平均每分钟有1位顾客上门，在特定某分钟同时有4位顾客购物的排队等候（Queueing）概率约0.02，或者是2%。^[6]

经典的排队理论由于数学上的限制性而难以塑造所有真实世界的情况。这局限的产生是由于这理论的潜在设想不常包含在真实世界。

举一个例，数学模型经常假设有无限个顾客或队伍的容量或无限制的抵达间隔或服务时间，但非常明显地，这些限制不一定在真实世界中存在。很多的时候，虽然这些限制真的存在，它们却可以安全地被忽略，因为真实世界和理论之间的分别并不在统计学上有意义，其原因是发生那么边缘的情况的概率跟期望的正常情况相差很远。所以理论的解答可以把棘手的或不充分的情报证明到有用。

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