Heuristicas e metaheuristicas para otimização combinatoria multiobjetivo

Resumo: Neste trabalho apresentam-se contribuições de desenvolvimentos de métodos heurísticos para problemas de otimização combinatória multiobjetivo. O objetivo dos métodos propostos é gerar, em tempo computacional aceitável, um conjunto de soluções dominantes próximo ao conjunto Pareto-ótimo, permitindo ao decisor (decision maker) a escolha de uma solução que satisfaça seus interesses. Os métodos são testados no problema de programação de tarefas em um flowshop e no problema da mochila. Inicialmente, desenvolve-se uma heurística construtiva para gerar um conjunto de soluções dominantes do problema de flowshop multiobjetivo. Para obter conjuntos de soluções dominantes próximos aos conjuntos Paretoótimos, desenvolve-se uma heurística de busca local e duas metaheurísticas. A primeira é baseada em conceitos de Algoritmos Genéticos no qual usa-se fortemente o conceito de dominância de Pareto e combinam-se estratégias de elitismo, preservação de diversidade na população e busca local. A seguir, é proposto um método baseado em Busca Tabu na qual explora-se um conjunto de soluções em paralelo com o propósito de encontrar uma variedade de soluções distribuídas sobre toda a fronteira dominante. O desempenho dos métodos propostos é testado sobre uma variedade de instâncias do problema de flowshop multiobjetivo e do problema da mochila multiobjetivo.Abstract: This work presents contributions to the development of heuristic methods for multiobjective combinatorial problems. The goal of the proposed methods is to generate in a reazonable time a set of approximately Pareto-optimal solutions, allowing the decision maker to choose a solution of interest. The methods are tested on the flowshop scheduling problem and the knapsack problem. First, we develop a constructive heuristic to generate a set of dominant solutions for the multiobjective flowshop scheduling problem. In order to find sets of dominant solutions which are closer to the Pareto-optimal sets, we develop a local search heuristic and two metaheuristics. The first one is based on Genetic Algorithms which strongly use the concept of Pareto dominance and combine elitism, population diversity and local search strategies. Then, we propose a Tabu Search-based method which explores a set of solutions in parallel to find a variety of solutions distributed along the Pareto frontier. The performance of the proposed methods is tested in a number of instances for the multiobjective flowshop scheduling problem and the multiobjective knapsack problem