Epstein, Leah, Levin, Asif, Soper, Alan ORCID: 0000-0002-0901-9803 and Strusevich, Vitaly (2017) Power of preemption for minimizing total completion time for uniform parallel machines. SIAM Journal on Discrete Mathematics, 31 (1). pp. 101-123. ISSN 0895-4801 (Print), 1095-7146 (Online) (doi:https://doi.org/10.1137/16M1066610)

Preview

PDF (Publisher's PDF - Open Access) 16762 SOPER_Power_of_Preemption_2017.pdf - Published Version Available under License Creative Commons Attribution. Download (275kB) | Preview

Abstract

For scheduling problems on parallel machines, the power of preemption is defined as the supremum ratio of the cost of an optimal nonpreemptive schedule over the cost of an optimal preemptive schedule (for the same input), where the cost is defined by a fixed common cost function. We present a tight analysis of the power of preemption for the problem of minimizing the total completion time on m ≥ 2 uniformly related machines, showing that its value for m = 2 is equal to 1.2, and its overall value is approximately 1.39795.

Item Type:	Article
Additional Information:	© 2017 SIAM. Published by SIAM under the terms of the Creative Commons 4.0 license.
Uncontrolled Keywords:	Scheduling; Total completion time; Power of pre-emption; Uniformly related machines
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
Last Modified:	04 Mar 2022 13:07
URI:	http://gala.gre.ac.uk/id/eprint/16762

Actions (login required)

View Item

Downloads