Scheduling of tasks on a multi-machine system to reduce the makespan,
while satisfying the precedence constraints between the tasks, is
known to be an NP-hard problem. We propose a new formulation and show
that energy-aware scheduling is a generalization of the minimum
makespan scheduling problem. Taking the system graph and program
graph as inputs, we propose three different algorithms for
energy-aware scheduling, each of them having their own strengths and
limitations. The first is a genetic algorithm (Plain GA) that
searches for an energy reducing schedule. The second (CA+GA) uses
cellular automata (CA) to generate low energy schedules while using a
genetic algorithm (GA) to find good rules for the CA. The third (EAH)
is a heuristic which gives preference to high-efficiency machines in
allocation. We have tested our algorithms on well-known program
graphs and compared our results with other state-of-the-art scheduling
algorithms, which confirms the efficacy of our approach. Our work
also gives insight into the time-energy trade-offs in scheduling.