Parameterized Complexity of Scheduling Problems in Robotic Process Automation

Michal Dvořák, Antonín Novák, Přemysl Šůcha, Dušan Knop, Claire Hanen · 2026

Read Parameterized Complexity of Scheduling Problems in Robotic Process Automation by Michal Dvořák, Antonín Novák, Přemysl Šůcha, Dušan Knop, Claire Hanen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-11984.txt.

Introduction

Michal Dvořák, Antonín Novák, Přemysl Šůcha, Dušan Knop, and Claire Hanen study the cost of scheduling in robotic process automation. RPA tools run office tasks by script. Their schedules must respect task order, release times, and due dates.

They ask how hard the single-machine case is as key terms grow. This is a parameterized complexity study, which sorts tasks by which inputs drive the cost. Such maps help firms pick tools that scale. They also show which RPA schedules are bound to stay hard. The maps also show which inputs drive the hard cases.

Catalog record

CREATORMichal Dvořák, Antonín Novák, Přemysl Šůcha, Dušan Knop, Claire Hanen
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-11984

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Parameterized Complexity of Scheduling Problems in Robotic Process Automation Michal Dvořák, Antonín Novák, Přemysl Šůcha, Dušan Knop, Claire Hanen Abstract This paper studies the growing domain of Robotic Process Automation (RPA) problems. Motivated by scheduling problems arising in RPA, we study the parameterized complexity of the single-machine problem 1 | prec , r j , d j | ∗ 1|\operatorname{prec},r_{j},d_{j}|* . We focus on parameters naturally linked to RPA systems, including chain-like precedences, the number of distinct processing times, and the structure of the time windows. We show that the problem is W[2] -hard parameterized by the number of chains, even with only two prescribed processing times and two distinct time-window lengths. This hardness remains even for distinct processing times and time windows under prec-consistent time windows. On the positive side, we obtain polynomial-time algorithm when all jobs share a single time-window length and FPT when the processing times, release times and deadlines are chain-uniform. We also show that the problem lies in XP when parameterized by the width of the precedence relation. 1 Introduction With the increasing market competition, companies are pressured to seek ways to remain competitive while increasing their revenue, decreasing costs, and streamlining their operations. Achieving those goals is often connected with improving the efficiency of companies’ business processes. To run daily operations, large companies developed internal processes for business-related activities such as invoice processing, payment handling, and customer relationship management, but also for their back-office operations such as report generation and human resources activities, e.g., employee onboarding, payroll, etc. These workflows used to be operated by humans who are susceptible to errors, do not work 24/7, and are costly to scale up. Hence, to enable further growth and increase efficiency, companies are forced to automate their processes. Robotic Process Automation (RPA) ( 47 ) is quickly becoming the major technology for automating repetitive, rule-based tasks across many sectors by emulating human interactions with software, thus delivering faster throughput, higher accuracy, and continuous operation without risks of human fatigue. The increasing adoption of RPA systems by large enterprises has attracted the research community, which started to address different aspects of RPA—economic perspective ( 2 ; 29 ) , reports on real case-studies ( 24 ) or mathematical optimization ( 40 ) . A typical RPA system consists of a set of business processes that are automated. Each process performs operations on the individual data entries, also called items , which represent the basic unit of work. An example of a process may be a data extraction from invoices sent by suppliers via email, with the individual operation representing an optical character recognition over the PDF file and storing the extracted entries in the database. The execution of the processes might be constrained by time windows imposed by the company’s internal rules, customer requirements, or technological limitations. Each operation performed on a data entry is carried out by a software robot , which requires a hardware resource to run on (i.e. a machine, in scheduling terminology), and may require a software license. The number of licenses is typically limited ( 40 ) as the companies are charged by RPA vendors based on the number of robot licenses used. Items to be handled by a process are stored in a given number k\in\mathbb{N}_{0} of queues and the process retrieves the items (typically, but not exclusively) in the first-in first-out (FIFO) fashion. Hence, the order in which items are processed is constrained by chain precedence, or a general directed acyclic graph with limited width w\in\mathbb{N}_{0} . The processing time of an item j is denoted by p_{j}\in\mathbb{N} . Generally, they may be arbitrary, but often they are dependent on the queue in which they appear. Thus, it is reasonable to assume that all items in queue Q have processing times all equal to p_{Q} , as they are workloads of the same type. The item j enters the queue at time r_{j} , denoting its release time. The customer may choose to impose the deadline d_{j} , by which the item j should be completed. The most typical situation in RPA systems is to set the time between an item’s arrival and its deadline to a constant value, referred to as Service Level Agreement (SLA) \Delta=d_{j}-r_{j} . An RPA scheduler aims to optimize the execution of processes within the company, respecting its hardware resources, time-related constraints, and license budget in order to guarantee that all items are processed within the prescribed time, as reflected by the SLA the company committed to. The scheduling in RPA systems opens new application areas for scheduling research, as it introduces new problems to be studied, as well as provides new applications for the decades-old results. In order to design efficient scheduling algorithms for RPA systems, we need to understand the complexity of the new emerging problems as well as connections to the other well-known problems. One of the pioneering works in the area of application of optimization methods in RPA systems was presented by 40 . They coin the problem of minimizing the cost of robot licenses as an optimization problem solved by a mixed-integer linear programming model. They describe the whole range of relevant aspects of RPA scheduling, for example, they deal with different process types, the existence of licenses, deadlines, etc. However, their work focuses more on capacity planning than the scheduling problem, disregarding the sequencing aspect of the problem. As a result, their formulation leads to a bin-packing type of optimization problem. For example, the precedence relations between the items are not considered, which becomes an increasingly relevant feature of RPA systems, as the complexity of the automated workflows grows rapidly. A term associated nowadays with RPA is the hyperautomation that is a broader strategic approach that combines RPA with other technologies (e.g., artificial intelligence, machine learning) to automate and optimize end-to-end business processes beyond task-level automation. It is projected ( 36 ) that by 2030, the hyperautomation market size will extend beyond basic tasks, and will increase by 2.5\times compared to 2025 levels. Hence, to support these workflows, more elaborate modeling beyond simple capacity planning is needed. For efficient scheduling in these complex systems, it is insufficient to rely just on simple online rules governing the execution of activities. Hence, we would like to retrieve the schedule over a rolling horizon as the result of a well-defined optimization problem. To design efficient algorithms to solve these problems, we need to understand the complexity of its various aspects—namely, its (potential) tractability if some of the natural parameters such as number of queues k , precedence width w , maximum processing time p_{\max} , number of distinct processing times \#p_{j} , or number of distinct SLA’s (i.e., number of distinct time windows) \#(d_{j}-r_{j}) (see Section 4 for formal definitions) are bounded by a constant which is fairly small. This finer complexity characterization, also known as parameterized complexity , may provide the needed problem insights. It is known that in scheduling environments with parallel machines, already the simplest problems tend to be hard ( 45 ) . Therefore, in studying parameterized complexity of the problems that result from RPA scheduling, we rather focus on a family of single-machine problems with respect to

Read the complete text