KOPS - Das Institutionelle Repositorium der Universität 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

Zitieren

Dateien zu dieser Ressource

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 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 deposit-license eng

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

Karrenbauer etal.pdf 210

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto