Benvenuti nell'Anagrafe della Ricerca d'Ateneo
La valutazione delle attività di ricerca che si svolgono nelle università ha assunto un'importanza rilevante sia per l'intero sistema universitario sia all'interno di ogni singolo ateneo. Roma Tre si è quindi dotata di idonei strumenti informativi in grado di supportare al meglio le azioni di monitoraggio e di valutazione delle attività di ricerca svolte nei propri dipartimentied ha realizzato una Anagrafe della Ricerca di Ateneo.
EnglishWe investigate the preemptive scheduling of periodic tasks with hard deadlines. We show that, even in the uniprocessor case, no pseudopolynomial-time algorithm can test the feasibility of a task system within a constant speedup bound, unless P = NP. This result contrasts with recent results for sporadic task systems. For two special cases, synchronous task systems and systems with a constant number of different task types, we provide the first polynomial-time constant-speedup feasibility tests for multiprocessor platforms. Furthermore, we show that the problem of testing feasibility is coNP-hard for synchronous multiprocessor task systems. The complexity of some of these problems has been open for a long time. We also propose a weight maximization variant of the feasibility problem, where every task has a nonnegative weight, and the goal is to find a subset of tasks that can be scheduled feasibly and has maximum weight. We give the first constant-speed, constant-approximation algorithm for the case of synchronous task systems, together with related hardness results. © 2012 ACM.
Bonifaci, V., Chan, H.-., Marchetti-Spaccamela, A., & Megow, N. (2012). Algorithms and complexity for periodic real-time scheduling. ACM TRANSACTIONS ON ALGORITHMS, 9(1), 1-19 [10.1145/2390176.2390182].
| Titolo: | Algorithms and complexity for periodic real-time scheduling | |
| Autori: | ||
| Data di pubblicazione: | 2012 | |
| Rivista: | ||
| Citazione: | Bonifaci, V., Chan, H.-., Marchetti-Spaccamela, A., & Megow, N. (2012). Algorithms and complexity for periodic real-time scheduling. ACM TRANSACTIONS ON ALGORITHMS, 9(1), 1-19 [10.1145/2390176.2390182]. | |
| Handle: | http://hdl.handle.net/11590/381331 | |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| periodic-talg.pdf | Documento in Post-print | DRM non definito | Open Access Visualizza/Apri |
http://hdl.handle.net/11590/381331
Copyright © 2021