Branch and Bound Algorithm for the Heterogeneous Computing Scheduling Multi-Objective Problem

Authors

  • J. Carlos Soto-Monterrubio Tecnológico Nacional de México, Instituto Tecnológico de Ciudad Madero
  • Alejandro Santiago Universidad de Cádiz
  • Héctor J. Fraire-Huacuja Tecnológico Nacional de México, Instituto Tecnológico de Ciudad Madero
  • Juan Frausto-Solís Tecnológico Nacional de México, Instituto Tecnológico de Ciudad Madero
  • David Terán-Villanueva Tecnológico Nacional de México, Instituto Tecnológico de Ciudad Madero

Keywords:

Scheduling, optimal Pareto front, exact algorithm, branch and bound

Abstract

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.

Downloads

Published

2016-11-09

How to Cite

Soto-Monterrubio, J. C., Santiago, A., Fraire-Huacuja, H. J., Frausto-Solís, J., & Terán-Villanueva, D. (2016). Branch and Bound Algorithm for the Heterogeneous Computing Scheduling Multi-Objective Problem. International Journal of Combinatorial Optimization Problems and Informatics, 7(3), 7–19. Retrieved from https://ijcopi.org/ojs/article/view/23

Issue

Vol. 7 No. 3 (2016)

Section

Articles

Most read articles by the same author(s)