MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Bonifaci, Vincenzo
Chan, Ho-Leung
Marchetti-Spaccamela, Alberto
Megow, Nicole
dblp
dblp
dblp
dblp
Not MPG Author(s):
Marchetti-Spaccamela, Alberto
Editor(s):
Charikar, Mosesdblp
Not MPII Editor(s):
Charikar, Moses
BibTeX cite key*:
Bonifaci:2010:b
Title, Booktitle
Title*:
Algorithms and Complexity for Periodic Real-Time Scheduling
SODA10_109_bonifaciv.pdf (759.2 KB)
Booktitle*:
21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)
Event, URLs
Conference URL::
http://www.siam.org/meetings/da10/
Downloading URL:
http://www.siam.org/proceedings/soda/2010/SODA10_109_bonifaciv.pdf
Event Address*:
Austin (TX), USA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
10 January 2010
Event End Date:
10 January 2010
Publisher
Name*:
SIAM
URL:
Address*:
Philadelphia, Pa.
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
1350-1359
Year*:
2010
VG Wort Pages:
28
ISBN/ISSN:
978-0-898716-98-6
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Keywords:
Real-Time Scheduling, Periodic Task System, Feasibility Test, Earliest Deadline First, Approximation Algorithm
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Bonifaci:2010:b,
AUTHOR = {Bonifaci, Vincenzo and Chan, Ho-Leung and Marchetti-Spaccamela, Alberto and Megow, Nicole},
EDITOR = {Charikar, Moses},
TITLE = {Algorithms and Complexity for Periodic Real-Time Scheduling},
BOOKTITLE = {21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)},
PUBLISHER = {SIAM},
YEAR = {2010},
PAGES = {1350--1359},
ADDRESS = {Austin (TX), USA},
ISBN = {978-0-898716-98-6},
}


Entry last modified by Vincenzo Bonifaci, 02/10/2011
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
01/10/2010 04:57:19 PM
Revisions
11.
10.
9.
8.
7.
Editor(s)
Vincenzo Bonifaci
Vincenzo Bonifaci
Anja Becker
Anja Becker
Anja Becker
Edit Dates
02/10/2011 05:23:12 PM
02/10/2011 11:47:40 AM
14.01.2011 09:23:03
10.01.2011 11:18:37
12/20/2010 06:22:04 PM


File Attachment Icon
SODA10_109_bonifaciv.pdf