Use este identificador para citar ou linkar para este item: https://repositorio.ufu.br/handle/123456789/36613
ORCID:  http://orcid.org/0000-0003-1286-9072
Tipo do documento: Dissertação
Tipo de acesso: Acesso Aberto
Título: Um algoritmo genético híbrido para otimização do escalonamento de tarefas independentes em máquinas heterogêneas
Título(s) alternativo(s): A hybrid genetic algorithm for optimizing the scheduling of independent tasks on heterogeneous machines
Autor(es): Sousa, José Junio Ribeiro
Primeiro orientador: Gabriel, Paulo Henrique Ribeiro
Primeiro membro da banca: Rampazzo, Priscila Cristina Berbert
Segundo membro da banca: Fernandes, Márcia Aparecida
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
Área(s) do CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Assunto: Computação
Algorítmos genéticos
Integração de aplicações corporativas (Sistemas de computação)
Redes de computadores
Idioma: por
País: Brasil
Editora: Universidade Federal de Uberlândia
Programa: Programa de Pós-graduação em Ciência da Computação
Referência: 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
Identificador do documento: http://doi.org/10.14393/ufu.di.2022.582
URI: https://repositorio.ufu.br/handle/123456789/36613
Data de defesa: 27-Set-2022
Aparece nas coleções:DISSERTAÇÃO - Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
AlgoritmoGeneticoHibrido.pdfDissertação2.46 MBAdobe PDFThumbnail
Visualizar/Abrir


Este item está licenciada sob uma Licença Creative Commons Creative Commons