Aunque algunos factores de incertidumbre pueden ocurrir en muchos entornos prácticos, los problemas de programación de pedidos de clientes que involucran a dos agentes en tales entornos inciertos no han recibido atención en la literatura actual. Motivados por esta observación, abordamos un problema de programación de pedidos de clientes de dos agentes donde varios pedidos de clientes tienen tiempos de procesamiento de componentes dependientes del escenario y fechas de liberación con el fin de encontrar un horario apropiado para minimizar el máximo del tiempo total de finalización de los pedidos de clientes que pertenecen a un agente y están sujetos a una restricción con el otro agente. Para resolver este problema, se derivan una cota inferior y seis propiedades dominantes que se utilizan para proponer un algoritmo de ramificación y acotamiento para encontrar una solución óptima exacta. Posteriormente, se proponen y evalúan empíricamente tres heurísticas de búsqueda local y dos variantes de una hiperheurística de recocido simulado para encontrar soluciones aproximadas. Finalmente, concluimos el artículo con un resumen de nuestros hallazgos y algunas direcciones para futuras investigaciones.