/img alt="Imagem da capa" class="recordcover" src="""/>
Dissertação
Hibridização de métodos exatos e heurísticos para a minimização do atraso ponderado no escalonamento de tarefas em máquinas paralelas
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...
Autor principal: | Silva, Marcos Thomaz da |
---|---|
Outros Autores: | http://lattes.cnpq.br/1710397494828508, https://orcid.org/0000-0001-7621-2411 |
Grau: | Dissertação |
Idioma: | por |
Publicado em: |
Universidade Federal do Amazonas
2020
|
Assuntos: | |
Acesso em linha: |
https://tede.ufam.edu.br/handle/tede/7593 |
Resumo: |
---|
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. |