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 polynomial 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 profit maximization variant of the feasibility problem, where every task has a non-negative profit, and the goal is to find a subset of tasks that can be scheduled feasibly with maximum profit. We give the first constant-speed, constant-approximation algorithm for the case of synchronous task systems, together with related hardness results. Copyright © by SIAM.
Bonifaci, V., Chan, H.-., Marchetti-Spaccamela, A., & Megow, N. (2010). Algorithms and complexity for periodic real-time scheduling. In Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (pp.1350-1359). Association for Computing Machinery (ACM).
| Titolo: | Algorithms and complexity for periodic real-time scheduling |
| Autori: | |
| Data di pubblicazione: | 2010 |
| Citazione: | Bonifaci, V., Chan, H.-., Marchetti-Spaccamela, A., & Megow, N. (2010). Algorithms and complexity for periodic real-time scheduling. In Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (pp.1350-1359). Association for Computing Machinery (ACM). |
| Handle: | http://hdl.handle.net/11590/381239 |
| ISBN: | 978-0-89871-701-3 |
| Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |
File in questo prodotto:
http://hdl.handle.net/11590/381239
Copyright © 2021