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

Abstract. We present a new approximation algorithm for rate-monotonic multi-processor scheduling of periodic tasks with implicit deadlines. We prove that for an arbitrary parameter k E N it yields solutions with at most ( ~ + t)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 im-plemented to run in time O(n2), 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- fil strategy yields the result.