Análise de estruturas de vizinhança: um estudo de caso sobre o problema de programação de tarefas em ambiente Job Shop
| Ano de defesa: | 2020 |
|---|---|
| Autor(a) principal: | |
| Orientador(a): | |
| Banca de defesa: | , |
| Tipo de documento: | Dissertação |
| Tipo de acesso: | Acesso aberto |
| Idioma: | por |
| Instituição de defesa: |
Universidade Federal da Bahia
Instituto de Matemática e Estatística Departamento de Ciência da Computação |
| Programa de Pós-Graduação: |
em Ciência da Computação
|
| Departamento: |
Não Informado pela instituição
|
| País: |
brasil
|
| Palavras-chave em Português: | |
| Área do conhecimento CNPq: | |
| Link de acesso: | http://repositorio.ufba.br/ri/handle/ri/33305 |
Resumo: | Uma das características mais importantes de uma busca local é a sua estrutura de vizinhança. Amplamente utilizada em problemas de otimização, uma vizinhança é um mapeamento que atribui para cada solução s ∈ S um conjunto de soluções vizinhas N(s). Procedimentos de busca local usam o conceito de vizinhanças para mover-se de uma solução s para uma outra solução vizinha s’ ∈ N(s). Nesta dissertação, realizamos uma análise experimental do desempenho de seis estruturas de vizinhança para o Problema de Programação de Tarefas em ambiente Job Shop. O objetivo desse problema consiste em planejar a execução de tarefas considerando um conjunto limitado de recursos e respeitando as restrições estabelecidas. Para uma análise efetiva das estruturas de vizinhança, foram utilizados quatro critérios de avaliação: Eficiência, Convergência, Força e Aprimoramento. Neste trabalho, vizinhanças foram apresentadas a partir da utilização de conceitos de teoria dos grafos. Os procedimentos de busca local aplicados foram desenvolvidos com base nas heurísticas Hill Climbing e Variable Neighborhood Descent, a última com o objetivo de estudar as interferências entre buscas realizando combinações de vizinhanças. A partir da análise dos resultados obtidos, foi possível correlacionar desempenhos das vizinhanças e obter informações úteis para entender por que certas vizinhanças apresentam desempenhos melhores que outras nos critérios de avaliação definidos. |