Feature Transformations for Improving the Performance of Selection Hyper-heuristics on Job Shop Scheduling Problems

Este trabajo de tesis se centra en el problema de planificación de talleres (JS), un problema complejo de optimización combinatoria con amplia presencia en entornos de planificación del mundo real. La tesis aborda la dificultad de encontrar soluciones óptimas para estos problemas, particularmente en relación con las heurísticas, que son sensibles a las características del problema y pueden verse afectadas significativamente por pequeños cambios. Para abordar esto, se propone el uso de hiperheurísticas (HH) como método de solución.

Las hiperheurísticas, en comparación con las heurísticas, son capaces de seleccionar la heurística más adecuada para cada paso de la búsqueda, mejorando la adaptabilidad a diferentes problemas e instancias. Se clasifican en cuatro clases según su funcionamiento: selección, generación, perturbativas y constructivas. Se destaca la aplicación de las hiperheurísticas en el dominio de la planificación, donde la optimización de la producción es un objetivo clave en las industrias basadas en la cadena de suministro.

La investigación se centra en las transformaciones de características para mejorar el rendimiento de las hiperheurísticas constructivas de selección. Se introduce la idea de que las transformaciones de características pueden reestructurar los valores de las características para ayudar a los algoritmos de aprendizaje automático durante la fase de entrenamiento. Se utiliza el enfoque de Simulated Annealing (SA) como un algoritmo de búsqueda que simula el proceso de cristalización durante el enfriamiento, permitiendo la adaptación y optimización de las hiperheurísticas.

Los experimentos realizados demostraron que las hiperheurísticas (HH) pueden superar el rendimiento de las heurísticas individuales en las instancias de prueba, utilizando el algoritmo SA para el entrenamiento. La aplicación de las transformaciones de características (LT y ST) se muestra como un enfoque prometedor para obtener HH más estables, aunque no necesariamente con un mejor rendimiento. Se discute la importancia de ajustar los parámetros de las transformaciones para obtener resultados óptimos. La investigación concluye que las transformaciones de características pueden contribuir al desarrollo de HH con mejores capacidades de generalización y mayor estabilidad.