Publicação: Um algoritmo genético híbrido para otimização do escalonamento de tarefas independentes em máquinas heterogêneas
Carregando...
Tipo do documento
Data
Direito de acesso
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Título da Revista
ISSN da Revista
Título de Volume
Autores
Orientador
Coorientador
Resumo
Nos últimos anos com o crescente poder de processamento das máquinas e a comunica- ção entre aplicações distribuídas cada vez mais rápidas devido a alta velocidade das redes proporcionaram ainda mais o uso de computação distribuída para solucionar problemas de escalonamento. Diversos algoritmos buscam soluções ótimas para problemas de esca- lonamento, baseado em diversas funções objetivo. O critério mais abordado na literatura é a minimização do makespan. Motivado por essas características, este trabalho propõe a aplicação de um algoritmo genético (AG) híbrido para o problema de escalonamento de tarefas independentes. O algoritmo possui duas fases: na primeira, utiliza-se um modelo de otimização relaxado (linear) para gerar um conjunto de soluções válidas (inteiras), correspondentes à primeira geração do AG. Em seguida, o algoritmo evolui essa popula- ção. O processo evolutivo é aperfeiçoado por meio de um algoritmo de busca local. Esse algoritmo busca reduzir a carga de trabalho dos processadores sobrecarregados, migrando tarefas para os processadores menos ocupados. Caso a migração não encontre melhores resultados, o algoritmo troca tarefas entre esses dois processadores (consequentemente, a busca local tenta balancear a carga de trabalho). O algoritmo genético híbrido proposto aqui foi comparado com outros algoritmos bastante conhecidos da literatura, superando-os em diversas instâncias. Isso indica que o método proposto é uma abordagem promissora a ser considerada para instâncias maiores.
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.
Palavras-chave
Algoritmos Genéticos, Algoritmos Híbridos, Ambientes Heterogêneos, Problemas de Escalonamento, Busca Local, Modelo ETC, Task Scheduling, Genetic Algorithm, Local Search, ETC Model
Citação
SOUSA, José Junio Ribeiro. Um algoritmo genético híbrido para otimização do escalonamento de tarefas independentes em máquinas heterogêneas. 2022. 60 f. Dissertação (Mestrado em Ciências da Computação) - Universidade Federal de Uberlândia, Uberlândia, 2022. DOI https://doi.org/10.14393/ufu.di.2022.582
Avaliação
Revisão
Suplementado Por
Referenciado Por
Licença Creative Commons
Exceto quando indicado de outra forma, a licença deste item é descrita como Acesso Aberto