Algoritmo genético paralelo para o escalonamento de tarefas
Carregando...
Data de Submissão
Data de Defesa
2025-11-26
Edição
Autores
Orientadores
Coorientadores
Editores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Descrição
Problemas de escalonamento de tarefas estão presentes em diversas aplicações e a solução destes é fundamental para uma otimização no uso dos recursos. Entre os modelos existentes, destaca-se o problema de escalonamento do tipo Flow Shop permutacional, que possuem uma complexidade combinatória e cuja a solução por métodos exatos é limitada a instâncias de pequeno porte. Neste contexto, os algoritmos genéticos surgem como uma alternativa, devido à sua capacidade de explorar amplos espaços de busca e encontrar soluções de alta qualidade. No entanto, algoritmos genéticos podem demandar um alto custo computacional, particularmente em problemas que envolvem populações com grande número de indivíduos por geração. Portanto, neste trabalho foi desenvolvido uma implementação de algoritmos genéticos paralelos para a resolução do problema de escalonamento do tipo Flow-Shop permutacional, com o objetivo de reduzir o tempo total de execução das tarefas, isto é, o tempo necessário para que todas as tarefas sejam processadas em todas as máquinas do ambiente Flow-Shop. Para tanto, foi testado um modelo em ilhas bidimensionais, avaliando diferentes números de ilhas e número de gerações entre migrações. As implementações foram desenvolvidas para uma arquitetura de memória distribuída, utilizando um cluster de computadores, e a comunicação entre os processos foi realizada por meio da biblioteca Message Passing Interface (MPI). A qualidade das soluções foi avaliada a partir da base de testes proposta por Taillard (1993), amplamente utilizada na literatura. Os resultados obtidos mostram que tanto a versão sequencial do algoritmo genético quanto a versão paralela em modelo de ilhas apresentaram resultados superiores aos reportados na literatura. Por fim, nos testes limitando o número de avaliações da função objetivo, a versão paralela alcançou um speedup de cerca de 10 vezes em um computador com 10 núcleos, indicando que o custo de comunicação da migração de indivíduos não afetou significativamente o desempenho da implementação paralela. [resumo fornecido pelo autor]