TY - GEN
T1 - Assigning sporadic tasks to unrelated parallel machines
AU - Marchetti-Spaccamela, Alberto
AU - Rutten, Cyriel
AU - Van Der Ster, Suzanne
AU - Wiese, Andreas
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84883787865&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-31594-7_56
DO - 10.1007/978-3-642-31594-7_56
M3 - Conference contribution
AN - SCOPUS:84883787865
SN - 9783642315930
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 665
EP - 676
BT - Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
T2 - 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
Y2 - 9 July 2012 through 13 July 2012
ER -