Karrenbauer, AndreasRothvoss, Thomas2010-11-212010-11-212010-11-21201110.1007/978-3-642-18318-8_15https://infoscience.epfl.ch/handle/20.500.14299/58001We 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.schedulingapproximation algorithmsA 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Taskstext::conference output::conference proceedings::conference paper