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).
2025
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].
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/498056
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact