Skip navigation

Single parameter analysis of power of preemption on two and three uniform machines

Single parameter analysis of power of preemption on two and three uniform machines

Warning

Notice of Repository Upgrade

Greenwich Academic Literature Archive will be being upgraded between 16:00 18th February and 10:00 20th February. During this time user login will be disabled but publications will still be accessible for download, except for one or two brief periods.

We apologise for any inconvenience. Please contact gala@gre.ac.uk for more information.

Soper, Alan J. ORCID: 0000-0002-0901-9803 and Strusevich, Vitaly A. (2014) Single parameter analysis of power of preemption on two and three uniform machines. Discrete Optimization, 12. pp. 26-46. ISSN 1572-5286 (doi:10.1016/j.disopt.2013.12.004)

Full text not available from this repository.

Abstract

We consider scheduling problems on two and three uniform parallel machines. In the case of three machines we focus on the instances in which two machines have the same speed. For these models, we analyze the power of preemption defined as the ratio of the makespan of an optimal non-preemptive schedule over the makespan of an optimal preemptive schedule.Wederive tight upper bounds on the power of preemption expressed as piecewise functions of a single parameter, which is the speed of the fastest machine.

Item Type: Article
Uncontrolled Keywords: Scheduling; Uniform parallel machines; Power of 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: 25 Apr 2017 14:34
Selected for GREAT 2016: GREAT a
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/10166

Actions (login required)

View Item View Item