We study a popular task model for scheduling parallel real-time tasks, where the internal parallelism of each task is modeled by a directed acyclic graph (DAG). We show that deciding the feasibility of a set of sporadically recurrent DAG tasks is hard for the complexity class PSPACE, thus ruling out approaches to this problem that rely on Integer Linear Programming or Satisfiability solvers (assuming NP≠PSPACE).
Bonifaci, V., Marchetti-Spaccamela, A. (2025). Feasibility analysis of recurrent DAG tasks is PSPACE-hard. THEORETICAL COMPUTER SCIENCE, 1030(115062) [10.1016/j.tcs.2024.115062].
Feasibility analysis of recurrent DAG tasks is PSPACE-hard
Bonifaci, Vincenzo
;
2025-01-01
Abstract
We study a popular task model for scheduling parallel real-time tasks, where the internal parallelism of each task is modeled by a directed acyclic graph (DAG). We show that deciding the feasibility of a set of sporadically recurrent DAG tasks is hard for the complexity class PSPACE, thus ruling out approaches to this problem that rely on Integer Linear Programming or Satisfiability solvers (assuming NP≠PSPACE).File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
