Aplicação do Particle Swarm Optimization a um problema de escalonamento de máquinas paralelas não relacionadas com tempos de setup dependentes da sequência

Abstract

Esta dissertação aborda um problema de escalonamento de máquinas paralelas não relacionadas com tempos de setup dependentes da sequência e o objetivo é minimizar o makespan de um conjunto de trabalhos. Para tal, é implementado o algoritmo Particle Swarm Optimization, que é usado para resolver um problema da literatura, dividido em pequenos e grandes problemas, consoante o número de trabalhos que são utilizados. O desempenho deste algoritmo foi avaliado através de uma análise comparativa das suas soluções com as soluções obtidas usando o Ant Colony Optimization, o Simulated Annealing e o Genetic Algorithm. Na implementação do algoritmo em estudo foi utilizado a toolbox particleswarm do software MATLAB, que tenta otimizar utilizando o algoritmo Particle Swarm Optimization. Os resultados da implementação mostram que para pequenos problemas o Particle Swarm consegue superar o Genetic Algorithm em algumas instâncias, sendo que os outros três algoritmos apresentam valores de makespan inferiores. Para grandes problemas, é clara a superioridade do Particle Swarm em relação ao Genetic Algorithm, no entanto, relativamente aos restantes algoritmos o mesmo não acontece. Existe também a tendência crescente da variação percentual entre os algoritmos à medida que o número de máquinas aumenta para o mesmo número de trabalhos.

This dissertation addresses the unrelated parallel machine scheduling problem with sequence-dependent setup times and the objective is to minimize the makespan of a set of jobs. It is implemented the Particle Swarm Optimization, used to solve a problem from the literature, divided into small and large problems, depending on the number of jobs that are used. Particle Swarm performance is evaluated through a comparative analysis between its solutions and the solutions obtained using Ant Colony Optimization, Simulated Annealing and Genetic Algorithm. For implementing the algorithm under study, the particle swarm toolbox from the MATLAB software was used, which tries to optimize using the Particle Swarm Optimization. The results of the implementation show that for small problems the Particle Swarm can overcome the Genetic Algorithm in some instances, with the other three algorithms having lower makespan values. For large problems, the Particle Swarm superiority over Genetic Algorithm is clear, however, in relation to the other algorithms the same does not happen. There is also as increasing trend in the percentage variation between the algorithms as the number of machines increases for the same number of jobs.