Assigning sporadic tasks to unrelated parallel machines

Alberto Marchetti-Spaccamela, Cyriel Rutten, Suzanne Van Der Ster, Andreas Wiese

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

We study the problem of assigning sporadic tasks to unrelated machines such that the tasks on each machine can be feasibly scheduled. Despite its importance for modern real-time systems, this problem has not been studied before. We present a polynomial-time algorithm which approximates the problem with a constant speedup factor of 11 + 4√3 ≈ 17.9 and show that any polynomial-time algorithm needs a speedup factor of at least 2, unless P = NP. In the case of a constant number of machines we give a polynomial-time approximation scheme. Key to these results are two new relaxations of the demand bound function which yields a sufficient and necessary condition for a task system on a single machine to be feasible.

Original languageEnglish
Title of host publicationAutomata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
Pages665-676
Number of pages12
EditionPART 1
DOIs
StatePublished - 2012
Externally publishedYes
Event39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 - Warwick, United Kingdom
Duration: 9 Jul 201213 Jul 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7391 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
Country/TerritoryUnited Kingdom
CityWarwick
Period9/07/1213/07/12

Fingerprint

Dive into the research topics of 'Assigning sporadic tasks to unrelated parallel machines'. Together they form a unique fingerprint.

Cite this