O uso de técnicas de busca em vizinhança de grande porte para o problema de programação de máquinas paralelas

Autores

  • Eduardo de Oliveira Ferreira
  • Gustavo Peixoto Silva

DOI:

https://doi.org/10.15675/gepros.v14i5.2370

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. O problema é resolvido em duas etapas: o particionamento das tarefas entre as máquinas e o sequenciamento das tarefas nas máquinas. A contribuição deste trabalho consiste em resolver as duas etapas com diferentes heurísticas de busca de grande porte e comparar suas eficiências. A técnica Very Large-scale Neighborhood Search, que utiliza um grafo de melhoria com cancelamento de ciclos negativos, é empregada para realizar o particionamento das tarefas. Um algoritmo de Programação Dinâmica, conhecido como Dynasearch, que também é uma técnica de busca em vizinhança de grande porte, realiza o sequenciamento das tarefas em cada máquina. Ambas as buscas são combinadas na metaheurística ILS. As duas versões do ILS são comparadas, resolvendo problemas benchmark da literatura.

Biografia do Autor

Gustavo Peixoto Silva


Downloads

Publicado

2019-11-01

Como Citar

de Oliveira Ferreira, E., & Silva, G. P. (2019). O uso de técnicas de busca em vizinhança de grande porte para o problema de programação de máquinas paralelas. Revista Gestão Da Produção Operações E Sistemas, 14(5), 48. https://doi.org/10.15675/gepros.v14i5.2370

Edição

Seção

Artigos