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 |
