Skip navigation

Power of preemption for minimizing total completion time for uniform parallel machines

Power of preemption for minimizing total completion time for uniform parallel machines

Epstein, Leah, Levin, Asif, Soper, Alan 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:10.1137/16M1066610)

[img]
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 / Department / Research Group: Faculty of Architecture, Computing & Humanities
Faculty of Architecture, Computing & Humanities > Department of Mathematical Sciences
Last Modified: 31 Aug 2017 11:18
Selected for GREAT 2016: None
Selected for GREAT 2017: GREAT a
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/16762

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics