Los estudios sobre el problema de programación de pedidos de clientes han estado atrayendo cada vez más atención. La mayoría de los enfoques actuales consideran que los tiempos de procesamiento de los componentes para los pedidos de los clientes en cada máquina son constantes o que todos los pedidos de los clientes están disponibles al inicio de la planificación de la producción. Sin embargo, estas suposiciones no se cumplen en aplicaciones del mundo real. La incertidumbre puede ser causada por múltiples problemas, incluyendo una avería de la máquina, cambios en el entorno de trabajo e inestabilidad de los trabajadores. Sobre la base de estos factores, introdujimos un problema de programación de pedidos de clientes en máquinas paralelas con dos tiempos de procesamiento de componentes dependientes del escenario, fechas límite y tiempos de preparación. El objetivo era identificar un horario apropiado y robusto para minimizar el máximo de la suma de números ponderados de pedidos tardíos entre los escenarios considerados. Para resolver este problema difícil, derivamos algunas propiedades dominantes y un límite inferior para determinar una solución óptima. Posteriormente, consideramos tres variantes del algoritmo de Moore, un algoritmo genético y un hiperheurístico basado en algoritmos genéticos que incorporaba las siete heurísticas de bajo nivel propuestas para resolver este problema. Finalmente, se evaluaron las actuaciones de todos los algoritmos propuestos.