Publicado no Encontro de Saberes 2014
Evento: XXII Seminário de Iniciação Científica
Área: ENGENHARIAS
Subárea: Engenharia de Produção
| Título |
| Um algoritmo híbrido para resolução do problema job shop scheduling com penalidade pelo tempo de atraso |
| Autores |
|
Tiago Pinheiro Dos Santos (Autor) Raphael Carlos Cruz (Autor) Marcone Jamilson Freitas Souza (Autor) |
| Resumo |
| Este trabalho tem seu foco no problema de programação da produção, mais especificamente a programação do tipo Job-Shop com penalidade pelo tempo de atraso em relação à data de entrega.No problema tratado, cada job consiste de um conjunto de tarefas que devem ser processadas em uma determinada máquina durante um período de tempo ininterrupto e predeterminado. Cada job tem uma data de entrega e o objetivo é minimizar o atraso na conclusão da operação. Este problema aparece em vários setores industriais, como por exemplo, nas indústrias siderúrgicas, têxteis e químicas. Sua aplicabilidade e dificuldade de solução por técnicas exatas foram elementos motivadores do presente estudo. Neste trabalho é proposto um algoritmo híbrido para resolvê-lo. O algoritmo combina os procedimentos Descida em Vizinhança Variável (VND), Busca Tabu (BT) e o método matemático Branch-and-Bound (B&B), como buscas locais do Iterated Local Search (ILS). A BT somente é acionada após certo número de iterações sem melhora do VND. O B&B, por sua vez, é acionado apenas depois de um determinado número de iterações sem melhora da BT. O algoritmo proposto ainda contém um módulo de Reconexão por Caminhos, o qual é acionado a cada iteração do algoritmo para conectar um ótimo local a uma solução elite gerada durante a busca.O algoritmo foi testado em 47 problemas-teste da literatura e comparado a outros três algoritmos, considerados os melhores para a solução do problema em estudo.Os experimentos computacionais realizados mostraram que o algoritmo proposto gera soluções de alta qualidade e baixa variabilidade, produzindo desvios de 0,028%, na média, em relação às melhores soluções conhecidas. Além disso, ele obteve o segundo melhor desempenho, tendo a vantagem sobre o primeiro de requerer a calibragem de menos parâmetros e ser de implementação mais fácil. Esses resultados validam, portanto, sua utilização como uma alternativa para as empresas na busca pela redução de seus custos de produção. |
