de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Algorithms and Complexity for Periodic Real-Time Scheduling

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44160

Bonifaci,  Vincenzo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44228

Chan,  Ho-Leung
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45020

Megow,  Nicole
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Bonifaci, V., Chan, H.-L., Marchetti-Spaccamela, A., & Megow, N. (2010). Algorithms and Complexity for Periodic Real-Time Scheduling. In M. Charikar (Ed.), 21st Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1350-1359). Philadelphia, PA: SIAM. Retrieved from http://epubs.siam.org/doi/pdf/10.1137/1.9781611973075.109.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-15F1-3
Abstract
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 $\ccp=\ccnp$. 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 tasks 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.