Un algoritmo de satisfactibilidad para el problema de Job Shop scheduling

    En este artículo proponemos un algoritmo llamado SPJS (Satisfactibilidad del problema de Job Shop) para el problema de scheduling, que permite encontrar asignaciones satisfactibles de Job Shop mediante la evaluación de cláusulas reducidas de la Lógica proposicional que representan al problema. La asignación propuesta en Job shop parte de una codificación en forma SAT que solo incluye a cláusulas que representan a las restricciones de precedencia y que se evalúan mediante la obtención de los tiempos de inicio más tardíos, los que se obtienen por medio de un algoritmo que encuentra la ruta más larga.