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)
|
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
Downloads per month over past year