Resolución de problemas de optimización multi-objetivo combinatorios en el entorno industrial

Abstract

El objetivo de la tesis doctoral Resolución de problemas de optimización multi-objetivo combinatorios en el entorno industrial, realizada por D. Pablo Valledor Pellicer y dirigida por Dr. D. Alberto Gómez Gómez, es analizar y modelar el problema de replanificación de tareas en entornos dinámicos del tipo flow shop con permutación, esquema de amplia aplicación en entornos industriales. Para esto, se requiere del análisis de las técnicas existentes en la literatura, tanto en problemas multi-objetivo, como en problemas de replanificación de trabajos, así como de la definición de una arquitectura de replanificación, y de diferentes algoritmos, que permitan resolver el problema de forma adecuada, al variar, tanto las tareas como el entorno de producción. Interés del Problema En múltiples problemas de optimización existen distintas funciones objetivo que se encuentran en conflicto al trabajar sobre un conjunto común de variables de decisión y no ser comparables al no expresarse en las mismas unidades de medida, no pudiéndose, por tanto, reducir el problema a una optimización mono-objetivo, técnicas ampliamente estudiadas en la literatura científica. Adicionalmente, son muy comunes en el entorno industrial, situaciones donde se producen disfunciones en el sistema, tales como llegadas de nuevos trabajos o roturas de máquinas, que requieren de una respuesta del sistema de planificación para adaptarse a estos nuevos cambios. Por tanto, el interés del problema es dual: por un lado, la consideración de la complejidad de problemas con varias funciones objetivo, y por otro lado, su aplicación en sistemas dinámicos. Metodología En primer lugar, se realiza una formulación matemática del problema, basada en un modelo de programación lineal entera. A partir de dicho modelo, se presenta la arquitectura de replanificación, basada en una estrategia predictiva-reactiva, propuesta para solucionar el problema. En dicha arquitectura, se expone el método de cálculo de la solución a ejecutar en el entorno de producción, y utilizada para evaluar la estabilidad del sistema, basada en el cálculo del punto de rodilla del frente de Pareto obtenido. Posteriormente, se describen los tres métodos de replanificación desarrollados. Dichos métodos son 7 reglas de prioridad y la aplicación de 2 metaheurísticas: RIPG y HDNSGA-II. Ésta última se ha diseñado específicamente para resolver el problema definido, mientras que la técnica RIPG es una técnica bi-objetivo propuesta en la literatura y que se ha adaptado a este entorno de producción dinámica. Los métodos propuestos se aplican a un benchmark específicamente diseñado en esta tesis, considerando 3 funciones objetivo: makespan, tardanza ponderada total y estabilidad, y adaptando el sistema en función de 3 tipos de disfunciones: llegadas de nuevos trabajos, roturas de máquinas y variación en los tiempos de procesamiento. Para realizar la comparación de los tres métodos es necesario un completo diseño de experimentos. Resultados El análisis de los resultados obtenidos permite la extracción de conclusiones interesantes. De acuerdo con la comparativa estadística realizada, el algoritmo HDNSGA-II se comporta mejor que el RIPG en el entorno diseñado, especialmente en problemas de mayor tamaño. En cuanto a las reglas de prioridad, la regla RANDOM tiene, en general, un mejor comportamiento que el resto de reglas evaluadas. Como inconveniente, RANDOM tiene un menor ratio de soluciones no dominadas respecto a las reglas ATC y FIFO, y el comportamiento de la métrica hipervolumen es dependiente de las dimensiones del problema. A lo largo de la tarea de estudio que se ha realizado, se han tenido que tomar decisiones, dejando muchas líneas de investigación para futuros trabajos. Entre dichas líneas destacan el uso de un método probabilístico para la fase de reinicialización del HDNSGA-II, y la adaptación de las técnicas en entornos con más de 4 funciones objetivo (denominados many-objective).