KOPS - The Institutional Repository of the University of Konstanz

A 3/2-approximation algorithm for rate-monotonic multiprocessor scheduling of implicit-deadline tasks

A 3/2-approximation algorithm for rate-monotonic multiprocessor scheduling of implicit-deadline tasks

Type of Publication: Contribution to a collection
URI (citable link): http://nbn-resolving.de/urn:nbn:de:bsz:352-172699
Author: Karrenbauer, Andreas; Rothvoß, Thomas
Year of publication: 2011
Published in: Approximation and Online Algorithms / Jansen, Klaus; Solis-Oba, Roberto (ed.). - Berlin, Heidelberg : Springer Berlin Heidelberg, 2011. - (Lecture Notes in Computer Science ; 6534). - pp. 166-177. - ISBN 978-3-642-18317-1
DOI (citable link): https://dx.doi.org/10.1007/978-3-642-18318-8_15
Summary:
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 ∈ N 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.
Subject (DDC): 004 Computer Science
Link to License: In Copyright
Bibliography of Konstanz: Yes

Cite This

Files in this item

[PDF]
Name: Karrenbauer etal.pdf
Size: 4.1 MiB
Format: PDF
View/Open
Checksum: MD5:8e6616138da8ea74c62d9963ab51ab14

KARRENBAUER, Andreas, Thomas ROTHVOSS, 2011. A 3/2-approximation algorithm for rate-monotonic multiprocessor scheduling of implicit-deadline tasks. In: JANSEN, Klaus, ed., Roberto SOLIS-OBA, ed.. Approximation and Online Algorithms. Berlin, Heidelberg:Springer Berlin Heidelberg, pp. 166-177. ISBN 978-3-642-18317-1. Available under: doi: 10.1007/978-3-642-18318-8_15

@incollection{Karrenbauer201132app-17269, title={A 3/2-approximation algorithm for rate-monotonic multiprocessor scheduling of implicit-deadline tasks}, year={2011}, doi={10.1007/978-3-642-18318-8_15}, number={6534}, isbn={978-3-642-18317-1}, address={Berlin, Heidelberg}, publisher={Springer Berlin Heidelberg}, series={Lecture Notes in Computer Science}, booktitle={Approximation and Online Algorithms}, pages={166--177}, editor={Jansen, Klaus and Solis-Oba, Roberto}, author={Karrenbauer, Andreas and Rothvoß, Thomas} }

Karrenbauer, Andreas A 3/2-approximation algorithm for rate-monotonic multiprocessor scheduling of implicit-deadline tasks terms-of-use First publ. in: Lecture Notes in Computer Science ; 6534 (2011). - S. 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 ∈ N 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 <sup>2</sup>), 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. 2012-07-31T22:25:05Z Rothvoß, Thomas Rothvoß, Thomas Karrenbauer, Andreas 2011 2011-12-01T13:18:56Z eng

Downloads since Oct 1, 2014 (Information about access statistics)

Karrenbauer etal.pdf 578

This item appears in the following Collection(s)

Search KOPS


Browse

My Account