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: Universidade Federal de Ouro Preto
| Título |
| Algoritmos heurísticos para solução do problema Job-Shop com penalização por atraso |
| Autores |
|
MATEUS HONORATO DE FARIA (Autor) MARCONE JAMILSON FREITAS SOUZA (Orientador) Manoel Victor Stilpen Moreira de Sa (Co-Autor) Vitor Nazário Coelho (Co-Orientador) |
| Resumo |
| Este trabalho tem seu foco no problema Job-Shop scheduling com penalização do atraso total. Nesse problema, há um conjunto de tarefas que devem ser processadas 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. Cada tarefa deve ser finalizada em uma data previamente conhecida e atrasos são penalizados. O objetivo considerado é o de minimizar o custo total gerado pelo atraso na finalização das 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) 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 por um procedimento baseado na regra de despacho Shortest Processing Remaining Time (SPRT), que 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. |
