A Genetic Algorithm with Critical‑Path‑Driven Dual‑Neighborhood Search for Flexible Job Shop Scheduling

Resumen Técnico: Un Algoritmo Genético con Búsqueda de Vecindad Dual Impulsada por la Ruta Crítica para la Programación Flexible de Talleres de Trabajo

Definición del Problema
El artículo aborda el Problema de Programación Flexible de Talleres de Trabajo (FJSP, por sus siglas en inglés), un desafío de optimización fuertemente NP-duro prevalente en la fabricación moderna. A diferencia del Problema Clásico de Programación de Talleres de Trabajo (JSP), donde las operaciones tienen asignaciones de máquinas fijas, el FJSP permite que cada operación sea procesada en cualquier máquina de un conjunto de candidatos alternativos, a menudo con tiempos de procesamiento variables. El objetivo principal es minimizar la fecha de finalización total o makespan ($C_{max}$), definida como el tiempo de finalización máximo de todos los trabajos. El problema implica determinar tanto la selección de máquinas para cada operación como la secuencia de procesamiento en cada máquina, satisfaciendo al mismo tiempo las restricciones de precedencia y la disponibilidad de las máquinas.

Metodología: HGVNSA
Los autores proponen un Algoritmo de Búsqueda de Vecindad Variable Híbrido Genético (HGVNSA) que integra un Algoritmo Genético (GA) para la exploración global con una Búsqueda de Vecindad Variable (VNS) impulsada por la Ruta Crítica para la explotación local.

1. Codificación y Decodificación: La solución se representa mediante una codificación de dos capas: un vector de Secuencia de Operaciones (OS) y un vector de Selección de Máquinas (MS). Se emplea una estrategia de decodificación activa para generar programas factibles.
2. Inicialización de la Población: Para equilibrar la calidad y la diversidad, la población inicial se genera utilizando una estrategia híbrida: Selección Global (60%, minimizando el incremento de carga global), Selección Local (30%, equilibrando la carga dentro de los trabajos) y Selección Aleatoria (10%).
3. Operaciones Genéticas:
   • Crossover (Cruce): Se introduce un operador de cruce basado en el Relacionamiento de Caminos (Path-Relinking, PR). En lugar de un intercambio aleatorio de genes, este transforma sistemáticamente una solución padre en otra, registrando y evaluando soluciones intermedias para explotar el espacio de búsqueda entre los padres.
   • Mutación: Un mecanismo de mutación adaptativa ajusta las probabilidades basándose en el fitness individual y el conteo de generaciones. Se utilizan dos tipos de mutación: mutación de OS (reordenamiento del orden de las operaciones) y mutación de MS (cambio de las asignaciones de máquinas).
   • Preservación de la Diversidad: Se emplea una estrategia basada en la distancia de Hamming para mantener la diversidad de la población y prevenir la convergencia prematura.
4. VNS de Vecindad Dual Impulsada por la Ruta Crítica: La búsqueda local, incrustada dentro del marco del GA, se centra en las operaciones ubicadas en la ruta crítica (el camino más largo en el grafo disyuntivo). Utiliza dos estructuras de vecindad complementarias:
   • Vecindad N8: Optimiza la secuencia de operaciones en la misma máquina. Extiende los movimientos tradicionales N5-N7 al permitir que las operaciones críticas fuera de los bloques críticos se muevan a los extremos de los bloques o a posiciones pre/post-bloque.
   • Vecindad de k-Inserción: Reasigna operaciones críticas a diferentes máquinas. Esto implica recorrer máquinas alternativas e insertar la operación en posiciones factibles, verificando dependencias cíclicas.
   • Estrategia de Búsqueda: El proceso VNS prioriza la vecindad N8 (menor costo computacional) y cambia a la k-inserción (mayor costo, búsqueda más amplia) solo si no se encuentra una mejora, asegurando un equilibrio entre la eficiencia y la profundidad de la exploración.

Contribuciones Clave
El artículo describe cinco contribuciones principales:

1. Marco Híbrido: Establece un marco sinérgico de "primero exploración global, explotación local después", equilibrando eficazmente la precisión de la solución y la eficiencia computacional.
2. Integración de Vecindad Dual: Es el primero en integrar las vecindades N8 y de k-inserción dentro de un marco VNS unificado para FJSP. Esta combinación aborda tanto la secuenciación intra-máquina como la reasignación inter-máquina, mejorando significativamente la capacidad de búsqueda local.
3. Operadores Genéticos Mejorados: La introducción del cruce por Relacionamiento de Caminos y las probabilidades de mutación adaptativas fortalece la capacidad del algoritmo para explorar el espacio de soluciones y mantener la estabilidad de la convergencia.
4. Rendimiento en Benchmarks: En el conjunto de benchmarks Brandimarte MK, el HGVNSA alcanza consistentemente las soluciones óptimas conocidas en 6 de 10 instancias (MK01-MK04, MK08-MK09) y logra el menor promedio de Desviación Porcentual Relativa (RPD) de 0.06% entre los algoritmos comparados (HGWO, HLO-PSO, HA, SLGA, ISLGA).
5. Aplicación en el Mundo Real: El algoritmo se aplicó a un escenario de procesamiento de ejes de engranajes en la Compañía A. Comparado con un Algoritmo Genético tradicional, el HGVNSA mejoró la eficiencia de producción en un 8.81%, demostrando su practicidad de ingeniería.

Resultados y Validación

• Pruebas de Benchmark: Experimentos extensos en las instancias MK01-MK10 mostraron que el HGVNSA superó a los algoritmos de comparación en términos de calidad de solución y estabilidad. Los estudios de ablación confirmaron que eliminar el componente VNS, la estructura de vecindad dual o los mecanismos adaptativos conducía a una degradación significativa del rendimiento (por ejemplo, eliminar VNS aumentó el makespan promedio en MK02 de 26 a 30.4).
• Estudio de Caso: En el estudio de caso de la Compañía A, que involucra 10 trabajos y 59 operaciones en 15 máquinas, el algoritmo redujo el makespan de 522 (GA tradicional) a 476.
• Convergencia: El análisis de convergencia indicó que, mientras otros algoritmos se estancaban tras una convergencia inicial rápida, el HGVNSA continuaba refinando las soluciones a través de sus mecanismos de búsqueda local, rompiendo los óptimos locales en iteraciones posteriores.

Significancia
El artículo afirma que el HGVNSA proporciona un marco de solución eficiente y robusto para el FJSP, abordando eficazmente los desafíos de equilibrar la búsqueda global y la local, así como el diseño de estructuras de vecindad efectivas. El estudio valida que la combinación de la búsqueda local impulsada por la ruta crítica con la evolución genética produce resultados superiores tanto en benchmarks teóricos como en entornos industriales prácticos. Los autores sugieren que este trabajo sienta las bases para futuras investigaciones en programación distribuida y el uso de aprendizaje por refuerzo profundo para la selección inteligente de vecindades, aunque no afirman que estas extensiones hayan sido implementadas en el estudio actual.