Parameterized Complexity of Scheduling Problems in Robotic Process Automation

Source: arxiv.org/abs/2601.11984

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

arXivarxiv/2601.11984Jan 17, 2026cs.DSscore 0

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…

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2601.11984
curl -X POST /api/v1/records/arxiv/2601.11984/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.11984/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'