Skip navigation

Parametric analysis of the quality of single preemption schedules on three uniform parallel machines

Parametric analysis of the quality of single preemption schedules on three uniform parallel machines

Soper, Alan J. ORCID: 0000-0002-0901-9803 and Strusevich, Vitaly A. (2018) Parametric analysis of the quality of single preemption schedules on three uniform parallel machines. Annals of Operations Research, 298 (1-2). pp. 469-495. ISSN 0254-5330 (Print), 1572-9338 (Online) (doi:https://doi.org/10.1007/s10479-018-2952-6)

[img]
Preview
PDF (Publisher's PDF - Open Access)
20879 SOPER_Parametric_Analysis_of_the_Quality_of_Single_Preemption_Schedules_(OA)_2018.pdf - Published Version
Available under License Creative Commons Attribution.

Download (856kB) | Preview

Abstract

For a scheduling problem to minimize the makespan on three uniform parallel machines we present a parametric analysis of the quality of a schedule with at most one preemption compared to the global optimal schedule with any number of preemptions. A tight bound is derived as a function of the relative speeds of the machines, provided that two of the machines have the same speed.

Item Type: Article
Additional Information: © The Author(s) 2018. Open Access. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Uncontrolled Keywords: 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
Last Modified: 04 Mar 2022 13:06
URI: http://gala.gre.ac.uk/id/eprint/20879

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics