Skip navigation

Schedules with a single preemption on uniform parallel machines

Schedules with a single preemption on uniform parallel machines

Soper, Alan J. ORCID: 0000-0002-0901-9803 and Strusevich, Vitaly A. (2018) Schedules with a single preemption on uniform parallel machines. Discrete Applied Mathematics. ISSN 0166-218X (doi:https://doi.org/10.1016/j.dam.2018.03.007)

[img]
Preview
PDF (Author Accepted Manuscript)
19683 SOPER Schedules_With_a_Single_Preemption_on_Uniform_Parallel_Machines_2018.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (314kB) | Preview

Abstract

For a scheduling problem to minimize the makespan on parallel machines, we consider schedules with at most one preemption. We show that in the case of two machines the problem is solvable in polynomial time. For m≥3 uniform parallel machines, we measure the quality of a single preemption as the worst-case ratio of the makespan of an optimal schedule with at most one preemption over the makespan of an optimal preemptive schedule. We show that the global bound on such a ratio is 2-2/m.

Item Type: Article
Uncontrolled Keywords: Scheduling, uniform parallel machines, power of preemption, quality of a single preemption
Subjects: Q Science > QA Mathematics
Faculty / Department / Research Group: Faculty of Architecture, Computing & Humanities
Faculty of Architecture, Computing & Humanities > Department of Mathematical Sciences
Related URLs:
Last Modified: 17 May 2019 14:23
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: GREAT a
Selected for GREAT 2019: GREAT 4
URI: http://gala.gre.ac.uk/id/eprint/19683

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics