Modelos e técnicas de local branching para o problema de abastecimento de linhas de montagem
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Alexandre Salles da Cunha
Carlos Roberto V de Carvalho
Ricardo Saraiva de Camargo
Carlos Roberto V de Carvalho
Ricardo Saraiva de Camargo
Resumo
O problema de abastecimento de linhas de montagem pode ser observado na indústria automobilística, onde os sistemas de manufatura normalmente apresentam linhas de produção paralelas dedicadas à montagem de diferentes famílias de produtos. Neste contexto, um processo de abastecimento deve garantir o fornecimento dos itens necessários para as linhas de produção realizarem suas operações, sendo desejável a utilização de políticas de abastecimento que possam reduzir os custos associados ao processo. O problema objeto de estudo possui características de sequenciamento e dimensionamento de lotes, se apresentando como um problema de NP-difícil para o qual encontrar uma solução viável pode ser considerado um problema NP-completo. Este trabalho realiza uma comparaçao de diferentes formulações matemáticas para o problema, avaliando a influência das diferentes formulações em métodos de solução considerando instâncias de tamanho real. É realizado um ensaio sobre a utilização de desigualdades váidas para o problema propostas na literatura utilizando um algoritmo de planos de corte simples e avaliando o efeito da adição de cortes à formulação durante a solução do problema utilizando pacotes de otimizaçao. São propostas três abordagens para a solução do problema baseadas na técnica de local branching, dentre as quais uma abordagem que gera um conjunto elite de soluções utilizando GRASP e que aproveita informaçõe extraídas através da solução da relaxação linear do problema, abordagem que se destaca por apresentar resultados promissores e diversas oportunidades para a realização de trabalhos futuros.
Abstract
The problem faced when feeding assembly lines can be seen in the automobile industry in which manufacturing systems usually have parallel production lines dedicated to assembling different product families. In this context, a feeding process must deliver the necessary items to ensure that the assembly lines can perform their operations, being highly desirable the use feeding policies that can reduce the costs associated with the feeding process. The problem evaluated in this study has similarities with lot sizing and sequencing problems, and it has been shown in the related literature that solving the problem is NP-hard whereas finding a valid solution can be considered NP-complete.This study makes a comparison of different mathematical formulations for the problem, assessing the influence of different formulations when solving real size instances of the problem. Experiments are made to evaluate the use of valid inequalities for the problem as proposed in the literature, using a simple cutting planes algorithm and evaluating theaddition of cuts to the formulation during the solving process when optimization packages are used. The study proposes three approaches for solving the problem based on the local branching technique, one of which is an approach that generates a set of elite solutions using GRASP and also takes advantage of information extracted from solving the linear relaxation of the problem, an approach which stands out by showing promising results and several opportunities for conducting future work.Keyw
Assunto
Engenharia de produção
Palavras-chave
Abastecimento de linhas de montagem, Modelagem matematica, Otimizacao combinatoria, Local branching