Publicado no Encontro de Saberes 2017
Evento: XXV Seminário de Iniciação Científica
Área: CIÊNCIAS EXATAS E DA TERRA
Subárea: Ciência da Computação
Órgão de Fomento: Fundação de Amparo à Pesquisa do Estado de Minas Gerais
| Título |
| O USO DE TÉCNICAS DE BUSCA EM VIZINHANÇA DE GRANDE PORTE PARA O PROBLEMA DE SEQUENCIAMENTO DE TAREFAS EM MÁQUINAS PARALELAS |
| Autores |
|
EDUARDO DE OLIVEIRA FERREIRA (Autor) Gustavo Peixoto Silva (Orientador) |
| Resumo |
| Este trabalho trata do problema de sequenciamento de tarefas em máquinas paralelas e uniformes (parallel machines total weighted tardiness problem). O objetivo é sequenciar as tarefas tal que cada tarefa seja realizada em uma máquina, cada máquina realize uma tarefa por vez e seja minimizada a soma dos atrasos ponderados. Existem duas questões na resolução do problema: o particionamento das tarefas entre as máquinas e o sequenciamento das tarefas em cada máquina. A contribuição deste trabalho é resolver as duas etapas com heurísticas de busca de grande porte. A técnica Very Large-scale Neighborhood Search, que usa grafos de melhoria, é empregada para realizar o particionamento das tarefas, e um algoritmo de Programação Dinâmica Dynasearch realiza o sequenciamento das tarefas nas máquinas. Ambas as buscas são combinadas na metaheurística ILS e os resultados são comparados com aqueles obtidos utilizando o ILS-VLNS combinado com o método de busca local First Improvement. A técnica Very Large-scale Neighborhood Search combinada com a Programação Dinâmica Dynasearch, batizada de ILS-DVLNS, produziu resultados que mostraram que o método estudado é mais eficiente do que os obtidos utilizando o ILS-VLNS, principalmente quando se aumenta o número de tarefas por máquina. De forma geral, a técnica ILS-DVLNS produz resultados satisfatórios de maneira eficiente. |
