Skip navigation

Power of preemption on uniform parallel machines

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)

[img]
Preview
PDF (Publisher's PDF (CC-BY License))
12881_SOPER_STRUSEVICH_LIPIcs_2014_(OA).pdf - Published Version
Available under License Creative Commons Attribution.

Download (355kB)
[img] 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 View Item

Downloads

Downloads per month over past year

View more statistics