65.9K
CodeProject 正在变化。 阅读更多。
Home

掌控你的服务系统：排队论实用入门

Kerry Cakebread
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.44/5 (9投票s)

2010 年 7 月 3 日

CPOL

6分钟阅读

viewsIcon

26033

downloadIcon

421

提供排队论的背景和概述，以及一个实现测量功能的类库

引言

去过医生办公室或银行的人都曾有过排队等待的经历。事实上，排队是日常生活的一部分。在某种程度上，它们反映了现代社会的公平性。顾客排队购买商品，来电者等待“下一位空闲的接线员”，库存堆积等待处理或出售，而互联网浏览器则等待 Web 服务器和路由器处理它们的请求。

当资源过于昂贵而无法实现个体化时，一种合理的做法就是轮流使用。然而，在大多数情况下，只有当资源前的队伍过长，或者由于浪费我们的时间（“您的来电对我们很重要，请保持通话”）或金钱（例如，以过多的库存或人员成本的形式）而给我们带来不便时，我们才会注意到它们。

许多组织已经积极地掌控了他们的服务系统，并刻意管理他们的队列，以提供最佳的服务水平，即满足或超出客户期望，但又不产生不必要的成本（例如，人员过多）。即使在到达人数和每位顾客的系统停留时间存在差异的情况下，也可以计算出表征顾客等待服务体验的指标，并帮助系统管理器最大限度地减少在劳动力或资本设备上的投资。分析这些指标的组织通常能够更快地应对变化。此外，在服务水平决策方面，它们拥有合理的可用信息，例如，当预算限制导致高层管理人员建议目标（即降低）服务水平时。同样，在快速增长的情况下，它们也拥有更准确的预期。

队列建模最有用的一项特性是，它能够优雅地从小型（子）系统扩展到包含许多较小系统的更大系统。值得注意的是，存在一个分析队列网络的框架，每个网络都有其自身的特性，这些网络共同构成一个更大的系统。

在本文中，您将看到一个关于顾客队列如何成为消除浪费和提供客户价值的极其重要的工具的模型。此外，我还将提供并讨论一个实用程序应用程序的示例源代码和一个 .NET 类，您可以使用它们来完成许多用于优化基本队列系统的分析。

背景

排队论的起源可以追溯到 Erlang 于 1909 年发表的一篇论文，尽管直到 David Kendall 于 1953 年的研究才出现了这类问题的常用表示法。1961 年，通过 John Little 在 MIT 的工作，数学分析获得了进一步的洞察，并被归纳为“Little 定律”。

该理论最初是为了解决电话接线员在电话客户想打电话时的可用性问题而开发的。尽管接线员花费几秒钟就可以建立连接，但新的请求通常比它们能被处理的速度更快地到达交换台，导致拨号尝试失败。因此，电话网络需要越来越多的接线员值班来处理流量。然而，随着排队系统和分析的出现，交换台可以将来电者放入队列，并在接线员空闲时尽快满足他们的拨号请求。然后，电话公司可以决定适当的服务水平，并相应地配备交换台人员。尽管今天的电路是数字化的，队列是虚拟的，但同样的拨号模式仍然在使用。

然而，尽管这些模型看起来已经很成熟，并且在运营和供应链管理中得到了广泛应用，但许多 IT 专业人员对建模这些队列仍然不熟悉。

排队系统由其输入群体（等待的顾客队列）、服务设施（员工、机器等）以及指定顾客服务顺序的优先级规则（先进先出、后进先出、时间切片等）来表征。排队分析使用一种称为马尔可夫链的特定形式的状态方程来对每个状态下的系统进行建模。进入这些系统的传入流量通过泊松分布进行建模，并遵循 Erlang 的排队论假设。

  • 到达和离开是随机且独立的事件。
  • 系统内的概率不会改变。
  • 所有传入流量都可以路由到网络中的任何其他服务器。
  • 拥塞在服务器空闲后立即得到清除。

当然，在现实中，这些假设（以及模型中隐含的其他假设）并不总是 100% 成立，但现实世界与理论之间的差异通常可以安全地忽略，因为它们在统计上并不显著。在不属于数学排队论范畴的情况下，已经开发了替代的分析方法（例如模拟）。

在排队论中，为了简化所涉及的数学，使用具有无记忆特性的概率分布会很方便。因此，排队模型经常通过使用指数分布来构建为泊松过程。

通常，一个队列由两个字母和一个数字来描述，该数字指定了到达时间的分布、服务过程的分布以及系统中的服务器数量，尽管也可以附加其他代码来指定附加特性。最常见的到达和服务的分布类型是马尔可夫（M，表示指数分布和泊松过程）、确定性（D，表示恒定的到达或服务时间）或通用（G）。因此，一个具有马尔可夫到达时间、确定性服务时间和单个服务器的队列将用缩写 M/D/1 来描述。

使用代码

本文附带了一个 .NET 项目的示例源代码，该项目可以完成许多用于优化基本队列系统的分析。这个队列库可以被帮助台活动报告调用，包含在决策支持应用程序中，或者简单地与附带的演示界面一起使用来进行实验。

该类支持单服务器和多服务器模型（通过传递给每个方法的 `servers` 参数确定）。它还支持有限源模型，即预计进入系统的客户数量是已知的（很少见）。这些函数根据传递给大多数方法的 `numberOfCustomers` 参数来确定是否使用有限源模型。

`Queue` 类中包含的公共方法有：

  • `avgSystemUtilization()` - 系统的平均利用率（它有多忙）
  • `probNCustomersInSystem()` - 在任何给定时间系统中有 N 个顾客的概率
  • `probZeroCustomersInSystem()` - 在任何给定时间系统为空的概率
  • `avgCustomersInSystem()` - 在任何给定时间系统中顾客的平均数量
  • `avgCustomerInLine()` - 在任何给定时间等待在队伍中（尚未服务）的顾客的平均数量
  • `avgTimeInSystem()` - 顾客完成整个系统（包括服务时间）所需的平均时间
  • `avgTimeInLine()` - 到达队伍最前面所需的平均时间

这些方法可以这样调用，例如：

Double avgCustsInLine = Queue.avgCustomersInLine(arrivalRate, 
                        serviceRate, servers, numberOfCustomers);

此调用会调用 `avgCustomersInLine()` 函数，如下所示：

public static double avgCustomersInLine(double arrivalRate, 
       double serviceRate, int servers, int numberOfCustomers)
{
    if (servers <= 0)
        throw new Exception("You must pass in a positive number of servers");
    //terminate with an error if queue is infeasible
    if (arrivalRate >= (servers * serviceRate))
    {
        throw new Exception("Infeasible queue");
    }
    if (numberOfCustomers > 0)
    {//finite source model
        double probZeroInSys = probZeroCustomersInSystem(arrivalRate, 
                               serviceRate, servers, numberOfCustomers);
        return numberOfCustomers - (((arrivalRate + serviceRate) / 
                                      arrivalRate) * (1 - probZeroInSys));
    }
    else
    {
        double avgUtilization = avgSystemUtilization(arrivalRate, 
                                serviceRate, servers, numberOfCustomers);
        if (servers == 1)
        {//single server model
            double avgCustInSys = avgCustomersInSystem(arrivalRate, 
                                  serviceRate, servers, numberOfCustomers);
            return avgUtilization * avgCustInSys;
        }
        else
        {//multiple server model
            double probZeroInSys = probZeroCustomersInSystem(arrivalRate, 
                                   serviceRate, servers, numberOfCustomers);
            return (probZeroInSys * Math.Pow((arrivalRate / serviceRate), 
                    servers) * avgUtilization) /
                (fact(servers) * Math.Pow(1 - avgUtilization, 2));
        }
    }
}

精选参考文献和扩展阅读

  1. Cooper, Robert B. *Introduction to Queueing Theory*, 2nd ed. New York: Elsevier-North Holland, 1980.
  2. Little, J.D.C. "A Proof for the Queueing Formula: L=lambda*W." *Operations Research*, vol. 9, (1961), pp 383-387.
  3. Krajewski and Ritzman, Operations Management Processes and Value Chains 7th edition (2004), Pearson Prentice Hall, Upper Saddle River, NJ, pp 535-581
  4. Moore, P.M. Queues, Inventories and Maintenance. New York: John Wiley & Sons, 1958.
  5. Saaty, T.L. Elements of Queueing Theory with Applications. New York: McGraw-Hill, 1961.
© . All rights reserved.