Automated decision-making for dynamic task assignment at scale

📄 arXiv: 2504.19933v1 📥 PDF

作者: Riccardo Lo Bianco, Willem van Jaarsveld, Jeroen Middelhuis, Luca Begnardi, Remco Dijkman

分类: cs.AI, cs.LG, math.OC

发布日期: 2025-04-28

💡 一句话要点

提出基于图结构和定制奖励函数的DRL决策支持系统，解决大规模动态任务分配问题。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 动态任务分配 深度强化学习 图神经网络 决策支持系统 过程挖掘

📋 核心要点

  1. 现有DTAP的DRL方法主要集中于小规模合成数据，难以应对真实世界大规模场景的复杂性。
  2. 提出一种基于图结构的DRL代理，结合定制的奖励函数，旨在最小化任务的平均周期时间。
  3. 实验结果表明，该方法在真实数据集上表现优异，能够匹配或超越现有最佳基线方法，并具备良好的泛化能力。

📝 摘要（中文）

本文研究动态任务分配问题（DTAP），其中每个任务是由随机活动序列组成的案例。此DTAP变体涉及决定将哪个员工分配给哪个活动，以尽可能快地处理请求。近年来，深度强化学习（DRL）已成为解决此DTAP变体的有前途的工具，但大多数研究仅限于解决小规模的合成问题，忽略了实际用例带来的挑战。为了弥合这一差距，本文提出了一种基于DRL的决策支持系统（DSS），用于实际规模的DTAP。为此，我们引入了一个具有两个新颖元素的DRL代理：一个用于观察和行动的图结构，可以有效地表示任何DTAP；以及一个奖励函数，该函数可证明等同于最小化任务平均周期时间的目标。这些新颖性的结合使代理能够为实际规模的DTAP学习有效且可泛化的分配策略。所提出的DSS在五个DTAP实例上进行了评估，这些实例的参数是通过过程挖掘从真实世界的日志中提取的。实验评估表明，所提出的DRL代理在所有DTAP实例中都与最佳基线相匹配或优于最佳基线，并且可以在不同的时间范围内和跨实例进行泛化。

🔬 方法详解

问题定义：论文旨在解决大规模动态任务分配问题（DTAP），其中每个任务包含一系列随机活动。现有方法，特别是基于DRL的方法，通常在小规模合成数据集上进行评估，无法有效处理真实世界大规模DTAP的复杂性和挑战，例如状态空间巨大、动作空间复杂等。

核心思路：论文的核心思路是利用深度强化学习（DRL）来学习任务分配策略，并通过引入图结构来表示DTAP的状态和动作，从而有效地处理大规模问题。此外，设计了一个与最小化平均周期时间目标等价的奖励函数，引导DRL代理学习更优的分配策略。

技术框架：该决策支持系统（DSS）的核心是一个DRL代理。该代理接收DTAP的状态作为输入，状态信息通过图结构进行编码。代理输出一个动作，表示将哪个员工分配给哪个活动。环境根据动作更新状态，并返回奖励。代理通过与环境的交互不断学习，优化分配策略。整体流程包括状态表示、动作选择、奖励计算和策略更新等环节。

关键创新：论文的关键创新在于两个方面：一是引入了图结构来表示DTAP的状态和动作，这使得代理能够有效地处理大规模问题，并具备更好的泛化能力。二是设计了一个与最小化平均周期时间目标等价的奖励函数，这使得代理能够直接优化问题的目标，而无需手动设计复杂的启发式规则。

关键设计：图结构用于表示员工、活动和任务之间的关系，节点表示员工和活动，边表示分配关系。奖励函数设计为负的平均周期时间，鼓励代理尽快完成任务。具体的网络结构和参数设置在论文中未详细说明，属于未知信息。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，所提出的DRL代理在五个从真实世界日志中提取参数的DTAP实例上进行了评估，结果表明该方法在所有实例中均能匹配或优于最佳基线。此外，该方法在不同的时间范围内和跨实例表现出良好的泛化能力，证明了其在实际应用中的潜力。

🎯 应用场景

该研究成果可应用于各种需要动态任务分配的场景，例如：呼叫中心座席分配、物流配送员调度、云服务器资源分配、生产线任务调度等。通过优化任务分配，可以显著提高资源利用率，缩短任务周期时间，降低运营成本，提升服务质量。

📄 摘要（原文）

The Dynamic Task Assignment Problem (DTAP) concerns matching resources to tasks in real time while minimizing some objectives, like resource costs or task cycle time. In this work, we consider a DTAP variant where every task is a case composed of a stochastic sequence of activities. The DTAP, in this case, involves the decision of which employee to assign to which activity to process requests as quickly as possible. In recent years, Deep Reinforcement Learning (DRL) has emerged as a promising tool for tackling this DTAP variant, but most research is limited to solving small-scale, synthetic problems, neglecting the challenges posed by real-world use cases. To bridge this gap, this work proposes a DRL-based Decision Support System (DSS) for real-world scale DTAPS. To this end, we introduce a DRL agent with two novel elements: a graph structure for observations and actions that can effectively represent any DTAP and a reward function that is provably equivalent to the objective of minimizing the average cycle time of tasks. The combination of these two novelties allows the agent to learn effective and generalizable assignment policies for real-world scale DTAPs. The proposed DSS is evaluated on five DTAP instances whose parameters are extracted from real-world logs through process mining. The experimental evaluation shows how the proposed DRL agent matches or outperforms the best baseline in all DTAP instances and generalizes on different time horizons and across instances.