Uma nova heurística para o problema de minimização de trocas de ferramentas
Data
2012-01-01
Autores
Chaves, Antonio Augusto [UNIFESP]
Senne, Edson Luiz França
Yanasse, Horacio Hideki [UNIFESP]
Orientadores
Tipo
Artigo
Título da Revista
ISSN da Revista
Título de Volume
Resumo
The minimization of tool switches problem (MTSP) seeks a sequence to process a set of jobs so that the number of tool switches required is minimized. This study presents a new heuristic for the MTSP. This heuristic has two phases: a constructive phase, based on a graph where the vertices correspond to tools and there is an arc k = (i, j) linking vertices i and j if and only if the tools i and j are required to execute some job; and an improvement phase, based on an Iterated Local Search. Computational results show that the proposed heuristic has a good performance on the instances tested contributing to a significant reduction in the number of nodes generated by an enumerative algorithm.
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.
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.
Descrição
Citação
Gestão & Produção. Universidade Federal de São Carlos, v. 19, n. 1, p. 17-30, 2012.