Resumen de Exploitation of parallelism in population-based metaheuristics and application to a galvanizing line
Diego Díaz Fidalgo
El acero es ubicuo en el mundo moderno, y una parte importante de muchos sectores económicos. El segmento del Acero Galvanizado es el mayor entre los diferentes productos de acero, dada su utilización en un amplio abanico de industrias, tales como la construcción, el automóvil, los electrodomésticos, y muchos otros.
La programación, o secuenciación, de las bobinas que se producen en una Línea de Galvanizado es extremadamente importante, puesto que tiene un gran impacto en los costes y la factibilidad de la producción.
Este problema de secuenciación es muy parecido a un Problema del Viajante (Travelling Salesperson Problem, TSP), con la complicación añadida de que algunos segmentos no son factibles. Para ciertos productos existen restricciones adicionales; estas restricciones invalidan cualquier aproximación basada en TSP, al depender de subsecuencias más largas que una bobina y su sucesora inmediata.
Las soluciones típicas para este problema se basan en programación por restricciones que depende de prioridades de las restricciones diseñadas cuidadosamente para cada línea con sus condiciones particulares y su combinación de productos.
El problema de programación de tareas (Job Scheduling Problem, JSP) y sus variantes no encajan adecuadamente con la programación de una Línea de Galvanizado. Igualmente incapaces de representar todas las condiciones necesarias son las formulaciones como problema de programación lineal entera (Integer Linear Program, ILP).
Descartados los métodos exactos, la aproximación habitual son los metaheurísticos. Los metaheurísticos basados en población, en particular, son fácilmente paralelizables y su estructura común permite diseñar métodos de alto nivel aplicables a todos ellos.
La evolución de los ordenadores lleva a la paralelización de algoritmos para extraer toda la capacidad computacional de los sistemas modernos, y así poder atacar problemas de mayor tamaño y complejidad. Esta tendencia ya resulta evidente en la literatura.
Al atacar un problema de optimización complejo de gran escala utilizando metaheurísticos debe tenerse en cuenta cuál es la mejor manera de sacar el máximo rendimiento de los equipos y cómo encaja con las propiedades del problema en cuestión.
Los desarrollos en metaheurísticos llevan décadas explotando estas capacidades, empezando por implementaciones muy específicas y avanzando hacia aproximaciones más generales.
Los beneficios de hacer más eficiente el uso de los recursos debe equilibrarse con la complejidad incurrida, tanto en la construcción del algoritmo como en la comunicación añadida, que en la práctica pueden perjudicar en mayor medida que los beneficios obtenidos. Este equilibrio se puede interpretar como un problema de optimización multi-objetivo. Los algoritmos existentes pueden situarse en el frente de Pareto representando diferentes compromisos entre las métricas. Aunque se pueden obtener mejores soluciones con métodos más complejos y computacionalmente más exigentes, hay un claro hueco en la región de baja complejidad.
Esta tesis trata de cubrir este hueco, proponiendo un método, denominado Multiverso, centrado en mejorar el desempeño en la región de la línea de referencia del frente de Pareto. No es un algoritmo concreto, sino una familia de algoritmos resultante de la aplicación de una transformación a cualquier metaheurístico basado en población.
El método Multiverso se prueba sobre el TSP, tanto con Algoritmos Genéticos como con Optimización por Colonia de Hormigas para validar las mejoras en calidad de la solución final y en la rapidez para alcanzar buenas soluciones. Finalmente, se aplica al problema de programación de la Línea de Galvanizado, para evaluar su capacidad de trasladar esas mejoras a este problema industrial bajo las condiciones que se dan en la práctica, incluida una exigente limitación del tiempo de ejecución debida a los requisitos operacionales del proceso.
