State-Space Search to Find Energy-Aware Pareto-Efficient Optimal Task Schedules

Bi-objective scheduling for parallel computing, in particular with the objectives to minimize makespan and energy, has been well studied in the literature. Numerous works have proposed algorithms that use Dynamic Voltage and Frequency Scaling (DVFS) as the mechanism to reduce energy consumption. Given the NP-hard nature of the combinatorial task scheduling problem, these algorithms are mostly heuristics, producing only a single or few schedules for a given instance. This research explores bi-objective task scheduling with the goal to find the set of Pareto-efficient solutions for a given small instance, using DVFS to balance energy and performance. We undertake this using a branch-and-bound depth-first search within an allocation-ordering state space model. Varying scaling factors and static energy models are considered. The proposed approach is evaluated with a dataset of small graphs resulting in thousands of produced schedules. In contrast to heuristics, our approach computes numerous trade-off solutions for a given problem instance as a Pareto-efficient set.