Tuesday, 13:15 - 13:40 h, Room: MA 041


Rodrigo Carrasco
Experimental results of approximation algorithms for energy aware scheduling

Coauthors: Garud Iyengar, Cliff Stein


The increasing awareness of the environmental impact of massive data centres has led to an increased interest in energy management algorithms.
We have developed several new constant factor approximation algorithms for energy aware scheduling problems. The objective is to minimize the sum of the total energy consumed and the total weighted completion time or the total weighted tardiness in the one machine non-preemptive setting, allowing for arbitrary precedence constraints and also release dates for the weighted completion time. Unlike previous known algorithms our new algorithms can handle general job-dependent energy cost functions extending their application to settings that have maintenance costs, wear and tear, replacement costs, etc., which in general also depend on the particular job being processed.
In this works we seek to understand the practical performance of these algorithms. We show that the practical performance is significantly superior to the theoretical bounds and in fact are very close to optimal. Additionally, we present heuristic improvements and we also investigate their performance in other settings: online, total weighted flow time, multiple machines, etc.


Talk 1 of the invited session Tue.2.MA 041
"Practical implementations and models using approximation algorithms" [...]
Cluster 1
"Approximation & online algorithms" [...]


  short term loans . But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.