Single parameter analysis of power of preemption on two and three uniform machines
| Autor: | Alan Soper, Vitaly A. Strusevich |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Mathematical optimization
Job shop scheduling Computer science Applied Mathematics Preemption Single parameter Parallel computing Theoretical Computer Science Scheduling (computing) Computer Science::Performance Computational Theory and Mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Piecewise Computer Science::Data Structures and Algorithms Computer Science::Operating Systems |
| Zdroj: | Discrete Optimization. 12:26-46 |
| ISSN: | 1572-5286 |
| DOI: | 10.1016/j.disopt.2013.12.004 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect