Publicado no Encontro de Saberes 2016
Evento: XXIV Seminário de Iniciação Científica
Área: ENGENHARIAS
Subárea: Engenharia de Controle e Automação
Órgão de Fomento: Fundação de Amparo à Pesquisa do Estado de Minas Gerais
| Título |
| Estudo e implementação de técnicas de busca em vizinhança de grande porte ao problema de sequenciamento de máquinas paralelas |
| Autores |
|
EDUARDO DE OLIVEIRA FERREIRA (Autor) Gustavo Peixoto Silva (Orientador) |
| Resumo |
| Este trabalho aborda o problema de sequenciamento de um conjunto de tarefas em uma série de máquinas paralelas e uniformes. Para cada tarefa é conhecido o seu tempo de processamento, a sua data de entrega e o peso por dia de atraso da data de finalização da tarefa em relação à sua data de entrega. O objetivo do problema é sequenciar as tarefas nas máquinas, tal que cada tarefa seja realizada em uma única máquina, cada máquina realize uma única tarefa por vez e que seja minimizada a soma dos atrasos ponderados. Este problema é conhecido na literatura como parallel machines total weighted tardiness problem. Existem duas questões essenciais em problemas de sequenciamento de máquinas paralelas, que são: i) o particionamento das tarefas entre as máquinas e ii) o sequenciamento das tarefas em cada máquina. Em um trabalho desenvolvido anteriormente pelos autores, foi implementada a técnica de busca local Very Large-scale Neighborhood Search - VLNS para otimizar o particionamento das tarefas entre as máquinas. Nesta implementação, o sequenciamento das tarefas em cada máquina foi realizado pelo método clássico de busca local First Improvement baseado na troca generalizada de pares de tarefas, ou, Generalized Pairwise Interchanges. Neste trabalho será apresentada a implementação da busca VLNS também para a segunda etapa do problema, ou seja, para definir a melhor sequencia das tarefas em cada máquina. Desta forma, integrando as duas implementações, ambas as etapas serão otimizadas por uma técnica de busca em vizinhança de grande porte. Desta nova forma, pode-se obter resultados mais interessantes, uma vez que a VLNS é uma busca mais abrangente do que as buscas clássicas, permitindo uma troca em série das tarefas pertencentes a uma mesma máquina. Neste contexto, a busca é denominada Dynasearch. A implementação será testada com dados benchmark da literatura e seus resultados serão comparados com aqueles obtidos anteriormente e os disponíveis na literatura. |
