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

Karrenbauer, Andreas; Rothvoß, Thomas

doi:10.1007/978-3-642-18318-8_15

Startseite
→
Zukunftskolleg
→
Zukunftskolleg
→
Dokumentanzeige

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

Publikationstyp:	Beitrag zu einem Sammelband
URI (zitierfähiger Link):	http://nbn-resolving.de/urn:nbn:de:bsz:352-172699
Autor/innen:	Karrenbauer, Andreas; Rothvoß, Thomas
Erscheinungsjahr:	2011
Erschienen in:	Approximation and Online Algorithms / Jansen, Klaus; Solis-Oba, Roberto (Hrsg.). - Berlin, Heidelberg : Springer Berlin Heidelberg, 2011. - (Lecture Notes in Computer Science ; 6534). - S. 166-177. - ISBN 978-3-642-18317-1
DOI (zitierfähiger Link):	https://dx.doi.org/10.1007/978-3-642-18318-8_15
Zusammenfassung:	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 ²), 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.
Fachgebiet (DDC):	004 Informatik
Link zur Lizenz:	Nutzungsbedingungen
Universitätsbibliographie:	Ja

Zitieren

Dateien zu dieser Ressource

Name: Karrenbauer etal.pdf

Größe: 4.127Mb

Format: PDF

Öffnen

Prüfsumme: 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 2012-07-31T22:25:05Z 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. First publ. in: Lecture Notes in Computer Science ; 6534 (2011). - S. 166-177 Rothvoß, Thomas Rothvoß, Thomas Karrenbauer, Andreas 2011 2011-12-01T13:18:56Z eng