Please use this identifier to cite or link to this item: http://riu.ufam.edu.br/handle/prefix/5828
metadata.dc.type: Trabalho de Conclusão de Curso
Title: Heurísticas e meta-heurísticas aplicadas a problemas de escalonamento de tarefas baseadas em datas de término sugeridas
metadata.dc.creator: Aguiar, Thuan Matheus Silva de
metadata.dc.contributor.advisor1: Amorim, Rainer Xavier de
metadata.dc.contributor.referee1: Freitas, Carlos Alberto Oliveira de
metadata.dc.contributor.referee2: Silva, Marcos Thomaz da
metadata.dc.description.resumo: As heurísticas e meta-heurísticas são métodos aproximados que vem se mostrando bastante promissores na resolução de problemas de otimização combinatória. São aplicadas em problemas complexos, ou que apresentam grande dificuldade de resolução, mesmo para um computador, em geral problemas NP-difíceis. Neste contexto, este trabalho tem como objetivo é identificar as heurísticas e meta-heurísticas que podem ser aplicadas ao escalonamento de tarefas com datas de término sugeridas. O método adotado consistiu em um estudo secundário denominado Mapeamento Sistemático (MS) para identificar as estratégias algorítmicas aplicadas ao problema investigado, juntamente com experimentação e análise empírica da execução de um Algoritmo Genético com Busca Local e Reconexão de Caminhos (GLS+PR). Como resultado do MS foram identificadas 13 tipos de estratégias algorítmicas, dentre as 30 publicações levantadas no MS, sendo que boa parte destas aplicam o algoritmo de busca local. O MS permitiu levantar as instâncias de testes da literatura para diferentes variações de problemas de escalonamento baseado em datas de término sugeridas. Quanto aos resultados dos experimentos computacionais realizados com o GLS+PR, foi identificado que esta abordagem fornece soluções competitivas em relação à literatura, para as baterias de teste realizadas com 40, 50 e 100 tarefas em 2, 4 e 10 máquinas paralelas idênticas.
Abstract: Heuristics and meta-heuristics are approximate methods that have been shown to be very promising in solving combinatorial optimization problems. Are applied to problems complex or difficult to solve, even for a computer, in general NP-difficult problems. In this context, this work aims to identify the heuristics and meta-heuristics that can be applied to task scheduling with dates suggested termination dates. The method adopted consisted of a secondary study called Mapping Systematic (MS) to identify the algorithmic strategies applied to the problem investigated, along with experimentation and empirical analysis of the execution of an Algorithm Genetics with Local Search and Path Reconnection (GLS + PR). As a result of the MS, 13 types of algorithmic strategies were identified, among the 30 publications raised in the MS, most of which apply the local search algorithm. The MS allowed to raise the literature testing instances for different variations of scheduling problems based on on suggested end dates. As for the results of computational experiments with GLS + PR, it was identified that this approach provides competitive solutions in relation to the literature, for the test batteries performed with 40, 50 and 100 tasks in 2, 4 and 10 identical parallel machines.
Keywords: Heurísticas
Meta-heurísticas
Otimização Combinatória
Escalonamento de Tarefas
metadata.dc.subject.cnpq: CIÊNCIAS EXATAS E DA TERRA
metadata.dc.language: por
metadata.dc.publisher.country: Brasil
metadata.dc.publisher.department: Instituto de Ciências Exatas e Tecnologia
metadata.dc.publisher.course: Engenharia de Software - Bacharelado - Itacoatiara
metadata.dc.rights: Acesso Aberto
URI: http://riu.ufam.edu.br/handle/prefix/5828
metadata.dc.subject.controlado: Algoritmo Genético com Busca Local
Reconexão de Caminhos
Estratégias algorítmicas
Escalonamento de tarefas
Appears in Collections:Trabalho de Conclusão de Curso - Graduação

Files in This Item:
File Description SizeFormat 
TCC_ThuanAguiar.pdfTCC Engenharia de Software2,82 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.