A comparison of two metaheuristic algorithms for scheduling problem on a heterogeneous CPU/FPGA architecture with communication delays

This paper considers the problem of scheduling on a heterogeneous CPU/FPGA architecture with communication delays, with the aim of minimizing the makespan (or the schedule length). For this strongly NP-hard problem, we present two iterative algorithms based on simulated annealing (SA) and genetic algorithms (GAs), which are used to run in the MPSoC an application described in a data flow graph. The performance of the proposed algorithms are evaluated and compared on a set of instances with up to 50 tasks. Computational experiments indicate that the innovative proposed algorithms provide competitive results for the studied problem and that the objective function values obtained are optimal or very close to a lower bound in a reasonable computation time.