Secuenciación de máquinas con necesidad de ajustes y recursos adicionales.

Abstract

[ES] En esta tesis doctoral se estudia el problema de secuenciación de máquinas paralelas no relacionadas con necesidad de ajustes y recursos adicionales asignados en los ajustes. En este problema, se tiene un grupo de tareas (también llamadas trabajos), donde cada una debe ser procesada en una de las máquinas paralelas disponibles. Para procesar una tarea después de otra en la misma máquina, se debe hacer un ajuste en la máquina. Se asume que estos ajustes deben ser realizados por un recurso adicional limitado (por ejemplo, operarios). En esta tesis doctoral se estudian dos variantes del problema planteado: 1) considerando el problema con el único objetivo de minimizar el tiempo máximo de finalización de todos los trabajos (makespan), y 2) considerando el problema multi-objetivo minimizando simultáneamente el makespan y el consumo máximo de recursos adicionales.

Inicialmente, se realiza una completa revisión bibliográfica sobre estudios relacionados con el problema planteado. En esta revisión se detecta que, a pesar de existir numerosos estudios de secuenciación de máquinas paralelas, no muchos de estos estudios tienen en cuenta recursos adicionales. Posteriormente, para introducir el problema a estudiar antes de plantear métodos de resolución, se realiza una breve explicación de los principales problemas de secuenciación de máquinas paralelas.

El problema de un solo objetivo está clasificado como NP-Hard. Por ello, para abordar su resolución se han diseñado e implementado heurísticas y metaheurísticas siguiendo dos enfoques diferentes. Para el primer enfoque, que ignora la información sobre el consumo de recursos adicionales en la fase constructiva, se adaptan dos de los mejores algoritmos existentes en la literatura para el problema de máquinas paralelas con ajustes sin necesidad de recursos adicionales. En el segundo enfoque, que sí tiene en cuenta la información sobre el consumo de recursos adicionales en la fase constructiva, se proponen nuevos algoritmos heurísticos y metaheurísticos para resolver el problema. Tras analizar los resultados de los experimentos computacionales realizados, concluimos que hay diferencias entre los dos enfoques, siendo significativamente mejor el enfoque que tiene en cuenta la información sobre los recursos adicionales.

Al igual que en el caso de un solo objetivo, la complejidad del problema multi-objetivo obliga a presentar algoritmos heurísticos o metaheurísticos para resolverlo. En esta tesis se presenta un nuevo algoritmo metaheurístico multi-objetivo eficiente para encontrar buenas aproximaciones a la frontera de Pareto del problema. Además, se adaptaron otros tres algoritmos que han mostrado buenos resultados en diferentes estudios de problemas de secuenciación de máquinas multi-objetivo. Después de realizar experimentos computacionales exhaustivos, concluimos que el nuevo algoritmo propuesto en esta tesis es significativamente mejor que los otros tres algoritmos existentes, y que se han adaptado para resolver este problema.

[CAT] En aquesta tesi doctoral s'estudia el problema de seqüenciació de màquines paral·leles no relacionades amb necessitat d'ajustos i recursos addicionals assignats en els ajustos. En aquest problema, es tenen un grup de tasques (també anomenades treballs), on cadascuna ha de ser processada en una de les màquines paral·leles disponibles. Per processar una tasca després d'una altra en la mateixa màquina, s'ha de fer un ajustament en la màquina. S'assumeix que aquests ajustos en les màquines per a processar una tasca després del processament d'una altra, han de ser realitzats per un recurs addicional limitat (per exemple, operaris). En aquesta tesi doctoral s'estudien dos variants al problema plantejat: 1) considerant el problema com l'únic objectiu de minimitzar el temps màxim de finalització de tots els treballs (makespan), i 2) considerant el problema multi-objectiu minimitzant simultàniament el makespan i el consum màxim de recursos addicionals.

Inicialment, es realitza una completa revisió bibliogràfica sobre estudis relacionats amb el problema plantejat. En esta revisió es detecta que, tot i existir nombrosos estudis de seqüenciació de màquines paral·leles, hi ha molts pocs que tenen en compte recursos addicionals. Posteriorment, per introduir el problema a estudiar abans de plantejar mètodes de resolució, es realitza una breu explicació dels principals problemes de seqüenciació de màquines paral·leles.

El problema d'un sol objectiu està classificat com NP-Hard. Per això, per abordar la seua resolució s'han dissenyat i implementat heurístiques y metaheurístiques seguint dos enfocs diferents. El primer enfoc ignora la informació sobre el consum de recursos en la fase constructiva, adaptant dos dels millors algoritmes existents en la literatura per al problema de seqüenciació de màquines paral·leles amb ajustaments sense necessitat de recursos. Per al segon enfoc si es té en compte la informació sobre el consum de recursos en la fase constructiva. Després d'analitzar els resultats dels experiments computacionals realitzats, concloem que hi ha diferencies entre els dos enfocs, sent significativament millor l'enfoc que té en compte la informació sobre el recursos.

De la mateixa manera que en el cas d'un sol objectiu, la complexitat del problema multi-objectiu obliga a presentar algoritmes heurístics o metaheurístics per a resoldre-ho. En aquesta tesi es presenta un nou algoritme metaheurístic multi-objectiu eficient per trobar bones aproximacions a la frontera de Pareto del problema. A més, es van adaptar altres tres algoritmes que han mostrat bons resultats en diferents estudis de problemes de seqüenciació de màquines multi-objectiu. Després de realitzar experiments computacionals exhaustius, concloem que el nou algoritme proposat en aquesta tesi és significativament millor que els altres tres algoritmes existents i que s'han adaptat per resoldre aquest problema.

[EN] In this thesis we study the unrelated parallel machine scheduling problem with setup times and additional limited resources in the setups. In this problem, we have a group of tasks (also called jobs), where each one must be processed on one of the available parallel machines. To process one job after another on the same machine, a setup must be made on the machine. It is assumed that these setups on machines must be made by a limited additional resource (eg, operators). In this thesis two variants of the problem are studied: 1) considering the problem with the objective of minimizing the maximum completion time of all jobs (makespan), and 2) considering the multi-objective problem, minimizing the makespan and the maximum consumption of additional resources.

Initially, a complete literature review is carried out on studies related to the problem addressed in this thesis. This review finds that despite numerous parallel machine scheduling studies, there are very few that take into account additional resources. Subsequently, to introduce the problem addressed before proposing resolution methods, a brief explanation of the main parallel machines scheduling problems is made.

The problem with a single objective is classified as NP-Hard. Therefore, to solve it, heuristics and metaheuristics have been designed and implemented following two different approaches. For the first approach, which ignores the information on the consumption of resources in the construction phase, two of the best algorithms existing in the literature for the problem of parallel machines with setups without additional resources are adapted. For the second approach, which does take into account information on the consumption of resources in the construction phase, new heuristic and metaheuristic algorithms are proposed to solve the problem. Following the results of the computational experiments, we conclude that there are differences between the two approaches, the approach that takes into account the information on resources being significantly better.

As in the case of a single objective, the complexity of the multi-objective problem requires the formulation of heuristic or metaheuristic algorithms to solve it. In this thesis, a new efficient multi-objective metaheuristic algorithm is presented to find good approximations to the Pareto front of the problem. In addition, three other algorithms that have shown good results in different studies of multi-objective machine scheduling problems were adapted. After carrying out exhaustive computational experiments, we concluded that the new algorithm proposed in this thesis is significantly better than the other three adapted algorithms.