💻 ciencias de la computación

A Block-Guided Artificial Bee Colony Algorithm for Distributed Assembly Flowshop Scheduling with Sequence-Dependent Setup Times

Este artículo propone un algoritmo de Colonia de Abejas Artificiales Guiado por Bloques (BG-ABC) que integra un mecanismo de compresión de bloques consciente de la inactividad, una selección de operadores adaptativa de Ventana Deslizante de Límite Superior de Confianza 1 (SW-UCB1) y una búsqueda local enfocada en trabajos críticos para minimizar eficazmente la rampa de finalización (makespan) para el Problema de Programación de Flujo de Permutación de Ensamblaje Distribuido con Tiempos de Preparación Dependientes de la Secuencia (DAPFSP-SDST).

Autores originales: Ji-Feng Xu, Hong-Bo Song

Publicado 2026-10-30

📖 4 min de lectura☕ Lectura para el café

CC BY 4.0

Autores originales: Ji-Feng Xu, Hong-Bo Song

Artículo original bajo licencia CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

En el vasto e interconectado mundo de la fabricación moderna, el viaje de un producto a menudo no comienza en una sola fábrica, sino a través de una red de instalaciones especializadas dispersas por todo el globo. Imagine un automóvil siendo construido donde los motores se fabrican en un país, la electrónica en otro y el ensamblaje final ocurre en un tercero. Este enfoque distribuido ofrece flexibilidad y eficiencia, pero crea un rompecabezas logístico masivo. El desafío radica en decidir qué fábrica debe construir cada pieza, en qué orden deben procesarse esas piezas y, finalmente, cómo traerlas todas para el ensamblaje. Complicando esto aún más está la realidad de que las máquinas no siempre están listas para trabajar de inmediato; requieren tiempo para limpiar, cambiar herramientas o ajustar accesorios entre tareas. El tiempo necesario para esta preparación a menudo depende enteramente de qué trabajo se acaba de terminar y cuál es el siguiente. Esta naturaleza "dependiente de la secuencia" significa que un pequeño cambio en el orden de trabajo puede repercutir en todo el sistema, alterando drásticamente cuánto tiempo toma terminar todo. Resolver este rompecabezas es crítico para industrias que van desde la automotriz hasta la de muebles, ya que encontrar el programa más eficiente impacta directamente en los costos, los tiempos de entrega y la capacidad de satisfacer la demanda del cliente.

Los investigadores Ji-Feng Xu y Hong-Bo Song han abordado este complejo problema de programación mediante el desarrollo de un nuevo método computacional que imita el comportamiento de forrajeo de las abejas melíferas para encontrar los mejores programas de producción posibles. Su enfoque, diseñado específicamente para escenarios donde los tiempos de configuración varían según el orden de los trabajos, se centra en minimizar el tiempo total requerido para completar todos los productos, conocido como makespan. El equipo observó que en los programas más eficientes, ciertos pares de productos aparecen consistentemente uno al lado del otro porque requieren la menor cantidad de tiempo de configuración y no dejan tiempo de espera ocioso para la máquina de ensamblaje. Para aprovechar esto, crearon un sistema que identifica estos pares ideales y los bloquea juntos en "bloques" fijos, tratándolos como unidades individuales durante la búsqueda de una solución. Esta estrategia reduce efectivamente el enorme número de programas posibles a un conjunto mucho más pequeño y manejable, permitiendo que la computadora concentre su energía en las disposiciones más prometedoras en lugar de perder tiempo en combinaciones improbables.

Sin embargo, bloquear estos bloques conlleva un riesgo: el algoritmo podría quedarse estancado en un óptimo local, perdiendo una mejor solución que requiera separar un bloque. Para prevenir esto, los investigadores integraron un sistema de selección dinámica en la fase de "abeja empleada" del algoritmo. Este sistema actúa como un gerente inteligente que observa qué estrategias de búsqueda están funcionando mejor en el momento actual y desvía su atención en consecuencia, en lugar de aferrarse a un plan rígido. Cuando el algoritmo se queda estancado, un mecanismo de "abeja exploradora" interviene para disolver los bloques bloqueados y reconstruir el programa desde cero, asegurando que la búsqueda continúe explorando nuevas posibilidades. Además, los investigadores se dieron cuenta de que no todas las partes del programa necesitan el mismo nivel de atención. Dirigieron el algoritmo para que centrara sus esfuerzos de búsqueda detallada solo en la secuencia específica de trabajos que están causando cuellos de botella, ignorando las partes del programa que ya están funcionando sin problemas. Este enfoque dirigido ahorra una potencia de cálculo significativa, permitiendo que el sistema evalúe más soluciones potenciales en el mismo tiempo.

El equipo probó su nuevo método, al que llaman algoritmo de Colonia de Abejas Artificial guiada por Bloques (Block-Guided Artificial Bee Colony), contra una amplia gama de problemas de referencia estándar utilizados por investigadores en el campo. Estas pruebas involucraron miles de escenarios diferentes con distintos números de fábricas, máquinas y productos. Los resultados mostraron que su método superó consistentemente a los algoritmos de vanguardia existentes, encontrando programas que eran significativamente más cortos en duración. Al combinar la eficiencia de agrupar pares de productos ideales con la adaptabilidad de una búsqueda inspirada en las abejas, los investigadores demostraron una forma robusta de manejar la intrincada coordinación requerida en las cadenas de suministro modernas. Su trabajo sugiere que, al comprender los patrones estructurales específicos de estos problemas de programación, es posible diseñar herramientas inteligentes que hagan que las complejas redes de fabricación global funcionen de manera más fluida y eficiente.

Resumen Técnico: Un Algoritmo de Colonia de Abejas Artificiales Guiado por Bloques para la Programación de Flujo de Ensamblaje Distribuido con Tiempos de Configuración Dependientes de la Secuencia

Definición del Problema
Este artículo aborda el Problema de Programación de Flujo de Ensamblaje de Permutación Distribuida con Tiempos de Configuración Dependientes de la Secuencia (DAPFSP-SDST). El problema modela una cadena de suministro de múltiples etapas donde $n$ trabajos son procesados a través de $f$ fábricas idénticas, cada una con $m$ máquinas en una configuración de flujo de taller (flowshop). Al completarse, los trabajos son transportados a una instalación centralizada para ser ensamblados en $d$ productos en una única máquina de ensamblaje. El objetivo es minimizar la fecha de finalización total o makespan ( $C_{max}$ ).

Una complejidad crítica de este problema es la inclusión de Tiempos de Configuración Dependientes de la Secuencia (SDST) tanto en la etapa de fabricación como en la de ensamblaje. En la etapa de fabricación, los tiempos de configuración dependen de los trabajos consecutivos dentro de una fábrica; en la etapa de ensamblaje, dependen de los productos consecutivos. Se identifica que el problema es fuertemente NP-duro, lo que requiere la optimización simultánea de la asignación de trabajos a fábricas, la secuenciación de trabajos dentro de las fábricas y la secuenciación de ensamblaje de productos.

Metodología: El Algoritmo BG-ABC
Los autores proponen un algoritmo de Colonia de Abejas Artificiales Guiado por Bloques (BG-ABC). El diseño se fundamenta en la observación de que minimizar el makespan es equivalente a minimizar la suma del tiempo total de configuración de ensamblaje (TSTA) y el tiempo total de inactividad de ensamblaje (TITA). Las soluciones de alta calidad presentan frecuentemente pares de productos adyacentes que logran simultáneamente un SDST mínimo y un tiempo de inactividad de ensamblaje de cero.

El algoritmo integra cuatro mecanismos específicos en el marco estándar de ABC:

Compresión de Bloques Consciente de la Inactividad:
El algoritmo identifica "bloques compresibles", definidos como pares de productos consecutivos $(\pi_l, \pi_{l+1})$ donde $\pi_{l+1}$ es el sucesor de SDST-mínimo de $\pi_l$ y el tiempo de inactividad entre ellos es cero. Estos pares se bloquean en bloques atómicos. El espacio de búsqueda se reduce de permutaciones de productos individuales a permutaciones de estos bloques, reduciendo significativamente la dimensionalidad del espacio de búsqueda mientras se preservan patrones estructurales prometedores.
Selección Adaptativa de Operadores (SW-UCB1):
En la fase de abeja empleada, el algoritmo opera sobre la secuencia de bloques comprimidos utilizando tres operadores de vecindad: Intercambio (Swap), Inserción e Inversión. Para seleccionar dinámicamente el operador más efectivo a medida que avanza la búsqueda, se emplea un esquema de Ventana Deslizante de Límite Superior de Confianza 1 (SW-UCB1). Este mecanismo rastrea las recompensas recientes de cada operador dentro de una ventana deslizante, permitiendo que el algoritmo adapte su estrategia de búsqueda sin la compleja sintonización de parámetros requerida por el Q-learning.
Búsqueda Local de la Subsecuencia de Trabajos Críticos (CJS):
En la fase de abeja observadora, la búsqueda local se restringe a la "Subsecuencia de Trabajos Críticos" (CJS). Basándose en la observación de que los tiempos de inactividad para los productos que aparecen después del último tiempo de inactividad positivo no pueden reducirse más, el algoritmo concentra el esfuerzo computacional únicamente en el prefijo de la secuencia de productos (la Secuencia Crítica de Productos) que contiene tiempos de inactividad positivos. Se utiliza una estrategia de evaluación de dos niveles: una evaluación parcial rápida de los primeros $K$ productos filtra a los candidatos antes de que se dispare una evaluación completa del makespan, reduiendo la carga computacional.
Refinamiento y Reconstrucción (Fase de Abeja Exploradora/Scout):
Para contrarrestar el riesgo de convergencia prematura causado por la compresión de bloques, se implementa un mecanismo de abeja exploradora. Si un individuo se estanca más allá de un umbral $\theta$ , el algoritmo primero intenta un refinamiento dirigido mediante el descenso de vecindad en productos no críticos y el CJS. Si no se encuentra mejora, el algoritmo realiza un reinicio estructural: disuelve los bloques bloqueados, permuta aleatoriamente los productos restantes y mezcla los órdenes de los trabajos dentro de los productos, restaurando así la diversidad estructural y escapando de los óptimos locales.

Contribuciones Clave
El artículo reclama cuatro contribuciones primarias:

Perspectiva Estructural: La propuesta de un mecanismo de compresión de bloques consciente de la inactividad que bloquea pares de productos de SDST-mínimo y cero inactividad en bloques atómicos, reduciendo efectivamente la dimensionalidad del espacio de búsqueda.
Selección Adaptativa: La integración del esquema SW-UCB1 para seleccionar dinámicamente los operadores de vecindad basados en el rendimiento reciente, mejorando la adaptabilidad de la búsqueda.
Explotación Enfocada: La restricción de la búsqueda local a la Subsecuencia de Trabajos Críticos combinada con una estrategia de evaluación de dos niveles, lo que concentra los recursos computacionales en las regiones de cuello de botella del programa.
Gestión del Estancamiento: El diseño de un mecanismo de refinamiento y reconstrucción en la fase de la abeja exploradora que aborda específicamente los riesgos de estancamiento introducidos por la compresión de bloques.

Resultados Experimentales
El algoritmo fue evaluado en 540 instancias de referencia derivadas del conjunto de datos DAPFSP-SDST de Hatami et al. [7], cubriendo diversas escalas de problemas ( $n \in \{100, 200\}$ , $m \in \{5, 10, 20\}$ , $f \in \{4, 6, 8\}$ , $d \in \{30, 40, 50\}$ ).

Comparación: BG-ABC se comparó contra cuatro algoritmos de vanguardia: Búsqueda Ávida Iterada (IG), Hiper-heurística de Programación Genética (GP-HH), Optimización de Biogeografía Novel (NBBO) y Algoritmo de Dos Etapas (TSHA).
Desempeño: BG-ABC logró la Desviación Porcentual Relativa Promedio (ARPD) más baja de -1.95%, superando significativamente a TSHA (-1.28%), NBBO (-1.32%), GP-HH (-0.49%) e IG (0.81%). El análisis estadístico utilizando la prueba de Friedman y la prueba post-hoc de Bonferroni-Dunn confirmó que la superioridad de BG-ABC es estadísticamente significativa tanto al 95% como al 99% de nivel de confianza.
Estudio de Ablación: Se probaron variantes de BG-ABC carentes de componentes específicos (compresión de bloques, selección adaptativa, búsqueda CJS o reconstrucción guiada). El BG-ABC completo superó significativamente a todas las variantes, confirmando que cada componente no es redundante y contribuye al desempeño general.

Significancia y Reclamaciones
El artículo afirma que el algoritmo BG-ABC proporciona una herramienta de optimización inteligente práctica y robusta para entornos de cadena de suministro de múltiples etapas. Su significancia radica en haber embebido con éxito conocimientos estructurales específicos del problema (específicamente la relación entre SDST, tiempo de inactividad y formación de bloques) en una metaheurística basada en población. Al equilibrar la profundidad de búsqueda y el costo computacional mediante la compresión de bloques y la búsqueda local enfocada, el algoritmo supera las limitaciones de las heurísticas de descenso simple (como TSHA) y las metaheurísticas genéricas que no logran explotar plenamente las propiedades específicas del DAPFSP-SDST. Los autores concluyen que el método propuesto mejora efectivamente la eficiencia operativa y la toma de decisiones en sistemas de ensamblaje distribuidos.

Más como este