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

Alternative title A new heuristic for the minimization of tool switches problem
Author Chaves, Antonio Augusto Autor UNIFESP Google Scholar
Senne, Edson Luiz França Google Scholar
Yanasse, Horacio Hideki Autor UNIFESP Google Scholar
Institution Universidade Federal de São Paulo (UNIFESP)
Universidade Estadual Paulista (UNESP)
Instituto Nacional de Pesquisas Espaciais
Abstract 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.
Keywords Scheduling
Tool switches
Heuristic
Graph
Metaheuristic
Sequenciamento
Troca de ferramentas
Heurística
Grafo
Meta-heurísticas
Language Portuguese
Date 2012-01-01
Published in Gestão & Produção. Universidade Federal de São Carlos, v. 19, n. 1, p. 17-30, 2012.
ISSN 0104-530X (Sherpa/Romeo)
Publisher Universidade Federal de São Carlos
Extent 17-30
Origin http://dx.doi.org/10.1590/S0104-530X2012000100002
Access rights Open access Open Access
Type Article
SciELO ID S0104-530X2012000100002 (statistics in SciELO)
URI http://repositorio.unifesp.br/handle/11600/6831

Show full item record




File

Name: S0104-530X2012000100002.pdf
Size: 494.1Kb
Format: PDF
Description:
Open file

This item appears in the following Collection(s)

Search


Browse

Statistics

My Account