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

Research Area: | Algorithm Engineering for Real-time Scheduling and Routing | Year: | 2011 | ||
---|---|---|---|---|---|

Type of Publication: | In Proceedings | Keywords: | scheduling; approximation algorithms | ||

Authors: | A. Karrenbauer; T. Rothvoß | ||||

Volume: | 6534 | ||||

Book title: | Proceedings of the 8th International Workshop on Approximation and Online Algorithms (WAOA 2010) | ||||

Series: | Lecture Notes in Computer Science | Pages: | 166-177 | ||

BibTex: |
|||||

Abstract: | 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. |
||||

[Bibtex] |