Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/36613
Full metadata record
DC FieldValueLanguage
dc.creatorSousa, José Junio Ribeiro-
dc.date.accessioned2022-12-16T18:55:41Z-
dc.date.available2022-12-16T18:55:41Z-
dc.date.issued2022-09-27-
dc.identifier.citationSOUSA, 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.582pt_BR
dc.identifier.urihttps://repositorio.ufu.br/handle/123456789/36613-
dc.description.abstractIn 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.pt_BR
dc.languageporpt_BR
dc.publisherUniversidade Federal de Uberlândiapt_BR
dc.rightsAcesso Abertopt_BR
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/us/*
dc.subjectAlgoritmos Genéticospt_BR
dc.subjectAlgoritmos Híbridospt_BR
dc.subjectAmbientes Heterogêneospt_BR
dc.subjectProblemas de Escalonamentopt_BR
dc.subjectBusca Localpt_BR
dc.subjectModelo ETCpt_BR
dc.subjectTask Schedulingpt_BR
dc.subjectGenetic Algorithmpt_BR
dc.subjectLocal Searchpt_BR
dc.subjectETC Modelpt_BR
dc.titleUm algoritmo genético híbrido para otimização do escalonamento de tarefas independentes em máquinas heterogêneaspt_BR
dc.title.alternativeA hybrid genetic algorithm for optimizing the scheduling of independent tasks on heterogeneous machinespt_BR
dc.typeDissertaçãopt_BR
dc.contributor.advisor1Gabriel, Paulo Henrique Ribeiro-
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/3181954061121790pt_BR
dc.contributor.referee1Rampazzo, Priscila Cristina Berbert-
dc.contributor.referee1Latteshttp://lattes.cnpq.br/7297488900077729pt_BR
dc.contributor.referee2Fernandes, Márcia Aparecida-
dc.contributor.referee2Latteshttp://lattes.cnpq.br/8946715881289701pt_BR
dc.creator.Latteshttp://lattes.cnpq.br/4518785263457649pt_BR
dc.description.degreenameDissertação (Mestrado)pt_BR
dc.description.resumoNos ú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.pt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.programPrograma de Pós-graduação em Ciência da Computaçãopt_BR
dc.sizeorduration60pt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpt_BR
dc.identifier.doihttp://doi.org/10.14393/ufu.di.2022.582pt_BR
dc.orcid.putcode124850479-
dc.crossref.doibatchid87b7282b-0a46-40d2-85e8-54e1080f7d06-
dc.subject.autorizadoComputaçãopt_BR
dc.subject.autorizadoAlgorítmos genéticospt_BR
dc.subject.autorizadoIntegração de aplicações corporativas (Sistemas de computação)pt_BR
dc.subject.autorizadoRedes de computadorespt_BR
Appears in Collections:DISSERTAÇÃO - Ciência da Computação

Files in This Item:
File Description SizeFormat 
AlgoritmoGeneticoHibrido.pdfDissertação2.46 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons