Escalonador de tarefas para o plataforma de nuvens federadas BioNimbuZ usando beam search iterativo multiobjetivo

Abstract

O problema de escalonamento de tarefas em sua formulação genérica é NP-Completo, caracterizando-o assim como um problema computacionalmente difícil. Ao levar esse problema para o ambiente distribuído de federação de nuvens computacionais o mesmo se torna ainda mais complicado. Dessa forma, uma política de escalonamento eficiente é altamente desejável para qualquer plataforma de federação de nuvens. Neste contexto, este trabalho visa a proposta e implementação de uma nova política de escalonamento para a plataforma de nuvem federada BioNimbuZ, baseada no algoritmo de busca combinacional beam search. O algoritmo proposto foi concebido com o objetivo de convergir rápidamente para boas soluções. Além disso, ele deve ser multiobjetivo, pois visa minimizar ambos tempo e custo de execução via o uso de uma frente de pareto. Os resultados dos testes iniciais mostraram um bom desempenho do algoritmo em relação à velocidade de convergência e ao tempo de execução total do algoritmo. _____________________________________________________________________________ ABSTRACT

Task scheduling, on its general formulation, is NP-Complete, making it thus a computationally hard problem. Even more so in the the distributed computing environment of cloud federations. Therefore, an efficient scheduling policy is a crucial component for any cloud federation platform. On this context, this work defines a new scheduling policy for the BioNimbuZ cloud federation platform, based on the beam search algorithm. The proposed algorithm was conceived with the goal of having a fast convergence to good solutions. Moreover, the algorithm should be multiobjective, by minimizing both time and cost of execution, through the use of a pareto frontier. Preliminary tests showed that the algorithm had good performance when analyzing the speed of convergence and the overall execution time of the algorithm.