In this paper we study a CPU/FPGA heterogeneous architecture scheduling problem (often referred as Multi-Processors System on Chip or MPSoC) with communication delays’ constraints. In this context, we propose two approaches based on genetic algorithms. Their main goal is to run in the MPSoC an application, which is described by a given data flow graph. The aim is to minimize the schedule length (makespan). Computational experiments are conducted to evaluate the proposed algorithms. The obtained results show that the two approaches are often capable of finding optimal or near optimal solutions for the studied problem while improving significantly the running time compared to existing works.