Metaheurísticas constructivas para la secuenciación de máquinas en paralelo con ajustes entre trabajos y necesidad de recursos adicionales

Abstract

[ES] En este trabajo se pretende resolver el problema de secuenciación de máquinas paralelas no relacionadas con ajustes entre trabajos y recursos limitados adicionales. El objetivo del problema es minimizar el tiempo de finalización del último trabajo en ser procesado (makespan). Este makespan puede ser determinante para cualquier empresa con una cadena de producción a la hora de cumplir plazos de entrega o mejorar la productividad. Para abordar este problema se diseñarán e implementarán heurísticas que estarán formadas por dos fases: una fase constructiva donde se obtendrá una primera solución del problema, y una fase de reparación donde se arreglará la solución obtenida en la fase anterior si se supera el número de recursos permitidos. Además, para conseguir una mayor diversidad de soluciones, se aleatorizará parte de la fase constructiva, convirtiendo las heurísticas en metaheurísticas. Más adelante se realizará una extensa fase de experimentos y posterior análisis, en el que se probarán diferentes versiones de las heurísticas y metaheurísticas variando diferentes factores. A continuación, se compararán los resultados obtenidos por los algoritmos propuestos, con los logrados previamente para el mismo problema por un modelo de programación lineal entera (MILP, por sus siglas en inglés Mixed Integer Linear Program). La conclusión principal de estos experimentos es que, con un tiempo de proceso muy inferior, se pueden casi igualar y en algunos casos mejorar los resultados de este modelo utilizando los algoritmos heurísticos y metaheurísticos propuestos.

[EN] This project aims to solve the unrelated parallel machines scheduling problem with adjustments between jobs and additional limited resources. The goal of this problem is to minimize the completion time of the last job (makespan). This makespan can be decisive for any business with production chains when it comes to respect deadlines or improving productivity. To engage this problem, design and implementation of heuristics and metaheuristics will be done, and they will be split in two phases: a constructive phase where a first solution will be obtained, and a repair phase where this solution will be fixed in case of exceeding the resources limit. Furthermore, to achieve a major diversity of solutions, part of the construction phase will be randomized, transforming heuristics into metaheuristics. Later, an extensive experiments phase will be done with a proper analysis, where different versions of the heuristics and metaheuristics will be tested varying different factors. Next, the results obtained will be compared with the ones achieved for the same problem by an integer linear programming model (MILP). The main conclusion of these experiments is that, with much less processing time, the results obtained with the model are similar or in some instances even worse, compared to the ones achieved with the proposed heuristic and metaheuristic algorithms.

[CA] En aquest treball es tracta de resoldre el problema de seqüenciació de màquines paral·leles no relacionades amb ajustos entre treballs i recursos limitats adicionals. L’objectiu del problema es minimitzar el temps de finalització de l’últim treball a ser processat (makespan). Este makespan pot ser determinant per a qualsevol empresa amb una cadena de producció a l’hora de complir terminis de lliurament o millorar la productivitat. Per a abordar aquest problema es dissenyaran e implementaran heurístiques que estaran formades per dues fases: una fase constructiva on s’obtindrà una primera solució del problema, i una fase de reparació on s’arreglarà la solució obtinguda en la fase anterior si es supera el nombre de recursos permitits. A més, per a aconseguir una major diversitat de solucions, s’aleatoritzarà part de la fase construcitva, convertint les heurístiques en metaheurístiques. Més endavant es realitzarà una extensa fase d’experiments i posterior anàlisi, en el qual es provaran diferents versions de les heurístiques i metaheurístiques variant diferents factors. A continuació, es compararan els resultats obtinguts pels algorismes proposats, amb els reeixits prèviament per al mateix problema obtinguts amb un model de programació lineal sencera (MILP, per les seues sigles en anglés Mixed Integer Linear Program). La conclusió principal d’aquests experiments és que, amb un temps de procés molt inferior, es poden quasi igualar i en alguns casos millorar els resultats d’aquest model utilitzant els algorismes heurístics i metaheurístics proposats.