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

 

Abstract:
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" [...]

 

  payday loan . If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.