Paper Info
Title
Single parameter analysis of power of preemption on two and three uniform machines.
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. We derive tight upper bounds on the power of preemption expressed as piecewise functions of a single parameter, which is the speed of the fastest machine.
Year
DOI
Venue
2014
10.1016/j.disopt.2013.12.004
Discrete Optimization
Keywords
Field
DocType
Scheduling,Uniform parallel machines,Power of preemption
Parameter analysis,Mathematical optimization,Preemption,Job shop scheduling,Computer science,Scheduling (computing),Parallel computing,Piecewise
Journal
Volume
ISSN
Citations 
12
1572-5286
4
PageRank 
References 
Authors
0.47
6
2
Name
Order
Citations
PageRank
ALAN J. SOPER1254.48
Vitaly A. Strusevich271661.09