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: Conselho Nacional de Desenvolvimento Científico e Tecnológico
| Título |
| Algoritmos baseados em metaheurísticas para resolução do problema Job-shop scheduling com penalização da soma dos atrasos |
| Autores |
|
MANOEL VICTOR STILPEN MOREIRA DE SA (Autor) Marcone Jamilson Freitas Souza (Orientador) Vitor Nazário Coelho (Co-Orientador) |
| Resumo |
| Este trabalho tem seu foco no problema Job-Shop scheduling com penalização da soma dos atrasos. Este problema consiste em processar um conjunto de tarefas em um conjunto de máquinas. Cada tarefa passa por um conjunto específico de operações nessas máquinas, sendo que cada operação consome um tempo de processamento previamente definido. Cada tarefa deve ser finalizada em uma data conhecida a priori e atrasos são penalizados. O objetivo é minimizar o custo total gerado pelo atraso na finalização de todas as tarefas. Por ser um problema da classe NP-difícil, foram desenvolvidos vários algoritmos heurísticos para resolvê-lo. Esses algoritmos são baseados nas metaheurísticas Simulated Annealing, Busca em Vizinhança Variável (VNS, do inglês Variable Neighborhood Search) e GRASP e exploram características do problema para permitir uma busca mais eficaz do espaço de soluções. As soluções iniciais desses algoritmos são geradas pelo procedimento Adaptive Shortest Processing Remaining Time (ASPRT), especialmente desenvolvido para tratar o problema. A regra de despacho ASPRT consiste em escolher como operação candidata aquela cuja tarefa possui o menor tempo restante para sua finalização levando-se em consideração a diferença entre a data de término da operação candidata e sua respectiva data de entrega. Para testar os algoritmos desenvolvidos, foram usados problemas-teste clássicos da literatura e os resultados mostraram que o algoritmo VNS supera os demais na capacidade de gerar soluções finais de melhor qualidade. |
