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)

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)
	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:	Publisher
Last Modified:	04 Mar 2022 13:07
URI:	http://gala.gre.ac.uk/id/eprint/12881

Actions (login required)

View Item

Downloads