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

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

Título alternativo A new heuristic for the minimization of tool switches problem
Autor Chaves, Antonio Augusto Autor UNIFESP Google Scholar
Senne, Edson Luiz França Google Scholar
Yanasse, Horacio Hideki Autor UNIFESP Google Scholar
Instituição Universidade Federal de São Paulo (UNIFESP)
Universidade Estadual Paulista (UNESP)
Instituto Nacional de Pesquisas Espaciais
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.
Palavra-chave Scheduling
Tool switches
Heuristic
Graph
Metaheuristic
Sequenciamento
Troca de ferramentas
Heurística
Grafo
Meta-heurísticas
Idioma Português
Data de publicação 2012-01-01
Publicado em Gestão & Produção. Universidade Federal de São Carlos, v. 19, n. 1, p. 17-30, 2012.
ISSN 0104-530X (Sherpa/Romeo)
Publicador Universidade Federal de São Carlos
Extensão 17-30
Fonte http://dx.doi.org/10.1590/S0104-530X2012000100002
Direito de acesso Acesso aberto Open Access
Tipo Artigo
SciELO S0104-530X2012000100002 (estatísticas na SciELO)
Endereço permanente http://repositorio.unifesp.br/handle/11600/6831

Exibir registro completo




Arquivo

Nome: S0104-530X2012000100002.pdf
Tamanho: 494.1KB
Formato: PDF
Descrição:
Abrir arquivo

Este item está nas seguintes coleções

Buscar


Navegar

Minha conta