Hibridização de métodos exatos e heurísticos para a minimização do atraso ponderado no escalonamento de tarefas em máquinas paralelas

• Ano de defesa: 2018
• Autor(a) principal: Silva, Marcos Thomaz da
• Outros Autores: http://lattes.cnpq.br/1710397494828508, https://orcid.org/0000-0001-7621-2411
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Amazonas; Instituto de Computação; Brasil; UFAM; Programa de Pós-graduação em Informática
• Palavras-chave em Português: Algorítmos genéticos; Heurística; Programação linear; CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO; Algoritmos genéticos; Busca local; Heurísticas; Programação linear inteira; Escalonamento de tarefas
• Link de acesso: https://tede.ufam.edu.br/handle/tede/7593

Nesta dissertação estão sendo apresentados os resultados da investigação realizada sobre problemas de escalonamento em máquinas paralelas, com foco na minimização do atraso ponderado total das tarefas, com tempos de processamento e prazos estimados de término arbitrários. Este é um problema clássico muito encontrado em indústrias, ambientes de produção e cenários onde o atraso na realização de tarefas ou produção pode gerar multas ou penalidades. A estratégia de resolução aplicada faz uso de um método híbrido exato-heurístico, onde a execução de um Algoritmo Genético fortemente baseado em Busca Local, denominado GLS, fornece um conjunto de soluções de ótimos locais para ser incorporado em uma formulação de programação linear inteira tri-indexada, otimizando o processo de resolução enumerativo implícito. Sendo a parametrização um problema inerente aos algoritmos genéticos e meta-heurísticas em geral, foi utilizada a ferramenta iRace para a otimização e definição de parâmetros. O solver IBM ILog CPLEX e a biblioteca dinâmica UFFLP foram utilizados para avaliar o conjunto de soluções obtido através das heurísticas utilizando a formulação de programação inteira. Os experimentos computacionais foram realizados em instâncias criadas com base no benchmark disponível na OR-Library com 40, 50, 100, 150, 200, 300 e 500 tarefas, em ambientes com 2, 4, 10 e 20 máquinas paralelas, obtendo resultados competitivos frente às melhores estratégias disponibilizadas na literatura, e apresentando a robustez do método em instâncias maiores.