Power of preemption on uniform parallel machines
Soper, Alan J. ORCID: 0000-0002-0901-9803 and Strusevich, Vitaly A. (2014) Power of preemption on uniform parallel machines. In: 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’14) / 18th International Workshop on Randomization and Computation (RANDOM’14). Leibniz International Proceedings in Informatics (LIPIcs) (28). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, pp. 392-402. ISBN 9783939897743 ISSN 1868-8969 (doi:https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.392)
|
PDF (Publisher's PDF (CC-BY License))
12881_SOPER_STRUSEVICH_LIPIcs_2014_(OA).pdf - Published Version Available under License Creative Commons Attribution. Download (355kB) |
|
PDF (Acceptance email)
12881_SOPER_STRUSEVICH_APPROX2014_(conference_proceeding)_(Acceptance_email_6_June_2014).pdf - Additional Metadata Restricted to Repository staff only Download (387kB) |
Abstract
For a scheduling problem on parallel machines, the power of preemption is defined as the ratio of the makespan of an optimal non-preemptive schedule over the makespan of an optimal preemptive schedule. For m uniform parallel machines, we give the necessary and sufficient conditions under which the global bound of 2-1/m is tight. If the makespan of the optimal preemptive schedule is defined by the ratio of the total processing times of r < m longest jobs over the total speed of r fastest machines, we show that the tight bound on the power of preemption is 2-1/min{r,m-r}.
Item Type: | Conference Proceedings |
---|---|
Title of Proceedings: | 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’14) / 18th International Workshop on Randomization and Computation (RANDOM’14) |
Additional Information: | [1] Copyright: (c) Alan J. Soper and Vitaly A. Strusevich. Licensed under Creative Commons License CC-BY. |
Uncontrolled Keywords: | machine scheduling; uniform parallel machines; power of preemption; |
Subjects: | Q Science > QA Mathematics |
Faculty / School / Research Centre / Research Group: | Faculty of Engineering & Science > School of Computing & Mathematical Sciences (CMS) Faculty of Engineering & Science |
Related URLs: | |
Last Modified: | 04 Mar 2022 13:07 |
URI: | http://gala.gre.ac.uk/id/eprint/12881 |
Actions (login required)
View Item |
Downloads
Downloads per month over past year