The maximum gain of increasing the number of preemptions in multiprocessor scheduling

Document type: Journal Articles
Article type: Original article
Peer reviewed: Yes
Author(s): Kamilla Klonowska, Lars Lundberg, Håkan Lennerstad
Title: The maximum gain of increasing the number of preemptions in multiprocessor scheduling
Journal: ACTA INFORMATICA
Year: 2009
Volume: 46
Issue: 4
Pagination: 285-295
ISSN: 0001-5903
Publisher: Springer
URI/DOI: 10.1007/s00236-009-0096-5
ISI number: 000267214400002
Organization: Blekinge Institute of Technology
Department: School of Computing, School of Engineering - Dept. of Mathematics & Natural Sciences (Sektionen för datavetenskap och kommunikation, Sektionen för ingenjörsvetenskap - Avd.för matematik och naturvetenskap)
School of Computing S-371 79 Karlskrona, School of Engineering S-371 79 Karlskrona
+46 455 38 50 00
http://www.bth.se/com; http://www.bth.se/ing/
Language: English
Abstract: We consider the optimal makespan C(P, m, i) of an arbitrary set P of independent jobs scheduled with i preemptions on a multiprocessor with m identical processors. We compare the ratio for such makespans for i and j preemptions, respectively, where i < j. This ratio depends on P, but we are interested in the P that maximizes this ratio, i. e. we calculate a formula for the worst case ratio G(m, i, j) defined as G(m, i, j) = max C(P, m, i)/C(P, m, j), where the maximum is taken over all sets P of independent jobs.
Subject: Software Engineering\General
Edit