Energy Efficient Scheduling in Heterogeneous Systems with a Parallel Multiobjective Local Search

This article introduces ME-MLS, an e cient multithreading local search
algorithm for solving the multiobjective scheduling problem in heterogeneous com-
puting systems. We consider the minimization of both the makespan and energy
consumption objectives. The proposed method follows a fully multiobjective ap-
proach, applying a Pareto-based dominance search that is executed in parallel by
using several threads. The experimental analysis demonstrates that the new multi-
threading algorithm outperforms a set of fast and accurate two-phases deterministic
heuristics based on the traditional MinMin. The new ME-MLS method is able to
achieve signi cant improvements in both makespan and energy consumption objec-
tives in reduced execution times for a large set of testbed instances, while exhibiting
a near linear speedup behavior when using up to 24 threads.