Introducción de elementos de memoria en el método simulated annealing para resolver problemas de programación multiobjetivo de máquinas paralelas

Introduction of memory elements in simulated annealing method to solve multiobjective parallel machine scheduling problems

El presente artículo introduce una variante de la metaheurística Simulated Annealing, para la resolución de problemas de optimización multiobjetivo. Este enfoque se demonina MultiObjective Simulated Annealing with Random Trajectory Search,MOSARTS. Esta técnica agrega al algoritmo Simulated Annealing elementos de memoria de corto y largo plazo para realizaruna búsqueda que permita balancear el esfuerzo entre todos los objetivos involucrados en el problema. Los resultados obtenidos se compararon con otras tres metodologías en un problema real de programación de máquinas paralelas, compuesto por 24 trabajos y 2 máquinas idénticas. Este problema corresponde a un caso de estudio real de la industria regional del aserrío.En los experimentos realizados, MOSARTS se comportó de mejor manera que el resto de la herramientas de comparación,encontrando mejores soluciones en términos de dominancia y dispersión.

INTRODUCCIÓN

Los problemas del ámbito aplicado por lo general son multiobjetivos por naturaleza. Rara vez una decisión es tomada en base a un solo criterio. Por esta razón, resulta de gran interés el desarrollo de herramientas que reflejen las necesidades industriales y que puedan entregar soluciones en un tiempo razonable. No existen algoritmos exactos que puedan resolver problemas reales con más de un objetivo en un tiempo razonable. Es por esta razón que las metaheurísticas surgen como una alternativa práctica para resolver este tipo de problemas. Simulated Annealing (SA) corresponde a una metaheurística que ha sido probada profundamente en problemas de un solo objetivo con resultados que avalan su buen desempeño en términos de eficiencia y eficacia. En el ámbito multiobjetivo no existen muchos desarrollos asociados a esta herramienta, la mayoría de los desarrollos corresponden a algoritmos genéticos (AG) multiobjetivo que presentan la ventaja de un esquema poblacional lo cual facilita el modelamiento en términos multiobjetivo, sin embargo, debido a este mismo aspecto presentan una convergencia lenta. Es por este motivo que surge como oportunidad investigar en desarrollar un algoritmo multiobjetivo basado en Simulated Annealing que sea capaz de resolver problemas de tamaño industrial en un tiempo y calidad aceptable y con mayor velocidad de convergencia que AG.

Los problemas de programación de la producción corresponden a problemas combinatorios de alta complejidad considerados en su mayoría intratables a través de algoritmos exactos. Además, estos problemas son de alta aplicabilidad en el ámbito industrial, por lo cual resultan de gran interés tanto desde una perspectiva investigativa como de transferencia tecnológica.