机器人加工自动化中调度问题的参数化复杂性

《European Journal of Operational Research》：Parameterized complexity of scheduling problems in robotic process automation

　　• 从调度角度研究机器人流程自动化（RPA）。
• RPA相关调度问题的参数化复杂性。
• 重点关注链式优先级、时间窗口和受限的处理时间。
• 与几个单机调度问题相关的新复杂性结果。

**引言**

随着市场竞争的加剧，公司在寻求保持竞争力的同时，面临着增加收入、降低成本和优化运营的压力。实现这些目标通常与提高公司业务流程的效率紧密相关。为了运营日常业务，大型公司开发了内部流程，用于处理与业务相关的活动（如发票处理、付款处理和客户关系管理），以及后台操作（如报告生成和人力资源活动，例如员工入职、薪资等）。这些工作流程过去由人类操作，但他们容易出错，不能24/7工作，并且扩展成本很高。因此，为了实现进一步增长和提高效率，公司被迫自动化其流程。

机器人流程自动化（RPA）（Wewerka & Reichert, 2020）正迅速成为通过模仿人类与软件的交互来自动化许多领域重复性、基于规则的任务的主要技术，从而提供更快的吞吐量、更高的准确性和不因人类疲劳而中断的连续运行。大型企业对RPA系统的采用不断增加，吸引了研究界的关注，研究人员开始探讨RPA的不同方面——经济视角（Aguirre和Rodriguez, 2017, Lamberton等人, 2017）、实际案例研究（Huang & Vasarhelyi, 2019）或数学优化（Séguin等人, 2021）。

一个典型的RPA系统包含一组被自动化的业务流程。每个流程对单个数据条目（也称为项目）进行操作，这些数据条目代表工作的基本单元。例如，一个流程可能是从供应商通过电子邮件发送的发票中提取数据，其中单个操作代表对PDF文件的光学字符识别并将提取的信息存储在数据库中。流程的执行可能受到公司内部规则、客户要求或技术限制所规定的时间窗口的约束。对数据条目的每个操作都由一个软件机器人执行，该机器人需要硬件资源来运行（在调度术语中称为机器），并且可能需要软件许可证。许可证的数量通常是有限的（Séguin等人, 2021），因为公司根据使用的机器人许可证数量向RPA供应商付款。要处理的项目存储在给定数量的队列中（k≥0），流程通常（但并非仅限于）以先进先出（FIFO）的方式检索项目。因此，项目的处理顺序受到链式优先级的约束，或者说是具有有限宽度w的一般有向无环图。项目j的处理时间表示为pj。通常，这些时间可能是任意的，但往往取决于它们出现的队列。

RPA系统由一组包含待处理项目的队列组成。一个流程访问一个队列Q，并花费pj个工作时间来处理项目j。我们识别两种主要类型的队列：（i）具有均匀工作负载的队列，意味着队列Q中的所有项目j具有相同的时间处理时间pj=pm（即相同类型的交易）；（ii）具有非均匀工作负载的队列，其中每个项目可能有不同的处理时间（即需要不同量的工作来处理项目）。

项目j在时间tj进入特定的队列，对应于释放时间。项目j的完成截止时间由服务水平协议（SLA）θ决定，即dj=tj+θ，对于某个θ值。θ值通常对所有项目或特定队列Q中的项目是常数。流程通过发布者-订阅者架构相互通信，即在一个队列中添加或消耗项目。最常见的流程类型是加载器和工作者流程。加载器流程在时间t将新的待处理项目（即为另一个流程生成工作负载）批量添加到队列中，这意味着批次中的所有项目具有相同的释放时间tj。如果在时间t只有来自单个批次的项目存在于队列Q中，则所有项目都具有相同的释放时间tQ。由于存在SLA θ，所有截止时间dj也等于一个常数tQ。此外，工作者流程订阅队列并按FIFO方式处理项目。因此，工作者流程处理项目的顺序受到链式优先级的约束。在RPA系统的背景下，传统上称为项目的术语今后将被称为作业，以使我们的术语与调度领域中常用的术语保持一致。

为此，我们采用了Graham等人（1979年）引入的标准三字段表示法π|ξ|ψ。在三字段表示法中，π代表调度环境，在本文中是指机器的数量：一台机器（1），或不相关的parallel machines的数量（m），或未指定的不相关parallel machines的数量（∞）。ξ字段表示作业特征。例如：优先级（prec）、链式关系（chains）、作业的释放时间（tj）、作业的截止时间（dj）、处理时间的规格（pj=1, …）。最后，ψ字段表示问题的目标。在本文中，我们考虑最小化完成时间Cmax（即为作业的最大完成时间），或者用*表示我们只对可行调度感兴趣。

在这些复杂系统中进行高效调度，仅依靠简单的在线规则来控制活动的执行是不够的。因此，我们希望作为一个明确定义的优化问题的结果来获取滚动时间范围内的调度。为了设计解决这些问题的高效算法，我们需要了解其各个方面的复杂性——即如果某些自然参数（如队列数量k、优先级宽度w、最大处理时间pm、不同处理时间的数量#pj或不同SLA的数量（即不同时间窗口的数量）(dj-tj)（详见第4节中的正式定义）被一个相对较小的常数所限制，则其（潜在的）可解性。这种更细致的复杂性表征，也称为参数化复杂性，可能提供所需的问题洞察。众所周知，在具有并行机器的调度环境中，即使是最简单的问题也往往是困难的。例如，问题tm|dj|*对于m=2台机器来说是弱NP难的，并且当m被参数化时是强W[1]-难的（van Bevern等人, 2017）。同样，tm2|chains(dj, tj)|Cmax即使时间窗口的底层区间图的路径宽度是常数也是NP难的（Hanen & Munier Kordon, 2024）（详见第4节中对路径宽度的定义）。即使没有释放时间和截止时间，对于m=2台机器和k=3个链的问题也是NP难的。

因此，在研究由RPA调度产生的问题的参数化复杂性时，我们主要关注表1中确定的RPA的关键参数的一类单机问题。然而，在第7节中，我们总结了复杂性结果，并制定了涉及并行机器设置的RPA调度设计策略。

**片段**

大多数关于RPA的工作集中在量化在不同行业中实施机器人自动化效果的经济研究上（Prucha, 2024, Ribeiro等人, 2020），但运筹学文献仍然很大程度上不发达。一个值得注意的例外是Séguin和Benkalai（2020年）、Séguin等人（2021年）的工作，他们开发了一个简化的数学模型，用于处理业务交易。他们提出了一个最小化机器人许可证成本的问题。

**贡献和概述**

我们研究了1|prec,tj,dj|*的参数化复杂性，并考虑了与RPA调度密切相关的参数。我们考虑了类似链式的优先级，并证明对于任何正整数p
**通用表示法**

对于非负整数a, b，我们定义[α, β]?{α, α+1, …, β-1, β}和[α]?[1, α]。特别地，[0]=0?。严格偏序是一对(υ, ?)，其中υ是有限的集合，且?是υ上的一个非自反且传递的二元关系。如果对于υ中的任意两个不同的j1, j2，都有j1?j2, j2?j1，则集合υ′?υ是?-独立的。定义(υ, ?)的宽度ω为υ中最大的?-独立集的大小。

**参数化复杂性**

参数化复杂性是一个旨在研究计算复杂性的框架。

**难度结果**

在本节中，我们展示了1|chains(dj, tj)|cmax在k（链的数量）参数化下的强xnlp难度。作为我们归约的副产品，我们还得到了组合参数#pj+pm+(dj-tj)的para-np难度。我们首先介绍我们将要归约的问题。

对于一个属于ω*的单词w，让w[i]表示w中位置i的字符（从1开始索引），|w|表示w的长度。设u1, u2∈ω*是两个单词。u1和u2的洗牌乘积，表示为u1?u2，是所有(u1|+u2|)!(u1|!)|u2|!的集合。

**ω参数化的xp算法**

我们从一个解决优先级关系由k个链组成的特殊情况的算法开始。注意，在这种情况下，k等于优先级关系的宽度ω。

**引理15**

问题1|chains(dj, tj)|cmax可以在nω2时间内解决，其中n是作业的数量。

**证明**

设υ是要调度的作业集合，|υ|=n，并设υ=γ1∪?∪γk是作业集划分成的k个链，即γi={xi1, xi2, …, xi|γi}，xi1?xi2???xi|γi|。我们使用动态规划来解决问题。对于ji∈{0, 1, 2…

**设计rpa调度算法的策略**

从设计调度算法的角度来看，rpa领域相对独特。乍一看，它可能类似于与计算集群相关的问题（khallouli & huang, 2022）。然而，集群通常由更广泛的用户群体使用，计算作业的多样性要大得多。相反，rpa与一个公司的业务流程相关，这些业务流程是明确定义的并且处于公司的控制之下。尽管如此，共同的目标是提高效率。

**结论**

我们从参数化复杂性的角度研究了与rpa相关的调度问题的复杂性理论方面。重点关注在rpa调度的真实世界实例中可以认为是小的参数，我们发现大多数情况都呈现para-np难度，即#cj, #dj, #pj, pm, (dj-tj)，以及1|chains(dj, tj)|cmax在k（链的数量）参数化下的强xnlp难度。另一方面，我们证明了当释放时间已知时，问题变为fpt。

**作者贡献声明**

michal dvo?ák：写作——审阅与编辑，撰写——初稿，方法论，调查，形式分析。
antonín novák：写作——审阅与编辑，撰写——初稿，验证，方法论，调查，形式分析。
p?emysl ??cha：写作——审阅与编辑，验证，监督，项目管理，调查，资金筹集，概念化。
du?an knop：写作——审阅与编辑，验证，监督，方法论，调查，形式分析。

**利益冲突声明**

作者声明以下可能被视为潜在利益冲突的财务利益/个人关系：premysl sucha报告称获得了捷克共和国技术局的财务支持。premysl sucha报告称获得了欧盟的财务支持。如果有其他作者，他们声明没有已知的财务利益或个人关系可能影响本文报告的工作。

**致谢**

本工作得到了捷克共和国技术局在项目fw11020080下的支持，并得到了欧盟在项目roboprox - 机器人技术和先进工业生产（注册号cz.02.01.01/00/22_008/0004590）下的共同资助。

michal dvo?ák | antonín novák | p?emysl ??cha | du?an knop | claire hanen q}且实例最多有两个不同的时间窗口的情况下（即(dj-tj)≤2），该问题也是强xnlp难的（定理12）。换句话说，我们证明了该问题对于组合参数#pj+pm+(dj-tj)是para-np难的。 **通用表示法** 对于非负整数a, b，我们定义[α, β]?{α, α+1, …, β-1, β}和[α]?[1, α]。特别地，[0]=0?。严格偏序是一对(Υ, ?)，其中υ是有限的集合，且?是υ上的一个非自反且传递的二元关系。如果对于υ中的任意两个不同的j1, j2，都有j1?j2, j2?j1，则集合υ′?υ是?-独立的。定义(υ, ?)的宽度ω为υ中最大的?-独立集的大小。 **参数化复杂性** 参数化复杂性是一个旨在研究计算复杂性的框架。 **难度结果** 在本节中，我们展示了1|chains(dj, tj)|cmax在k（链的数量）参数化下的强xnlp难度。作为我们归约的副产品，我们还得到了组合参数#pj+pm+(dj-tj)的para-np难度。我们首先介绍我们将要归约的问题。 对于一个属于ω*的单词w，让w[i]表示w中位置i的字符（从1开始索引），|w|表示w的长度。设u1, u2∈ω*是两个单词。u1和u2的洗牌乘积，表示为u1?u2，是所有(u1|+u2|)!(u1|!)|u2|!的集合。 **ω参数化的xp算法** 我们从一个解决优先级关系由k个链组成的特殊情况的算法开始。注意，在这种情况下，k等于优先级关系的宽度ω。 **引理15** 问题1|chains(dj, tj)|cmax可以在nω2时间内解决，其中n是作业的数量。 **证明** 设υ是要调度的作业集合，|υ|=n，并设Υ=Γ1∪?∪Γk是作业集划分成的k个链，即Γi={xi1, xi2, …, xi|γi}，xi1?xi2???xi|γi|。我们使用动态规划来解决问题。对于ji∈{0, 1, 2… **设计rpa调度算法的策略** 从设计调度算法的角度来看，rpa领域相对独特。乍一看，它可能类似于与计算集群相关的问题（khallouli & huang, 2022）。然而，集群通常由更广泛的用户群体使用，计算作业的多样性要大得多。相反，rpa与一个公司的业务流程相关，这些业务流程是明确定义的并且处于公司的控制之下。尽管如此，共同的目标是提高效率。 **结论** 我们从参数化复杂性的角度研究了与rpa相关的调度问题的复杂性理论方面。重点关注在rpa调度的真实世界实例中可以认为是小的参数，我们发现大多数情况都呈现para-np难度，即#cj, #dj, #pj, pm, (dj-tj)，以及1|chains(dj, tj)|cmax在k（链的数量）参数化下的强xnlp难度。另一方面，我们证明了当释放时间已知时，问题变为fpt。 **作者贡献声明** michal dvo?ák：写作——审阅与编辑，撰写——初稿，方法论，调查，形式分析。 antonín novák：写作——审阅与编辑，撰写——初稿，验证，方法论，调查，形式分析。 p?emysl ??cha：写作——审阅与编辑，验证，监督，项目管理，调查，资金筹集，概念化。 du?an knop：写作——审阅与编辑，验证，监督，方法论，调查，形式分析。 **利益冲突声明** 作者声明以下可能被视为潜在利益冲突的财务利益 个人关系：premysl sucha报告称获得了捷克共和国技术局的财务支持。premysl sucha报告称获得了欧盟的财务支持。如果有其他作者，他们声明没有已知的财务利益或个人关系可能影响本文报告的工作。 **致谢** 本工作得到了捷克共和国技术局在项目fw11020080下的支持，并得到了欧盟在项目roboprox - 机器人技术和先进工业生产（注册号cz.02.01.01 00 22_008 0004590）下的共同资助。 michal dvo?ák | antonín novák | p?emysl ??cha | du?an knop | claire>
**通用表示法**

对于非负整数a, b，我们定义[α, β]?{α, α+1, …, β-1, β}和[α]?[1, α]。特别地，[0]=0?。严格偏序是一对(υ, ?)，其中υ是有限的集合，且?是υ上的一个非自反且传递的二元关系。如果对于υ中的任意两个不同的j1, j2，都有j1?j2, j2?j1，则集合υ′?υ是?-独立的。定义(υ, ?)的宽度ω为υ中最大的?-独立集的大小。

**参数化复杂性**

参数化复杂性是一个旨在研究计算复杂性的框架。

**难度结果**

在本节中，我们展示了1|chains(dj, tj)|cmax在k（链的数量）参数化下的强xnlp难度。作为我们归约的副产品，我们还得到了组合参数#pj+pm+(dj-tj)的para-np难度。我们首先介绍我们将要归约的问题。

对于一个属于ω*的单词w，让w[i]表示w中位置i的字符（从1开始索引），|w|表示w的长度。设u1, u2∈ω*是两个单词。u1和u2的洗牌乘积，表示为u1?u2，是所有(u1|+u2|)!(u1|!)|u2|!的集合。

**ω参数化的xp算法**

我们从一个解决优先级关系由k个链组成的特殊情况的算法开始。注意，在这种情况下，k等于优先级关系的宽度ω。

**引理15**

问题1|chains(dj, tj)|cmax可以在nω2时间内解决，其中n是作业的数量。

**证明**

设υ是要调度的作业集合，|υ|=n，并设υ=γ1∪?∪γk是作业集划分成的k个链，即γi={xi1, xi2, …, xi|γi}，xi1?xi2???xi|γi|。我们使用动态规划来解决问题。对于ji∈{0, 1, 2…

**设计rpa调度算法的策略**

从设计调度算法的角度来看，rpa领域相对独特。乍一看，它可能类似于与计算集群相关的问题（khallouli & huang, 2022）。然而，集群通常由更广泛的用户群体使用，计算作业的多样性要大得多。相反，rpa与一个公司的业务流程相关，这些业务流程是明确定义的并且处于公司的控制之下。尽管如此，共同的目标是提高效率。

**结论**

我们从参数化复杂性的角度研究了与rpa相关的调度问题的复杂性理论方面。重点关注在rpa调度的真实世界实例中可以认为是小的参数，我们发现大多数情况都呈现para-np难度，即#cj, #dj, #pj, pm, (dj-tj)，以及1|chains(dj, tj)|cmax在k（链的数量）参数化下的强xnlp难度。另一方面，我们证明了当释放时间已知时，问题变为fpt。

**作者贡献声明**

michal dvo?ák：写作——审阅与编辑，撰写——初稿，方法论，调查，形式分析。
antonín novák：写作——审阅与编辑，撰写——初稿，验证，方法论，调查，形式分析。
p?emysl ??cha：写作——审阅与编辑，验证，监督，项目管理，调查，资金筹集，概念化。
du?an knop：写作——审阅与编辑，验证，监督，方法论，调查，形式分析。

**利益冲突声明**

作者声明以下可能被视为潜在利益冲突的财务利益/个人关系：premysl sucha报告称获得了捷克共和国技术局的财务支持。premysl sucha报告称获得了欧盟的财务支持。如果有其他作者，他们声明没有已知的财务利益或个人关系可能影响本文报告的工作。

**致谢**

本工作得到了捷克共和国技术局在项目fw11020080下的支持，并得到了欧盟在项目roboprox - 机器人技术和先进工业生产（注册号cz.02.01.01/00/22_008/0004590）下的共同资助。

michal dvo?ák | antonín novák | p?emysl ??cha | du?an knop | claire hanen>