Um estudo sobre métodos heurísticos aplicados ao sequenciamento da produção em sistemas de manufatura flexíveis.

Abstract

O Problema de Minimização de Trocas de Ferramentas (SSP, do inglês Job Sequencing and Tool Switching Problem) consiste em determinar uma ordem para o processamento de tarefas em uma máquina flexível. Cada tarefa requer um subconjunto de ferramentas específico dentre todas as que estão disponíveis para utilização. A máquina flexível é capaz de armazenar as ferramentas requisitadas por uma tarefa, mas não tem capacidade suficiente para armazenar todas as ferramentas disponíveis simultaneamente. Devido a esta restrição de capacidade, pode ser necessário efetuar trocas de ferramentas entre tarefas, que exigem a paralisação da linha de produção. Desta forma, sequenciar as tarefas de forma otimizada leva a um menor número de trocas de ferramentas e consequentemente, menor tempo ocioso da linha de produção. O SSP pertence ao conjunto de problemas classificados como NP-Difícil. Neste trabalho, o SSP é modelado como Problema do Caixeiro Viajante Generalizado (GTSP, do inglês Generalized Traveling Salesman Problem). Deseja-se solucionar tal modelagem por meio dos métodos heurísticos busca local iterada e Generalized Lin-Kernighan Helsgaun. Os resultados obtidos demonstram que a modelagem é promissora, embora esteja limitada a solucionar instâncias cujos arquivos de entrada devidamente transformados tenham tamanhos compatíveis com a memória primária disponível. Esta limitação se deve à relação direta entre o número de vértices gerados e o tamanho dos arquivos de entrada gerados para os métodos heurísticos. Para as instâncias que foram devidamente solucionadas, foi possível encontrar soluções que distam percentualmente das melhores soluções conhecidas entre 0 e 10%.