Branch and Bound Algorithm for the Heterogeneous Computing Scheduling Multi-Objective Problem
Keywords:Scheduling, optimal Pareto front, exact algorithm, branch and bound
In this paper the Pareto optimization of the Heterogeneous Computing Scheduling Multi-Objective Problem (HCSMOP) is approached. The goal is to minimize two objectives which are in conflict: the overall completion time (makespan) and the energy consumed. In the revised literature, there are no reported exact algorithms which solve the HCSMOP. In this work, we propose a Branch and Bound algorithm to solve the problem and it is used to find the optimal Pareto front of a set of instances of the literature. This set is the first available benchmark to assess the performance of multiobjective algorithms with quality metrics that requires known the optimal front of the instances.