Heurísticas híbridas para escalonamento estático de tarefas em sistemas com processadores heterogêneos - Rios, Eyder Franco Sousa (2024)
A exploração dos recursos existentes em sistemas computacionais distribuídos através da alocação adequada dos componentes de aplicações paralelas não é um processo elementar. Tal procedimento constitui o Problema de Escalonamento de Tarefas que é, em sua forma geral, um problema NP-Completo e tem sido bastante explorado pela literatura especializada. A alta complexidade deste problema tem incentivado a pesquisa de métodos heurísticos para sua resolução, onde algoritmos da classe list scheduling constituem mecanismos comumente empregados. Todavia, a característica inerentemente gulosa destas heurísticas pode, em muitos casos, contribuir negativamente para o desempenho destes algoritmos. Este trabalho investiga a aplicabilidade da integração de heurísticas da classe list scheduling com mecanismos de busca baseados em metaheurísticas. O ob jetivo é combinar o poder de busca das metaheurísticas com a baixa complexidade de heurísticas list scheduling para a geração de escalonamentos e cientes em sistemas computacionais distribuídos, cujos recursos são geralmente heterogêneos. Para tanto, são propostas duas heurísticas denominadas HTSGA e HTSG baseadas, respectivamente, em Algoritmo Genético e GRASP. O mecanismo de busca implementado por estas heurísticas procura eliminar o comportamento guloso dos algoritmos list scheduling fornecendo novas possibilidades de escalonamento através da determinação de diferentes seqüências de vi atribuição de tarefas durante a construção de soluções. Além disso, foi investigada a possibilidade de adaptação das heurísticas propostas a diferentes classes de aplicações paralelas. Como forma de validação deste trabalho, o desempenho das heurísticas propostas foi comparado com algoritmos de construção tradicionais existente na literatura e com uma metaheurística que serviu de base para este trabalho. Os resultados mostraram que os algoritmos propostos são robustos tanto em relação à adaptabilidade às características das instâncias submetidas quanto na rápida convergência para soluções sub-ótimas