Metaheurísticas híbridas para la tardanza en job shop: qué funcionó y qué no

Este artículo se basa en el case study Hybrid Metaheuristic Scheduling, un relato solo documental de una investigación académica realizada en colaboración. La implementación y los datos no son públicos, y nada de lo que sigue va más allá de lo que el case study ya afirma.

El problema: trabajos atrasados, rutas fijas

Un job shop es un conjunto de trabajos, cada uno una secuencia de operaciones, cada operación ligada a una máquina. El objetivo clásico es terminar todo lo antes posible. En una planta metalmecánica la pregunta que de verdad duele es otra: ¿cuánto vamos a entregar tarde? El objetivo pasa a ser minimizar la tardanza total, Σ T_j: la suma, sobre todos los trabajos, de cuánto termina cada uno después de su fecha de entrega. Es un problema fuertemente NP-duro: para instancias de tamaño realista, los métodos exactos dejan de ser una opción.

Las plantas reales añaden un giro que los benchmarks académicos omiten. La secuencia de producción —preparación de material, mecanizado CNC, torneado, terminación— es tecnológica, no negociable. Una operación no puede colarse en un hueco conveniente de una máquina si su predecesora no ha terminado. Las instancias clásicas suponen ese tipo de inserción flexible; la planta no. Cuando se hizo este trabajo no existía ningún benchmark de job shop con restricciones de precedencia, así que el estudio adaptó instancias clásicas para añadirlas. Esa adaptación es a la vez la contribución del estudio y su principal limitación, y volveremos sobre ello.

Tres metaheurísticas, un motor

Ninguna metaheurística es buena en todo. El motor combina tres que son buenas en cosas distintas:

• GRASP (Greedy Randomized Adaptive Search) construye programas iniciales factibles y diversos: una heurística constructiva voraz inicializada con la regla de fecha de entrega más próxima (EDD), aleatorizada para que ejecuciones repetidas exploren regiones distintas.
• VNS (Variable Neighborhood Search) mejora un programa cambiando sistemáticamente la estructura de vecindad, que es lo que le permite salir de los óptimos locales en los que una sola vecindad lo atraparía.
• ILS (Iterated Local Search) perturba una buena solución lo justo para salir de su zona de atracción y vuelve a intensificar con búsqueda local.

El ciclo es sencillo de enunciar: construir con GRASP, mejorar con VNS, evaluar tardanza y factibilidad, perturbar con ILS cuando el progreso se estanca, conservar el mejor, repetir hasta que se cumpla una regla de parada: un máximo de iteraciones, una racha sin mejora o la convergencia dentro de una tolerancia. El valor del híbrido está en los traspasos entre etapas: la construcción aporta diversidad, la búsqueda local aporta calidad, la perturbación aporta persistencia.

Medirlo como corresponde

Las metaheurísticas son estocásticas, así que una sola buena ejecución no demuestra nada. La evaluación siguió la tardanza total, el tiempo de convergencia y la estabilidad de los resultados entre ejecuciones repetidas, sobre un conjunto de instancias de benchmark adaptadas (la familia Ta01–Ta53). Las diferencias entre estrategias se contrastaron con un test de Tukey en vez de a ojo: la pregunta no era "qué número es menor" sino "si la diferencia es mayor que el ruido".

El resultado principal, tal como lo publica el case study: los enfoques híbridos superaron de forma consistente a las estrategias de un solo método, y GRASP combinado con VNS dio el mejor equilibrio entre calidad del programa y tiempo de cómputo. Frente al método de referencia (búsqueda local más EDD), el póster del case study reporta una mejora media de la tardanza total de aproximadamente un tercio en el conjunto de instancias. Los diagramas de Gantt del repositorio muestran cómo se ve eso en un programa de diez máquinas.

Lo que el estudio no afirma

Esta es la parte que vale la pena leer dos veces, porque es la que suele caerse cuando una investigación se convierte en pieza de portafolio.

• Las instancias son benchmarks adaptados, no datos de una planta real. Derivar instancias de una planta en operación se identificó como el siguiente paso natural y no se hizo: exige un levantamiento de datos completo sobre una operación en marcha.
• Los resultados son comparativos, no absolutos. Sostienen conclusiones sobre el comportamiento relativo de GRASP, VNS e ILS bajo restricciones de precedencia en estas instancias. No establecen garantías de desempeño en ningún sistema industrial concreto.
• No hay publicación. El trabajo se envió a una revista con revisión por pares y no se publicó: los revisores pidieron justamente las instancias de planta real descritas arriba, y esa extensión no se llevó a cabo.

Nada de eso hace menos real la ingeniería. Hace que las afirmaciones tengan el tamaño correcto.

Tres lecciones

• Optimiza el objetivo que la planta siente. El makespan es elegante; la tardanza es lo que ve el cliente.
• Hibrida por función, no por moda. Cada componente se gana su sitio haciendo algo que los demás no pueden: diversificar, intensificar, escapar.
• Valida con estadística y declara los límites. Un test de Tukey y una sección de alcance honesta valen más que un número de titular.

La metodología, el contexto industrial, los resultados y las limitaciones están documentados en el repositorio público del case study.