Publicado no Encontro de Saberes 2017
Evento: XXV Seminário de Iniciação Científica
Área: CIÊNCIAS EXATAS E DA TERRA
Subárea: Ciência da Computação
Título |
Uma Heurística Aplicada ao Problema de Minimização de Pilhas Abertas |
Autores |
JOAO VITOR MASCARENHAS DOS SANTOS (Autor) Marco Antonio Moreira de Carvalho (Orientador) |
Resumo |
Este trabalho apresenta um método heurístico para o Problema de Minimização de Pilhas Abertas (ou MOSP, do inglês Minimization of Open Stack Problem), um problema de sequenciamento de padrões de corte. Neste contexto, o problema pede por uma permutação dos padrões de corte tal que a utilização do estoque intermediário seja minimizada, minimizando também a manipulação desnecessária dos padrões cortados. O método proposto se baseia em busca em grafos seguida por procedimentos de busca local e é comparada com dois métodos da literatura em experimentos computacionais abrangentes que consideraram conjuntos de instâncias reais e artificiais da literatura. Os resultados reportados mostram que o método proposto, em um curto intervalo de tempo, pôde igualar boa parte dos melhores resultados da literatura, aprimorar alguns deles e também obter um baixo gap quando comparado às soluções ótimas e limitantes inferiores disponíveis. |