Los problemas de programación de flujo de trabajo son ejemplos clásicos de problemas de programación multi-recursos y multi-operaciones donde el objetivo es minimizar el makespan. Debido a la alta complejidad e intractabilidad del problema, aparte de algunos casos excepcionales, no existen algoritmos explícitos para encontrar la permutación óptima en entornos de múltiples máquinas. Por lo tanto, se utilizan diferentes enfoques heurísticos, incluidos algoritmos evolutivos y meméticos, para obtener la solución, o al menos, una aproximación lo suficientemente cercana al óptimo. Este artículo propone un enfoque novedoso: una combinación novedosa de dos heurísticos bastante eficientes, el algoritmo evolutivo memético bacteriano discreto (DBMEA) propuesto anteriormente por nuestro grupo, y un heurístico convenientemente modificado, el método del árbol de Monte Carlo. Mediante su combinación anidada se obtuvo un nuevo algoritmo: el algoritmo evolutivo memético bacteriano discreto híbrido (HDBMEA), que fue ampliamente probado en el conjunto de datos de referencia de Taillard. Nuestros resultados se compararon con todos los demás enfoques importantes publicados en la literatura, y encontramos que este método compuesto novedoso produce buenos resultados en general y, en algunos casos, incluso aproximaciones mejores al óptimo que cualquiera de las soluciones propuestas hasta ahora.