Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




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, Moses

dblp

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

URL of the conference:

http://www.siam.org/meetings/da10/

URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
SODA10_109_bonifaciv.pdf