Métodos Heurísticos: Balanceo de Líneas

La sección introduce el concepto de líneas de ensamblaje, su origen en la Revolución Industrial con las contribuciones de Adam Smith, Frederick W. Taylor y Henry Ford, y su evolución hasta el problema actual de balanceo. Se define una línea de ensamblaje como una serie de estaciones de trabajo donde se realizan tareas en un tiempo determinado, siguiendo un orden específico dictado por las relaciones de precedencia. Se mencionan las variantes del Problema Simple de Balanceo de Líneas de Ensamblaje (SALBP): SALBP-1 (minimizar el número de estaciones dado un tiempo de ciclo), SALBP-2 (minimizar el tiempo de ciclo dado un número de estaciones), SALBP-E (minimizar el producto del número de estaciones y el tiempo de ciclo), y SALBP-F (determinar la factibilidad de una solución dada). Se destaca la importancia del trabajo de Miralles et al. (2007) que, a través de un estudio de caso en un centro de trabajo para discapacitados en España, abrió nuevas vías de investigación en este ámbito, conectando la optimización de procesos de manufactura con la inclusión social. Este estudio inicial sentó las bases para la investigación posterior en el Problema de Balanceo de Línea de Ensamblaje y Asignación de Trabajadores (ALWABP), una generalización del SALBP que incorpora la asignación de trabajadores como una nueva variable de decisión, donde los tiempos de ejecución de las tareas son dependientes del trabajador y donde algunos trabajadores podrían no ser capaces de realizar ciertas tareas. La complejidad del ALBP y la necesidad de métodos eficientes para su resolución, especialmente considerando que es un problema NP-duro, se plantean como una justificación central de la investigación. El documento se centra en el ALWABP tipo II que busca minimizar el tiempo de ciclo dado un número fijo de estaciones.

Esta parte del documento profundiza en las características del ALWABP. Se establece que, a diferencia del SALBP, en el ALWABP la asignación de trabajadores a las estaciones se convierte en una variable crucial en el proceso de balanceo. Cada trabajador tiene un tiempo de ejecución específico para cada tarea, y en algunos casos un trabajador podría no poder realizar una tarea en absoluto (tiempo de ejecución infinito). Se define la notación para representar el conjunto de sucesores de una tarea (Fi*). El objetivo del modelo ALWABP-II es minimizar el tiempo de ciclo, dado un número fijo de estaciones, sujeto a dos restricciones fundamentales: cada estación cuenta con un único trabajador capaz de realizar todas las tareas asignadas a esa estación, y cada tarea es asignada a una y solo una estación donde puede ser ejecutada. Se hace referencia a trabajos previos que han explorado el ALWABP en sus tipologías I y II, mostrando el interés creciente en este tipo de problema. También se discute la ineficiencia de los métodos exactos para resolver problemas combinatorios de gran envergadura, especialmente aquellos catalogados como NP-completos, debido al tiempo computacionalmente excesivo que requieren y la gran cantidad de variables que implican. Se introduce, en este punto, el concepto de heurísticas y su utilidad para encontrar soluciones factibles en tiempo razonable, aunque no necesariamente óptimas. Se menciona la búsqueda de soluciones dentro del espacio de soluciones factibles.

La sección de antecedentes contextualiza el ALWABP dentro de un marco más amplio de problemas de optimización combinatoria en el ámbito empresarial. Se destaca la búsqueda de soluciones que optimizan recursos y mejoren continuamente los estándares de calidad y tiempos de producción. Se enfatiza que el ALWABP es una variante del ALBP general y comparte elementos esenciales con este, pero se diferencia por la consideración explícita de la asignación de trabajadores a las estaciones. Se mencionan algunos métodos heurísticos y exactos que se han utilizado para resolver el SALBP y sus variantes en las últimas seis décadas, clasificándolos en métodos basados en prioridad y procedimientos enumerativos restringidos, por un lado; y enfoques branch and bound y programación dinámica, por otro. Se citan trabajos relevantes, incluyendo el de Blum & Miralles (2011) que compararon un algoritmo Beam Search con trabajos previos, y el de Moreira et al. (2012) que propusieron heurísticas simples para el problema. Se hace mención también al trabajo de Vilà y Pereira (2013) que desarrollaron nuevos límites inferiores para algoritmos Branch and Bound. Se describe la evolución del problema ALWABP, incluyendo el trabajo de Moreira et al. (2015) sobre la integración de trabajadores discapacitados a una línea de ensamblaje, y el de Zacharia y Nearchou (2016) que abordan el problema multi-objetivo. Finalmente, se introducen los métodos constructivos y los métodos de búsqueda dentro de la categoría de heurísticas, junto con las metaheurísticas, que se presentan como una alternativa más sofisticada que ayuda a evitar los óptimos locales.

El documento inicia esta sección reconociendo la ineficiencia de los métodos exactos para resolver problemas combinatorios de gran escala, como el ALWABP. Se argumenta que el tiempo requerido para encontrar una solución óptima mediante métodos exactos es inaceptable y que el espacio de búsqueda es enorme. Esto se fundamenta en la cita de Duarte Muñoz et al. (2007). Como solución a esta limitación computacional, se introduce el concepto de heurísticas o métodos aproximados. Se explica que las heurísticas permiten encontrar soluciones factibles, aunque no necesariamente óptimas, en un tiempo computacionalmente aceptable. Se destaca que estas soluciones factibles pueden luego ser evaluadas para encontrar la mejor entre ellas. La discusión luego se centra en las limitaciones inherentes a las heurísticas simples, particularmente la tendencia a quedar atrapadas en óptimos locales. Esta limitación se aborda con la introducción de las metaheurísticas, que son métodos de búsqueda más sofisticados que guían los procesos heurísticos para evitar este problema.

Se presenta la propuesta central del trabajo: el uso de dos algoritmos diferentes para resolver el ALWABP, cada uno basado en una estrategia metodológica distinta. El primer algoritmo se basa en una metaheurística GRASP (Greedy Randomized Adaptive Search Procedure), combinada con una metaheurística VND (Variable Neighborhood Descent). La metaheurística GRASP se utiliza en la fase constructiva para obtener una solución factible inicial, mientras que la VND se emplea en la fase de mejora para buscar soluciones mejores en la vecindad de la solución inicial. El segundo algoritmo propone un enfoque innovador al utilizar una matheurística, que integra una metaheurística (GRASP) con un método exacto. Esta combinación aprovecha las ventajas de ambos enfoques: la capacidad de la metaheurística para explorar rápidamente un amplio espacio de soluciones y la capacidad del método exacto para garantizar la optimalidad local. La originalidad de estos enfoques se resalta al mencionar que ninguno de los trabajos previos había utilizado estas combinaciones específicas de métodos para abordar este problema, aunque sí se habían explorado otros métodos metaheurísticos y exactos por separado. Se introduce el concepto de vecindad en el contexto de las metaheurísticas y se explica brevemente la estrategia determinista de cambio de vecindad en el procedimiento VND.

Antes de presentar los algoritmos aproximados, el documento describe el intento de resolver el problema ALWABP-2 utilizando un método exacto con el software de optimización CPLEX y el lenguaje de modelado AMPL (Fourer et al., 2003). Se explica que este enfoque se utilizó para obtener una referencia de soluciones óptimas y evaluar el desempeño de las metodologías aproximadas. Se observa que para instancias pequeñas (familias Rozieg y Heskia), CPLEX encontró la solución óptima global en todas las 160 instancias probadas. Sin embargo, para instancias de mayor tamaño (familias Tongue y Wee-Mag), el tiempo de computación de CPLEX fue excesivo (alrededor de 6 horas), lo que llevó a limitar el tiempo de ejecución a 3600 segundos. Esta limitación en el tiempo de procesamiento para las instancias más grandes evidenció la dificultad de los métodos exactos para manejar problemas NP-hard, donde la complejidad computacional aumenta drásticamente con el tamaño del problema, haciendo que este enfoque sea poco práctico para instancias de gran escala. Esta ineficiencia justifica el uso de las heurísticas y metaheurísticas en el estudio.

Para evaluar el rendimiento de los algoritmos propuestos, se utilizaron instancias del problema ALWABP generadas a partir de instancias existentes del SALBP. Se mantuvieron los diagramas de precedencia originales, asignándose los tiempos de ejecución originales al trabajador número 1, mientras que los tiempos para los trabajadores adicionales se generaron aleatoriamente a partir de los tiempos originales (Blum & Miralles, 2011). Las familias de instancias usadas fueron Rozieg, Heskia, Tongue y Wee-Mag, con detalles adicionales disponibles en Scholl (1976). Se utilizaron un total de 320 instancias (80 por familia), agrupadas en 8 conjuntos de 10 instancias cada uno, mismas que fueron previamente utilizadas por Chaves et al. (2007) para la verificación de su propio algoritmo. La metodología implicó la ejecución repetida de cada algoritmo un número determinado de veces, registrándose los mejores resultados obtenidos en todas las repeticiones. La presencia de tiempos de ejecución infinitos en algunas instancias se manejó de una manera que se detallará más adelante. Se utilizaron gráficos para visualizar los resultados, mostrando dos grupos de 10 instancias para cada caso de número de trabajadores en cada familia.

La sección presenta los resultados obtenidos por el algoritmo basado en la metaheurística GRASP combinada con VND. Se describe el comportamiento del algoritmo, mostrando una gráfica que ilustra la búsqueda de soluciones. Cada pico en la gráfica representa una asignación diferente de tareas y trabajadores, y cada punto indica un movimiento de mejora. Se compararon los resultados con otros métodos, incluyendo IBS y MP, observándose que para las familias Rozieg y Heskia, con un menor número de estaciones, el algoritmo obtuvo soluciones óptimas en la mayoría de las instancias. Sin embargo, en grupos con mayor número de estaciones, se observó un mayor porcentaje de error. Se menciona que el algoritmo utilizó un enfoque first improvement, donde se ejecutaba el primer movimiento de mejora encontrado y se cambiaba de vecindad. El tiempo de ejecución se limitó a 34200 segundos por instancia, debido a la alta duración del proceso en algunas familias de instancias más grandes. A pesar del buen desempeño en algunas instancias, se observó que el método tiene un desempeño inferior a IBS y MP, lo que justifica la búsqueda de un enfoque alternativo.

Los resultados del algoritmo matheurístico se comparan con los resultados del algoritmo metaheurístico y con los métodos IBS y MP. Se destaca que en las familias Rozieg y Heskia, el método matheurístico encontró las soluciones óptimas, coincidiendo con los resultados del método exacto (CPLEX). Para las familias Tongue y Wee-Mag, el método exacto no pudo encontrar la solución óptima dentro del tiempo límite, por lo que la comparación se realiza con los resultados aproximados. Se observa que el algoritmo matheurístico obtuvo mejores resultados que el metaheurístico en todas las instancias evaluadas, especialmente en términos de tiempo de ciclo. En las familias de instancias Tongue y Wee-Mag, el método matheurístico demostró ser competitivo con el método IBS, registrando mejoras significativas (5% en el grupo 1 y 3.5% en el grupo 3 de la familia Wee) en comparación con el método IBS. Aunque el algoritmo matheurístico no siempre encuentra la solución óptima global del ALWABP-2 en las familias grandes, se encontró que resuelve de manera óptima el subproblema SALBP-2. El enfoque de relajación del problema original a su versión más simple, combinada con el método exacto, permite obtener soluciones óptimas para cada asignación de trabajadores probada. La eficiencia del algoritmo radica en la capacidad de seleccionar, entre las múltiples posibilidades de asignación de trabajadores, aquella que conduce a la mejor solución de manera rápida.

Esta sección presenta la comparación de los resultados obtenidos por los dos algoritmos propuestos (metaheurístico y matheurístico) con métodos previamente existentes en la literatura, específicamente IBS y MP. La evaluación se realiza sobre las cuatro familias de instancias (Rozieg, Heskia, Tongue y Wee-Mag). Para las familias Rozieg y Heskia, que presentan un menor número de estaciones, el algoritmo matheurístico consigue alcanzar las soluciones óptimas encontradas tanto por el método exacto (CPLEX) como por el método MP, mientras que el algoritmo metaheurístico también se acerca a dichas soluciones óptimas en la mayoría de los casos para grupos con un menor número de estaciones. Sin embargo, en los grupos con un mayor número de estaciones, el porcentaje de error aumenta en ambos algoritmos. En las familias Tongue y Wee-Mag, de mayor complejidad, donde el método exacto no logró obtener soluciones óptimas en un tiempo razonable, la matheurística demostró ser la más competitiva, superando al método metaheurístico en todas las instancias y mostrando un rendimiento comparable al método IBS, con mejoras promedio de hasta un 5% en la familia Wee para grupos con menor número de estaciones. Se destaca que, aunque el algoritmo matheurístico no siempre alcanza la solución óptima global del ALWABP-2 en instancias grandes, sí encuentra la solución óptima del subproblema SALBP-2 para todas las soluciones evaluadas. Esto se debe a la simplificación del problema original mediante la relajación de variables.

El análisis de los resultados se centra en la comparación entre ambos algoritmos, resaltando la superioridad del método matheurístico en términos de eficiencia y calidad de la solución. Se discuten las limitaciones de cada uno de los algoritmos. En el caso del algoritmo metaheurístico, la estrategia first improvement puede impedir la exploración de todas las combinaciones posibles de trabajadores, afectando el desempeño en instancias más complejas. La limitación de tiempo impuesta en la ejecución de los algoritmos (34200 segundos) también pudo afectar la capacidad de exploración del espacio de búsqueda, especialmente en las familias de instancias más numerosas. Se analiza el tiempo de ejecución de ambos algoritmos, observándose que el algoritmo matheurístico, aunque superior en calidad de la solución, no siempre supera en tiempo de ejecución al método IBS en los grupos de mayor tamaño. Se recalca que la diferencia en los tiempos de ciclo entre los métodos metaheurístico y matheurístico es notable en todas las instancias evaluadas, con el método matheurístico siempre presentando valores menores. En familias como Rozieg y Heskia, el método matheurístico logró encontrar los valores óptimos, coincidiendo con los resultados del método exacto, lo cual subraya su eficiencia y precisión en estas instancias. La incapacidad del método exacto para resolver las familias Tongue y Wee en un tiempo razonable refuerza la necesidad de métodos aproximados eficientes como el matheurístico propuesto.

La conclusión principal del trabajo destaca la superioridad del algoritmo basado en matheurísticas sobre el algoritmo metaheurístico y otros métodos de la literatura (IBS, MP) para resolver el problema ALWABP-2. Se concluye que la combinación de un método exacto (CPLEX) con una metaheurística (GRASP) ofrece una solución eficiente y competitiva. Finalmente, se presentan sugerencias para futuras líneas de investigación. Se propone la mejora del algoritmo matheurístico mediante la implementación de una metaheurística GRASP reactiva, que utilizaría una memoria para guardar los valores de alfa que hayan resultado en soluciones de alta calidad, mejorando la eficiencia en la búsqueda de soluciones. Para el algoritmo metaheurístico, se sugieren alternativas como la exploración de otros criterios miopes para la asignación de tareas a estaciones y la sustitución del método VND por un método VNS (Variable Neighborhood Search) o BVNS (Best Variable Neighborhood Search) para optimizar la fase de mejora. La combinación de métodos exactos y heurísticos se presenta como una estrategia prometedora para abordar eficientemente problemas de optimización combinatoria complejos como el ALWABP.