Beam Search Algorithms for Minimizing Tool Switches on a Flexible Manufacturing System

In the minimization of tool switches problem we seek a sequence to process a set of jobs so that the number of tool switches required is minimized. In this work different variations of a heuristic based on partial ordered job sequences are implemented and evaluated. All variations adopt a depth first strategy of the enumeration tree. The computational test results indicate that good results can be obtained by a variation which keeps the best three branches at each node of the enumeration tree, and randomly choose, among all active nodes, the next node to branch when backtracking.

Um algoritmo enumerativo baseado em ordenamento parcial para resolução do problema de minimização de trocas de ferramentas

No problema de minimização de troca de ferramentas procura-se por uma sequência para processar um conjunto de tarefas de modo que o número requerido de trocas de ferramentas seja o menor possível. Neste trabalho propõe-se um algoritmo para resolver este problema baseado em um ordenamento parcial das tarefas. Uma sequência ótima é obtida expandindo-se as sequências parciais enumeradas. Testes computacionais são apresentados.

Uma nova heurística para o problema de minimização de trocas de ferramentas

O problema de minimização de troca de ferramentas (MTSP) busca uma sequência de processamento de um conjunto de tarefas, de modo a minimizar o número de trocas de ferramentas requeridas. Este trabalho apresenta uma nova heurística para o MTSP, capaz de produzir bons limitantes superiores para um algoritmo enumerativo. Esta heurística possui duas fases: uma fase construtiva que é baseada em um grafo em que os vértices correspondem a ferramentas e existe um arco k = (i, j) que liga os vértices i e j se e somente se as ferramentas i e j são necessárias para a execução de alguma tarefa k; e uma fase de refinamento baseada na meta-heurística Busca Local Iterativa. Resultados computacionais mostram que a heurística proposta tem um bom desempenho para os problemas testados, contribuindo para uma redução significativa no número de nós gerados de um algoritmo enumerativo.