Diseño de desarrollo de un generador y recomendador de algoritmos de búsqueda en problemas de scheduling complejos

Abstract

[ES] Este Trabajo de Fin de Grado (TFG) aborda la problemática de la planificación industrial, centrándose en los desafíos relacionados con la programación de tareas, conocido como JSP (Job Shop Scheduling Problem). El estudio destaca cómo éstos desafíos han evolucionado, pasando de un enfoque exclusivo en la optimización temporal a la consideración de aspectos más amplios, como el impacto en el consumo de energía. Sin embargo, se ha observado que muchos de los problemas tratados en la literatura actual han quedado obsoletos y no reflejan la realidad industrial actual, lo que subraya la necesidad urgente de desarrollar herramientas que generen problemas más representativos de situaciones reales. Además, dada la amplia variedad de métodos desarrollados para resolver este tipo de problemas, es esencial contar con una herramienta que, basándose en las características específicas de un problema dado, pueda recomendar el método más adecuado para su resolución. Para abordar estas dos necesidades, se han diseñado y desarrollado dos herramientas principales: un generador de instancias configurable y un recomendador de algoritmos. El generador de instancias permite la creación de un conjunto diverso y representativo de problemas JSP, del cual se han generado un total de 9720 instancias para este trabajo. Éstas instancias han sido resueltas utilizando diversos algoritmos de optimización, tanto exactos como aproximados. Éstos datos han sido utilizados para entrenar y evaluar el recomendador de algoritmos mediante modelos de aprendizaje automático, destacando el modelo XGBoost, que ha alcanzado una precisión del 83.44 % en las pruebas realizadas.

[EN] This Final Degree Project (FDP) addresses the issue of industrial planning, focusing on the challenges related to task scheduling, known as the Job Shop Scheduling Problem (JSP). The study highlights how these challenges have evolved from an exclusive focus on time optimization to the consideration of broader aspects, such as the impact on energy consumption. However, it has been observed that many of the problems addressed in current literature have become obsolete and do not reflect the current industrial reality, underscoring the urgent need to develop tools that generate problems more representative of real-life situations.

Furthermore, given the wide range of methods developed to solve this type of problem, it is essential to have a tool that, based on the specific characteristics of a given problem, can recommend the most suitable method for its resolution. To address these two needs, two main tools have been designed and developed: a configurable instance generator and an algorithm recommender.

The instance generator allows for the creation of a diverse and representative set of JSP problems, from which a total of 9720 instances have been generated for this project. These instances have been solved using various optimization algorithms, both exact and approximate. This data has been used to train and evaluate the algorithm recommender through machine learning models, highlighting the XGBoost model, which achieved an accuracy of 83.44% in the tests conducted.

[CA] Este Treball de Fi de Grau (TFG) aborda la problemàtica de la planificació industrial, centrant-se en els desafiaments relacionats amb la programació de tasques, conegut com JSP (Job Shop Scheduling Problem). L’estudi destaca com estos desafiaments han evolucionat, passant d’un enfocament exclusiu en l’optimització temporal a la consideració d’aspectes més amplis, com l’impacte en el consum d’energia. No obstant això, s’ha observat que molts dels problemes tractats en la literatura actual han quedat obsolets i no reflectixen la realitat industrial actual, la qual cosa subratlla la necessitat urgent de desenvolupar ferramentes que generen problemes més representatius de situacions reals. A més a més, donada l’àmplia varietat de mètodes desenvolupats per a resoldre este tipus de problemes, és essencial comptar amb una ferramenta que, basant-se en les característiques específiques d’un problema donat, puga recomanar el mètode més adequat per a la seua resolució. Per a abordar estos problemes, s’han dissenyat i desenvolupat dos ferramentes principals: un generador d’instàncies configurable i un recomanador d’algorismes. El generador d’instàncies permet la creació d’un conjunt divers i representatiu de problemes JSP, del qual s’han generat un total de 9720 instàncies per a este treball. Estes instàncies han sigut resoltes utilitzant diversos algorismes d’optimització, tant exactes com aproximats. Estes dades han sigut utilitzades per a entrenar i avaluar el recomanador d’algorismes mitjançant models d’aprenentatge automàtic, destacant el model XGBoost, que ha aconseguit una precisió del 83.44% en les proves realitzades.