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)

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

Downloads