(Centro Federal de Educação Tecnológica de Minas Gerais, 2023-08-18) Reis, Daniel Morais dos; Souza, Sérgio Ricardo; Barrientos, Anolan Yamilé Milanés; http://lattes.cnpq.br/8899693603008522; http://lattes.cnpq.br/3677015295211434; http://lattes.cnpq.br/2020021419382172; Souza, Sérgio Ricardo; Barrientos, Anolan Yamilé Milanés; Coleho, Igor Machado; Fernandes, Gustavo Alves; Menezes, Gustavo Campos; Souza, Marcone Jamilson Freitas
Este trabalho otimiza métodos sequenciais e propõe métodos heurísticos paralelizados em GPUs Nvidia CUDA para a solucionar o Problema de Instalação de Fibras em Redes Óticas - PIFRO. O PIFRO consiste em alocar, em uma rede ótica que utiliza tecnologia Wavelength Division Multiplexing (WDM), um conjunto de requisições previamente conhecidas com múltiplas origens e destinos. O objetivo é minimizar o custo total dos dispositivos necessários para a operação da rede. Após provar que a versão de decisão do PIFRO é NP-Difícil, é realizada uma formulação matemática e implementadas duas metaheurísticas paralelizadas em formatos inéditos, buscando a melhoria dos resultados da literatura. Uma das heurísticas é baseada em Biased Random Key Genetic Algorithm (BRKGA) e a outra é baseada em Iterated Local Search (ILS) as quais foram selecionadas pelos bons resultados existentes para o problema. Os conceitos básicos de processamento paralelo são analisados e selecionados para execução de novas metaheurísticas em ambientes heterogêneos com GPUs