A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks

We present a new approximation algorithm for rate-monotonic multiprocessor scheduling of periodic tasks with implicit deadlines. We prove that for an arbitrary parameter k it yields solutions with at most (3/2 + 1/k)*OPT+9k many processors, thus it gives an asymptotic 3/2-approximation algorithm. This improves over the previously best known ratio of 7/4. Our algorithm can be implemented to run in time O(n^2), where n is the number of tasks. It is based on custom-tailored weights for the tasks such that a greedy maximal matching and subsequent partitioning by a first-fit strategy yields the result.


Published in:
Approximation and Online Algorithms, 8th International Workshop (WAOA 2010)
Presented at:
Approximation and Online Algorithms, 8th International Workshop (WAOA 2010), Liverpool, UK, September 9-10, 2010
Year:
2010
Publisher:
Springer
Keywords:
Laboratories:




 Record created 2010-11-21, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)