We 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 |