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
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.
[ Back ]