Heurísticas e meta-heurísticas aplicadas a problemas de escalonamento de tarefas baseadas em datas de término sugeridas
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 identif...
| Autor principal: | Aguiar, Thuan Matheus Silva de |
|---|---|
| Grau: | Trabalho de Conclusão de Curso |
| Idioma: | por |
| Publicado em: |
Brasil
2020
|
| Assuntos: | |
| Acesso em linha: |
http://riu.ufam.edu.br/handle/prefix/5828 |
| id |
oai:localhost:prefix-5828 |
|---|---|
| recordtype |
dspace |
| spelling |
oai:localhost:prefix-58282025-03-10T20:29:44Z Heurísticas e meta-heurísticas aplicadas a problemas de escalonamento de tarefas baseadas em datas de término sugeridas Aguiar, Thuan Matheus Silva de Amorim, Rainer Xavier de http://lattes.cnpq.br/6851610498599368 Freitas, Carlos Alberto Oliveira de http://lattes.cnpq.br/5295896684679547 Silva, Marcos Thomaz da http://lattes.cnpq.br/1710397494828508 Heurísticas Meta-heurísticas Otimização Combinatória Escalonamento de Tarefas CIÊNCIAS EXATAS E DA TERRA: ENGENHARIA DE SOFTWARE Algoritmo Genético com Busca Local Reconexão de Caminhos Estratégias algorítmicas Escalonamento de tarefas 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. 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. 1 Não 2020-12-16T15:13:54Z 2020-12-15 2020-12-16T15:13:54Z 2020-11-26 Trabalho de Conclusão de Curso http://riu.ufam.edu.br/handle/prefix/5828 por Acesso Aberto Brasil Instituto de Ciências Exatas e Tecnologia Itacoatiara/AM Engenharia de Software - Bacharelado - Itacoatiara |
| institution |
Repositório Institucional - Universidade Federal do Amazonas |
| collection |
RI-UFAM |
| language |
por |
| topic |
Heurísticas Meta-heurísticas Otimização Combinatória Escalonamento de Tarefas CIÊNCIAS EXATAS E DA TERRA: ENGENHARIA DE SOFTWARE Algoritmo Genético com Busca Local Reconexão de Caminhos Estratégias algorítmicas Escalonamento de tarefas |
| spellingShingle |
Heurísticas Meta-heurísticas Otimização Combinatória Escalonamento de Tarefas CIÊNCIAS EXATAS E DA TERRA: ENGENHARIA DE SOFTWARE Algoritmo Genético com Busca Local Reconexão de Caminhos Estratégias algorítmicas Escalonamento de tarefas Aguiar, Thuan Matheus Silva de Heurísticas e meta-heurísticas aplicadas a problemas de escalonamento de tarefas baseadas em datas de término sugeridas |
| topic_facet |
Heurísticas Meta-heurísticas Otimização Combinatória Escalonamento de Tarefas CIÊNCIAS EXATAS E DA TERRA: ENGENHARIA DE SOFTWARE Algoritmo Genético com Busca Local Reconexão de Caminhos Estratégias algorítmicas Escalonamento de tarefas |
| description |
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. |
| author_additional |
Amorim, Rainer Xavier de |
| author_additionalStr |
Amorim, Rainer Xavier de |
| format |
Trabalho de Conclusão de Curso |
| author |
Aguiar, Thuan Matheus Silva de |
| title |
Heurísticas e meta-heurísticas aplicadas a problemas de escalonamento de tarefas baseadas em datas de término sugeridas |
| title_short |
Heurísticas e meta-heurísticas aplicadas a problemas de escalonamento de tarefas baseadas em datas de término sugeridas |
| title_full |
Heurísticas e meta-heurísticas aplicadas a problemas de escalonamento de tarefas baseadas em datas de término sugeridas |
| title_fullStr |
Heurísticas e meta-heurísticas aplicadas a problemas de escalonamento de tarefas baseadas em datas de término sugeridas |
| title_full_unstemmed |
Heurísticas e meta-heurísticas aplicadas a problemas de escalonamento de tarefas baseadas em datas de término sugeridas |
| title_sort |
heurísticas e meta-heurísticas aplicadas a problemas de escalonamento de tarefas baseadas em datas de término sugeridas |
| publisher |
Brasil |
| publishDate |
2020 |
| url |
http://riu.ufam.edu.br/handle/prefix/5828 |
| _version_ |
1831969758712430592 |
| score |
11.755432 |