A Multi-objective GRASP Algorithm for Joint Optimization of Energy Consumption and Schedule 
Length of Precedence-Constrained Applications

Abstract

We address the problem of scheduling precedence-constrained scientific applications on a heterogeneous 
distributed processor system with the twin objectives of minimizing simultaneously energy consumption 
and schedule length. Previous research efforts on scheduling have focused on the minimization of a quality 
of service metric based on the completion time of applications (e.g., the schedule length). Recently, many 
researchers are working on the design of new scheduling algorithms that consider the minimization of energy 
consumption. We report a new scheduling algorithm accounting for both objectives. The new scheduling algorithm 
is based on a multi-start randomized adaptive search technique (GRASP framework) that adopts Dynamic Voltage 
Scaling technique to minimize energy consumption. This technique enables processors to operate in different 
voltage supply levels at the cost of sacrificing clock frequencies. This multiple voltage implies a trade-off 
between the quality of the schedules and energy consumption. Therefore, the new proposed approach is designed 
as a multi-objective algorithm that simultaneously optimize both objectives. Simulation results on a set of 
real-world applications emphasize the robust performance of the proposed approach.