El desarrollo de programas integrados de producción y mantenimiento preventivo se ha convertido en un área de investigación muy atractiva debido a los inconvenientes que se evitarían con una gestión integrada entre estas actividades de la empresa. La naturaleza compleja de este tipo de problemas ha provocado que la mayoría de las alternativas de solución se hayan concentrado en la adopción de métodos heurísticos y metaheurísticos, capaces de proveer soluciones aceptables con una eficiencia razonable. En este sentido el presente trabajo muestra el diseño de un algoritmo para la programación integrada producción - mantenimiento en un ambiente productivo de máquinas paralelas, teniendo como objetivo minimizar el tiempo total de fabricación (makespan). El algoritmo fue estructurado en dos fases; en la primera se obtiene una solución inicial mediante el diseño de una heurística constructiva inspirada en la conocida regla de despacho Largest Processing Time (LPT), con algunas modificaciones para considerar la naturaleza estocástica del problema; en la fase 2 se intenta mejorar la solución inicial mediante un método de recocido simulado. A diferencia de otras propuestas en esta el momento de efectuar el mantenimiento preventivo no se considera un parámetro fijo, sino que constituye una variable de decisión que se trata de optimizar de conjunto con la secuencia de fabricación; por otro lado se considera el hecho de que varios trabajos pueden tener fechas de lanzamiento diferentes. Otros enfoques bajo los cuales puede abordarse el problema de la integración fueron considerados como mecanismo para evaluar la efectividad del algoritmo propuesto.