{"id":"arxiv/2601.11984","url":"https://arxiv.org/abs/2601.11984","tags":["cs.DS","math.OC"],"score":0,"title":"Parameterized Complexity of Scheduling Problems in Robotic Process Automation","domain":"cs.DS","source":"arxiv","authors":["Michal Dvořák","Antonín Novák","Přemysl Šůcha","Dušan Knop","Claire Hanen"],"reviews":0,"subject":"cs.DS","summary":"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 with precedence constraints, release times, and deadlines (i.e., the problem known as $1|\\operatorname{prec},r_j,d_j|*$ in the three-field notation). 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 strongly XNLP-hard parameterized by the number of…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-17","reactions":{}}