Joint Planning of Assembly Sequence Planning and Assembly Line Balancing Based on Improved Artificial Fish Swarm Algorithm

Resumen Técnico: Planificación Conjunta de la Secuencia de Ensamblaje y el Balanceo de la Línea de Ensamblaje Basada en un Algoritmo Mejorado de Enjambre de Peces Artificiales

Planteamiento del Problema
El artículo aborda el complejo desafío de optimizar simultáneamente la Planificación de la Secuencia de Ensamblaje (ASP, por sus siglas en inglés) y el Balanceo de la Línea de Ensamblaje (ALB). Estos dos problemas están intrínsecamente acoplados; la ASP determina el orden óptimo para ensamblar los componentes con el fin de minimizar los costos, mientras que la ALB asigna estas tareas a estaciones de trabajo para minimizar el tiempo de inactividad y balancear la línea. Ambos se clasifican como problemas de Complejidad Polinómica No Determinista (NP-hard) con complejidad polinómica. Los autores señalan que optimizar estos problemas por separado a menudo conduce a un rendimiento subóptimo del sistema global. Además, los métodos existentes para la ASP suelen sufrir de "explosión combinatoria" cuando utilizan la búsqueda en grafos, y los métodos tradicionales de generación de matrices pueden ser lentos e ineficientes para productos complejos. Adicionalmente, muchos estudios de ALB no tienen en cuenta los cambios dinámicos en las herramientas y direcciones de ensamblaje inherentes a la ASP, lo que resulta en resultados de balanceo que pueden ser impracticables en los procesos de ensamblaje reales.

Metodología
El enfoque propuesto integra la ASP y la ALB en un marco de optimización multiobjetivo unificado utilizando un Algoritmo de Enjambre de Peces Artificiales Híbrido (HAFSA). La metodología se estructura en tres fases principales:

1. Modelado de ASP mediante BOM y Matriz de Restricciones:

   • En lugar de depender únicamente de grafos AND/OR que causan explosión combinatoria, los autores construyen una matriz de restricciones de ensamblaje modular basada en el diagrama jerárquico de la Lista de Materiales (BOM).
   • La matriz de restricciones de ensamblaje ($E(G)$) se define mediante un grafo dirigido donde los elementos representan piezas y los valores indican la prioridad y las relaciones de conexión (por ejemplo, $1$ para conexión directa antes, $-1$ para después, $9$ para conexión no directa antes, etc.).
   • Partición de Subensamblajes: Un algoritmo analiza la jerarquía de la BOM para determinar la independencia de los subensamblajes. Verifica iterativamente los valores de las columnas en la matriz de restricciones; si un grupo de piezas muestra relaciones consistentes no positivas o no negativas con piezas externas, se identifican como subensamblajes independientes. Si no es así, el algoritmo desprende filas específicas para crear módulos independientes factibles.
   • Planificación Interna: Dentro de cada subensamblaje identificado, se utiliza un algoritmo de intercambio y solidificación específico para generar secuencias de ensamblaje internas factibles basadas en los valores de la matriz de restricciones.

2. Modelo de Optimización Multiobjetivo:
   El modelo integrado busca minimizar tres funciones objetivo simultáneamente:

   • Balance de Tiempo de la Estación de Trabajo: Minimizar la varianza entre el ritmo de producción ($T_c$) y los tiempos individuales de las estaciones de trabajo ($T_m$).
   • Costos de Cambio: Minimizar el número total de cambios de herramientas de ensamblaje y cambios de dirección de ensamblaje entre tareas consecutivas.
   • Tiempo Máximo de la Estación de Trabajo: Minimizar el tiempo de ciclo (el tiempo máximo entre todas las estaciones de trabajo).

3. Algoritmo de Enjambre de Peces Artificiales Híbrido (HAFSA):
   Para resolver este problema multiobjetivo, los autores proponen un HAFSA que combina el Algoritmo de Enjambre de Peces Artificiales (AFSA) con la Optimización por Enjambre de Partículas (PSO) y conceptos de optimalidad de Pareto.

   • Codificación/Decodificación: Las tareas de ensamblaje se codifican basándose en los pesos de prioridad dentro de los subensamblajes. La decodificación asigna las tareas a las estaciones de trabajo secuencialmente, abriendo nuevas estaciones de trabajo solo cuando se excede la restricción del tiempo de ciclo.
   • Conjunto de Soluciones de Pareto: Un repositorio externo almacena soluciones no dominadas. Se utiliza un mecanismo de distancia de apiñamiento (crowding distance) para mantener la diversidad y gestionar el tamaño del repositorio.
   • Mejoras del Algoritmo:
     • Lógica de Comportamiento: El algoritmo sigue un orden de búsqueda serial: persecución de la cola, búsqueda de alimento, agrupamiento y comportamiento aleatorio.
     • Integración de PSO: Para evitar que el algoritmo caiga en óptimos locales (una debilidad conocida del AFSA estándar), se introducen operaciones de PSO. Esto incluye el uso de un criterio de Metropolis (concepto de recocido simulado) para aceptar soluciones que se deterioran con cierta probabilidad, permitiendo que la búsqueda escape de trampas locales.
     • Inercia Dinámica: El "campo visual" (rango de búsqueda) de los peces artificiales se ajusta dinámicamente utilizando un peso de inercia ($\omega$) inspirado en PSO, comenzando con un campo grande para la exploración global y estrechándose para la convergencia local.

Contribuciones Clave

• Marco Integrado: El artículo propone un método para planificar conjuntamente la ASP y la ALB en lugar de tratarlas secuencialmente, reconociendo su interdependencia.
• Identificación de Subensamblajes Basada en Matrices: Un enfoque novedoso que utiliza la jerarquía de la BOM y la matriz de restricciones de ensamblaje para identificar automáticamente subensamblajes independientes, reduciendo el espacio de búsqueda y evitando la explosión combinatoria.
• Algoritmo HAFSA: El desarrollo de un Algoritmo de Enjambre de Peces Artificiales Híbrido basado en Pareto que mejora al AFSA estándar incorporando operaciones de PSO y principios de recocido simulado para mejorar las capacidades de búsqueda global y evitar los óptimos locales.
• Manejo Multiobjetivo: La inclusión explícita de los cambios de herramienta y los cambios de dirección como objetivos de optimización junto con el balanceo de tiempo tradicional.

Resultos
El método propuesto fue validado mediante un estudio de caso de un producto específico con 21 tareas de ensamblaje. Se comparó el HAFSA (etiquetado como AFSA&PSO) contra un algoritmo de Optimización por Enjambre de Partículas (PSO) estándar y un Algoritmo de Enjambre de Peces Artificiales (AFSA) estándar.

• Balance de Estación de Trabajo: Los tres algoritmos lograron el mismo tiempo máximo de operación de la estación de trabajo de 31 minutos. Sin embargo, el valor de balance entre estaciones para el HAFSA fue de 0.69, lo cual fue superior al resultado del PSO (0.75) e igual al AFSA estándar (0.69).
• Eficiencia de Cambio: El HAFSA logró un total de 22 cambios (herramienta + dirección). Esto fue igual al resultado del PSO (22) pero significativamente mejor que el AFSA estándar, que resultó en 24 cambios.
• Conclusión de los Datos: El HAFSA demostró la capacidad de encontrar una solución de Pareto-óptima que equilibra eficazmente los tiempos de estación mientras minimiza el número total de cambios operativos, superando al AFSA estándar en la reducción de cambios y igualando o superando al PSO en las métricas de balance.

Significancia y Reivindicaciones
El artículo afirma que su principal significancia radica en mejorar la eficiencia y la viabilidad de la planificación conjunta de ASP y ALB. Al utilizar la jerarquía de la BOM para el preprocesamiento de los subensamblajes, el método hace que el espacio de búsqueda sea más dirigido, mejorando así la eficiencia de la solución y evitando la generación de un gran número de soluciones inviables.

Los autores aseguran que el HAFSA propuesto es más efectivo que los algoritmos tradicionales AFSA y PSO para este problema multiobjetivo específico. La integración de las operaciones de PSO en el comportamiento del enjambre de peces permite que el algoritmo escape mejor de los óptimos locales, resultando en soluciones de Pareto de mayor calidad. El estudio concluye que este enfoque integrado proporciona un método de planificación más razonable y eficiente para las líneas de ensamblaje de productos complejos, particularmente donde los cambios de herramienta y dirección son factores de costo críticos.