Um algoritmo genético híbrido para otimização do escalonamento de tarefas independentes em máquinas heterogêneas

Abstract

In recent years with the increasing processing power of machines and the increasingly faster communication between distributed applications due to the high speed of networks have provided even more use of distributed computing to solve scheduling problems. Seve- ral algorithms seek optimal solutions to scheduling problems, based on several objective functions. The criterion most often addressed in the literature is the minimization of makespan. Motivated by these characteristics, this work proposes the application of a hybrid genetic algorithm (GA) to the problem of scheduling independent tasks. The al- gorithm has two phases: in the Ąrst phase, a relaxed (linear) optimization model is used to generate a set of valid (integer) solutions, corresponding to the Ąrst generation of the GA. Then, the algorithm evolves this population. The evolutionary process is reĄned by means of a local search algorithm. This algorithm seeks to reduce the workload of overloaded processors by migrating tasks to the less busy processors. If the migration does not Ąnd better results, the algorithm switches tasks between these two processors (consequently, the local search tries to balance the workload). The hybrid genetic algo- rithm proposed here was compared with other well-known algorithms in the literature, outperforming them in several instances. This indicates that the proposed method is a promising approach to consider for larger instances.