非平稳服务系统中的资源调度

挑战

作者：萨米拉·希尔扎伊和杰弗里·史密斯（奥本大学）

本文曾在2018年冬季仿真会议上发表。

我们专注于一个顾客到达时间不稳定的服务系统，目标是制定一套服务人员配置方案，确保顾客到达时不会遇到长时间或难以预测的排队情况。机场售票柜台就是一个典型的例子。虽然旅客到达时间不稳定，但旅客通常不希望长时间排队办理登机手续。此外，不可预测性在这些环境中也是一个重要问题，因为它常常迫使旅客“以防万一”提前到达。遗憾的是，我们很少能准确了解顾客到达流程的具体情况，只能通过观察样本来制定人员配置策略。我们通过案例研究表明，结合专门的输入分析工具进行仿真，可以有效地在这些环境中制定合理的人员配置策略。

介绍

我们的目标是优化机场值机柜台等服务系统的运行，重点关注人员配置水平，以最大程度地控制顾客的等待时间。我们假设旅客到达是非平稳的，但我们并不了解到达过程的具体形式或参数。显然，如果服务速率远大于最大到达速率，顾客通常只需等待很短的时间，但这种产能过剩会造成资源成本高昂。虽然预期排队时间很重要，但我们更关注排队时间的可预测性/方差，正如Smith和Nelson（2015）所述。我们的目标是确定一种资源调度方案，使得在到达量非平稳的情况下，等待时间看起来几乎是平稳的。

输入分析可以说是大多数模拟研究中最昂贵的步骤之一，也是模拟成功的关键（Law 2009）。输入建模的一个重要步骤是评估数据是否独立同分布（IID）。虽然在对平稳随机过程建模时这很简单，但当随机过程遵循非平稳模式，其概率分布或其参数随时间变化时，评估就变得更加困难（Ansari et al. 2014）。他们提出了输入分析直方图和速率（HistoRIA）作为辅助输入建模的工具。Smith 和 Nelson（2015）使用时间段法来估计到达机场值机区排队的顾客的虚拟等待时间，这些顾客的到达数据具有非平稳性。他们发现，时间段内的平均等待时间比总体平均等待时间更能反映单个顾客的实际情况。影响等待时间的一个重要因素是每个时间段内分配的服务员数量。如果我们能够准确确定这些数量，就能显著提升顾客满意度。很明显，当我们拥有无限数量的服务器时，等待时间最短，但拥有无限服务器的成本太高，我们希望降低使用它们的成本。

在本案例研究中，我们重点关注在满足客户满意度约束的前提下，如何调度服务器数量以实现成本最小化。在相关研究中，Feldman等人（2008）开发了一种确定呼叫中心合适人员配置水平的方法，旨在实现目标时间稳定性能，他们假设到达率函数为正弦函数𝜆(𝑡)。Jennings等人（1996）考虑了一个具有一般非平稳到达和服务时间过程的多服务器系统。他们开发了一种基于时变正态分布的近似程序，其中均值和方差由无限服务器近似确定。Green等人（2007）回顾了排队论中用于设定具有时变客户需求的服务系统中人员配置要求的方法。他们展示了如何将平稳排队模型应用于非平稳环境。根据目标服务质量和服务时间的不同，他们讨论了应该使用哪种方法以及如何进行修改。 Whitt (2007) 探讨了应对呼叫中心时变需求并设定人员配置水平的方法，他阐述了每种方法的适用时机和原因，以及失效时的应对措施。Izady 等人 (2011) 尝试在存在时变需求、多种患者类型和资源共享等复杂因素的情况下，设定最低医疗人员配置水平以减少患者的等待时间。他们提出的人员配置算法依赖于无限服务器网络来计算资源随时间变化的负载，并强调了其在模拟多种客户类型等复杂情况方面的能力。这些文章假设到达率服从预定的分布，即正弦到达率函数，但我们这里只有一组样本数据可供分析，并不了解过程特征。此外，他们使用了一些近似方法来获得合适的资源调度，例如正态近似和延迟概率近似，这些估计受到参数大小的影响，但本文我们感兴趣的是减少对过程和系统特性的限制，并通过在仿真软件中进行实验，采用更紧密的假设来优化人员配备水平，使模型更加现实，并观察实际的稳定等待时间。

解决方案

初始模型

我们的基本模型与 Smith 和 Nelson (2015) 使用的模型类似，都采用单服务器设计，具有非平稳的到达过程和随时间变化的代理容量。主要区别在于，他们使用该模型来测量乘客在系统中的停留时间，而我们使用该模型来优化设施人员配备水平，以便到达的乘客能够更好地预测等待时间。

到达数据集的输入分析

我们首先使用机场值机柜台连续5天的旅客到达数据。通常情况下，我们无法确定该数据集的平稳性类型。在某些情况下，数据在会话间、月间、周间、日间等尺度上是平稳的。我们使用 HistoRIA 工具（Ansari 等人，2014）来描述样本到达数据的特征。这是一个图形化工具，可以帮助用户评估过程随时间变化的平稳性。为了简化初始工作，我们假设数据在日尺度上是平稳的，并且可以将数据视为包含“普通一天”的5个观测值。

该工具以每日所有乘客的到达间隔作为输入，计算出到达间隔时间后，将其转换为相应的时间戳。利用这些时间戳，该工具输出 HistoRIA 图。绘制 HistoRIA 图时，我们需要确定时间段的大小，即一天被划分成多少个较小的间隔。这些时间段的长度至关重要，因为它们必须足够短，以确保每个间隔内的到达乘客所承受的系统负载基本相同；同时又要足够长，以确保几乎可以肯定每个间隔内都有乘客到达（Smith 和 Nelson，2015）。此外，我们还需要确定研究天数，在本例中为五天，并考虑一天的小时数。图 1 显示了给定数据集的两个 HistoRIA 图示例。在第一个 HistoRIA 图中，每个时间段代表一小时；在第二个图中，每个时间段代表半小时。因此，分别有 24 个和 48 个时间段。在每个时间段内，灰色区域代表估计的到达率 (𝜆(𝑡))。如图所示，每小时时间段的平均到达率几乎等于相应 30 分钟时间段的平均到达率，因此对于该数据集，选择 1 小时作为时间段是合理的。我们将 1 小时时间段内的估计到达率作为 Simio 中机场值机模型的输入。

如上所述，我们的目标是确定服务器数量随时间变化的函数关系。我们考虑的是一个旅客到达量非平稳的机场值机系统，并从机场管理者和旅客两个角度分析该系统，从而在最佳人员配置水平下，确保双方都能获得满意的服务。如果没有服务器数量限制，系统中就不会出现等待时间，但这几乎肯定会造成容量浪费，因为旅客到达量是随机且非平稳的。图 2 展示了在服务器容量无限大假设下，模型一次运行的动态状态图。该图显示了模拟时间内队列中的旅客数量 (NIQ) 和系统总停留时间 (TIS)。队列中没有旅客，平均排队时间为零（在模拟时间内，TIQ 和 NIQ 均保持为零），并且按小时划分的平均系统停留时间几乎等于平均服务时间 3 分钟——这与我们的预期完全一致。然而，对于旅客而言，无限的服务器容量并不现实。

图 1：乘客间隔数据集的 HistoRIA 图。

图 2：无服务器容量限制时模型性能指标的状态图。

问题描述

从客户服务的角度来看，最佳系统是拥有大量服务器，从而避免顾客等待。然而，从成本角度来看，这通常并不现实。我们的目标是在尽可能减少顾客等待时间的前提下，最大限度地降低服务器使用成本。顾客希望在到达服务系统之前能够预估排队等待时间，也就是说，等待时间是可预测的。需要注意的是，缩短排队时间和预测排队时间是两个不同的目标，而我们这里关注的是可预测性。由于我们遇到的是非平稳的输入数据，且缺乏关于精确分布函数的信息，因此人员配置调度问题并非易事。顾客希望知道何时出门才能赶上航班。在那篇论文中，他们提出了一种确定乘客实际等待时间（TIS）的方法，用于虚拟等待时间的估算。在这里，我们将从顾客和机场管理两个角度来审视这个问题。机场管理方希望降低资源使用成本并提高客户服务水平，而顾客则希望减少值机排队的等待时间，并希望能够预测等待时间。我们将这个问题视为一个优化模型。该模型由下式给出

须遵守以下规定：

其中，c 为单位资源成本，s(t) 为时间 t 分配的资源单位数量（即调度方案），TIQ(t) 为时间 t 的排队时间，a 和 b 分别为与等待时间和服务水平相关的常数。例如，如果在机场值机柜台，顾客的 TIQ 小于 15 分钟的概率超过 90%，则我们假设顾客会感到满意。目标函数是最小化资源使用成本，决策变量由 s(t) 决定，即时间 t 的人员配置水平，约束条件是服务水平，我们通过 s(t) 来控制它。虽然到达数据在一天中是非平稳的，但我们使用模型来确定代理资源调度方案，以产生近似平稳的 TIQ 过程——我们称之为实际平稳。

图 1 显示，顾客到达数量在一天中变化显著，到达率范围为每小时 716 人次，最低为 10 人次，最高为 726 人次。管理者的目标是利用资源调度来控制顾客的等待时间——将服务员数量设置为时间 t 的函数。由于系统类型的原因，我们暂不考虑顾客放弃的情况，但在一般服务系统中，顾客放弃的情况可能很重要。然而，在大多数此类系统中，如果我们按照顾客感觉系统几乎静止的方式来安排所需的人员配置，顾客放弃的概率将显著降低。虽然我们的模型是时间连续的，但我们通过将一天划分为若干个时长为一小时的较小时间段来离散地调整人员配置水平，并在评估顾客等待时间时考虑每个时间段内的平均等待时间。

实证方法

为了阐明在非平稳过程中合理配置人员的重要性，我们展示了一些未考虑顾客到达非平稳性的预定义资源调度示例。对于上一节输入分析中获得的到达数据，我们在 Simio 中运行了仿真模型。到达人数最多的时间段是第 12 个时间段，约为 726 位顾客。我们假设服务率为每小时 20 位顾客，因此，如果管理者决定全天保持恒定的人员配置水平，例如 35 位服务员，那么排队等待时间应该很短。在这种情况下，每小时时间段内顾客的平均排队时间最长约为 3 分 40 秒。为了获得每个时间段的平均等待时间，我们采用了与 Smith 和 Nelson (2015) 相同的方法，需要考虑按顾客到达时间排序的排队时间。我们将所需数据从 Simio 导出到外部程序进行更多统计计算，并绘制每个时间段的平均排队时间。更多信息请参见他们论文中的图 6。由于每个时间段都配备 35 台服务器会增加服务器的使用成本，而且在大多数时间段内服务器处于闲置状态，利用率很低，因此我们将这些固定的服务器数量分别减少到 25 台和 15 台，并观察其对每个时间段内客户平均等待时间的影响。结果如图 3 所示。

当我们将服务等级降低到 25 时，高峰时段乘客的平均排队时间增加到约 80 分钟。然而，存在大量时间段内没有乘客排队，这影响了资源的使用成本。在拥有 15 台服务器的情况下，系统将无法服务所有乘客。在模拟结束时，仍有乘客在排队，并且存在一个平均等待时间超过 400 分钟的时间段。由于系统不再稳定，模拟未显示第 16 个时间段之后的结果。

从以上讨论可以看出，在这样一个非恒定的到达流程中，全天保持恒定的资源水平是不切实际的。一天中的某些时段系统人员过剩，而另一些时段则人员不足。在人员过剩的时段，管理者需要为资源使用支付额外费用；而在人员不足的时段，乘客则需要长时间等待才能获得服务。因此，我们应该合理配置人员，以优化资源使用成本，同时尽可能地减少乘客的等待时间。

图 3：乘客平均排队时间（分钟）和排队人数图

讨论可能的解决方案

我们在 Simio 中使用了手动优化方法，同时考虑了每个时间段内的人员配置水平和乘客平均等待时间。正如我们之前提到的，无论一天中的哪个时间段，乘客都希望排队等待时间是可预测的。我们假设，如果乘客的平均排队等待时间少于 10 分钟，他们就会感到满意。考虑到这一限制，我们力求在每个时间段内实现最低的人员配置水平，从而最大限度地降低资源使用成本，这正是我们的目标函数。为了在 Simio 中计算每个时间段内乘客的平均等待时间，我们为定义的 24 个时间段分别定义了一个 Tally 统计量。我们需要告诉模型将每个实体的 TIQ 值存储在正确的 Tally 统计量中。我们需要计算乘客到达时间和服务开始前时间之间的差值，因此当实体在代理对象中进入“处理前”状态时，我们执行了一个附加流程。详情请参阅他们论文中的图 4。

在 Simio 中，为了追踪排队的平均小时数，我们设计了 24 个响应，并添加了记录代理全天利用率的响应。我们应用这些响应和工作安排表，为具有非平稳到达量的登记柜台模型找到最佳人员配置水平。

下面概述了设定人员配置水平的基本算法。

• 将观测到的到达时间数据输入 HistoRIA 工具，以确定时间段长度。
• 在 Simio 模型中，使用步骤 1 中获得的到达率，并按相关时间段进行计算。
• 根据到达率的初步估计，设定不同时间段的人员配备水平。
• 将目标最大等待时间 (a) 设置为 10 分钟，满足此约束的概率 (b) 设置为 0.9（或其他常数）。
• 使用 Simio 模型计算每个时间段的排队时间。
• 检查哪些时间段的资源水平满足第 2.2 节优化方程中的约束条件，对于满足约束条件的时间段，将资源水平降低一个单位，然后转到步骤 5。对于不满足约束条件的时间段，将人员配备水平增加一个单位，然后转到步骤 5。对于我们降低一个单位的人员配备水平，如果响应变差，则将其值恢复到之前的值并保持不变。
• 如果所有人员配置水平保持不变，则将解决方案标记为“良好”。

图 4 展示了仿真模型得到的服务级别调度方案。为了获得这些服务器分配方案，我们首先根据输入分析得到的到达率和平均服务时间分布进行了初始猜测。然后，我们运行仿真模型，观察这些服务级别是否满足我们的约束条件以及实现服务器数量最少、成本最低的目标（为此，如果发现某个时间段的平均排队时间过短，我们可以减少该时间段的服务器分配数量，并观察在新的服务器数量下平均等待时间的变化）。我们不断重复这种试错过程，直至找到最佳分配方案（即无法减少每个时间段的服务器数量，且等待时间仍然满足约束条件）。在这些资源水平下，服务器的日利用率约为 97.208%，最大平均等待时间出现在第 7 个时间段，约为 9.49 分钟，满足了我们对乘客满意度的约束条件。一天中，我们在 24 个时间段内总共使用了 316 个资源。如果我们在每个时间段内使用固定的 35 个服务器，那么在所有 24 个时间段内，我们将总共使用 840 个资源。在第 13 个时间段内，我们观察到平均排队时间约为 30.8 分钟，代理利用率约为 43.09%。

正如我们在问题模型约束中所确定的，我们需要设置参数 b 来表示乘客的满意度百分比，因此我们不能仅仅根据每个区间内的平均等待时间来决定人员配置水平。为此，我们在 Simio 中考虑了每个响应的 90% 分位数。我们对模型进行了 300 次重复测试，并使用 SMORE 图作为辅助决策工具。结果表明，人员配置水平与仅考虑各区间平均等待时间的情况略有不同。图 5 显示了我们办理登机手续模型中平均排队时间响应和更新后的人员配置水平的两个 SMORE 图（我们任意选择了这四个区间）。

根据更新后的人员配置，我们每天总共需要 329 个服务器工时，服务器利用率约为 93.65%。在这种方法下，我们知道至少在 90% 的情况下，乘客在所有时间段内的等待时间都不会超过 10 分钟。因此，如果我们想要观察等待时间少于 10 分钟的乘客比例超过 90%，那么在某些时间段内，我们需要比我们希望观察每个时间段内平均等待时间少于 10 分钟的情况更多的服务器。

为了从顾客的角度体验几乎恒定的排队时间，我们可以得出结论：当到达率剧烈变化时，我们无法观察到不同时间段内相同的平均排队时间，因为增加或减少一名服务员都会导致平均等待时间发生彻底改变，在某些时间段内，等待时间的变化幅度甚至可达6分钟左右。因此，我们可以确定平均排队时间的上限。在到达率较低的时间段内，即使只有一名服务员，排队时间也会很短，这对管理者和顾客来说都是好事，因此我们无需在这些时间段内过多关注人员配置。当乘客计划何时出门才能赶上航班时，他们可以预测平均等待时间。

图4：机场值机柜台的人员配置情况。

上述讨论为我们提供了每小时平均排队时间的良好信息，我们使用重复实验计算了置信区间。管理者仅根据平均排队等待时间来决定人员配置水平是存在风险的，因为平均排队等待时间存在波动，同样，顾客也不能仅依赖平均等待时间来安排出门时间。我们可以使用SMORE图中报告的置信区间半宽来计算这些平均排队时间的标准差，但这些标准差只能提供关于平均排队等待时间的信息，而无法提供个体排队等待时间的信息，因此风险规避型乘客不能仅根据平均排队等待时间来安排行程。我们采用了Smith和Nelson（2015）的方法来计算个体标准差。我们对模型进行了300次重复实验，并使用外部Python程序汇总这些文件中的数据以进行进一步分析。表1显示了这些分析的输出结果。对于每个时间段，我们都有乘客排队时间的平均值和标准差以及观测次数。如前所述，我们在第 12 个时间段内到达率最高，并且在此表中，该时间段内 300 次重复观测的总观测数最高，总共为 218160 次观测。

结果表明，在所有时间段内，使用Python中的模拟方法和统计方法计算出的平均等待时间相同，但模拟方法低估了标准差，乘客不能仅考虑平均等待时间的标准差来规划行程。当我们考虑排队时间的平均值时，我们可以确定乘客在实际平稳情况下的等待时间上限或范围。我们不能说平均值完全相同，但旅客可以预期在排队中会遇到预定的最大等待时间。

表1：模拟结果与计算结果在均值和标准差方面的比较。负差值表示模拟结果低估了标准差。

商业影响

结论

在实际的客户服务系统中，旅客到达过程通常是非平稳的。这种非平稳性会使资源规划变得困难，因为系统需要在客户服务和资源成本之间寻求平衡。当我们无法获得关于输入数据的精确信息时（这种情况通常不会发生），这个问题会更加棘手。本文通过一个案例研究来说明这种情况：一位经理需要在旅客到达量非平稳的机场值机柜台确定人员配置水平。我们开发并演示了一种基于仿真的方法，从经理和旅客的角度确定合适的人员配置水平，并将该问题定义为一个优化模型，以实现可预测的等待时间结果。有了这些结果，旅客就可以安排从家到机场的出发时间，而无需担心迟到；机场经理也可以确保以尽可能低的资源成本满足客户的需求。这项工作的下一步是推广该方法，使其适用于其他类似情况，并改进时间段选择/识别方法，以期实现该过程的自动化。

图 5：两个小时区间的 SMORE 图和人员配备水平表。