Algoritmo híbrido multiobjetivo para o problema flexible job shop

Abstract

Flexible Job Shop (FJSP) is an important combinatorial optimization problem that has been widely researched by means evolutionary computation techniques. Algorithms based on Particle Swarm Optimization (PSO), for example, have shown good results for this problem, but tend to converge prematurely. Moreover, Genetic Algorithms (GAs) have the ability to deal with a large search space, but do not guarantee convergence. The multiobjective aspect of this problem has been considered by both of these techniques. These features have inspired this work, which presents a hybrid and multi-objective algorithm based on PSO, genetic operators and Pareto optimal settings through the procedure Fast Non-dominated Sorting (FNS). While the PSO characteristics guarantee convergence, genetic operators improve the exploitation of the search space. However, in order to reach better results than those presented in the literature, two significant innovations were introduced and a new PSO algorithm was obtained, that it is denominated PSO using Diversity (DIPSO), which is efficient to cope with FJSP. The first innovation was to take the global best as the Front-1 produced by Pareto optimal. Then, the global best is not just an individual of the population as in the original PSO, but a set containing all the best solutions found during the algorithm execution. The second innovation was the development of a crossover operator, which introduced diversity in the population and allowed to expand exploration of the search space. These two innovations allowed to find new solutions in three of the fifteen FJSP instances, improve results previously reported in the literature and reproduce several known solutions, demonstrating the DIPSO efficiency in addressing FJSP. It has been also observed that DIPSO is a new proposal of evolutionary algorithms, which can be used in other problems of this nature. In addition to the approach described in DIPSO, other proposals were investigated, such as the introduction of new objectives for the FJSP and the use of new techniques not yet explored.