Algoritmos de optimización para el problema flow-shop con necesidad de recursos adicionales

Abstract

En este Trabajo de Fin de Grado se quiere definir y tratar rigurosamente un problema de ajuste de tareas a máquinas a ejecutar en el mínimo tiempo posible, sujetas a unas restricciones de recursos a través de diferentes algoritmos como heurísticas greedy o metaheurísticas GRASP. Este problema es conocido también como Flowshop Scheduling Problem (FSP), un problema NP-Hard, que intentaremos solucionar a través de una búsqueda de la mejor solución factible posible con la ayuda de métodos heurísticos, ya que no podemos obtener una solución óptima debido a la gran complejidad del problema. A lo largo del siguiente trabajo, se proponen diferentes criterios y variantes greedy que permiten acercarse a esa mejor solución posible y tomar conclusiones en base a ello. Además, los experimentos computacionales permiten comparar los resultados obtenidos con diferentes modificaciones del algoritmo así como con diferentes instancias del problema y se analizarán los resultados obtenidos.

In this Bachelor's Thesis, we aim to find a feasible solution to the problem of assigning tasks to machines to be executed in the shortest possible time, subject to resource constraints, through different heuristics such as greedy heuristics or GRASP metaheuristics. This problem is also known as the Flowshop Scheduling Problem (FSP) and is an NP-Hard problem, where we will try to find the best possible feasible solution since no defined analytical optimal solution exists. Throughout this work, different criteria and greedy variants are proposed to approach that best possible solution and draw conclusions based on it. Additionally, computational experiments will be conducted to compare the results obtained with different modifications of the algorithm, as well as with different problem instances, and the obtained results will be analyzed.