Proposta de dois modelos matemáticos e abordagens heurísticas de resolução para problemas de produção em dois estágios com estoque intermediário
Abstract
Resumo: Este trabalho trata especificamente de Problemas de Produção Multiestágios. Processos que ocorrem em mais de um estágio produtivo se caracterizam pela necessidade de sincronia entre os estágios e, em geral, pela dependência que há entre eles. Esta configuração exige que sejam realizadas as atividades de dimensionamento e sequenciamento de lotes de forma integrada, o que torna tanto os modelos quanto a resolução dos problemas complexos. Sendo assim, o objetivo deste trabalho é detectar características importantes dos problemas de produção multiestágio, bem como propor modelos matemáticos e métodos de resolução para estes. Realizou-se uma revisão sistemática da literatura acerca dos problemas multiestágios abordados na literatura e identificou-se os métodos de resolução mais utilizados. São apresentados dois modelos matemáticos para dois estágios com estoque intermediário. Além disso são propostas cinco diferentes abordagens de resolução, sendo 4 destas abordagens heurísticas. São propostas duas formas de encontrar uma solução inicial e 4 heurísticas de melhoria. Propõe-se para solução inicial a primeira solução incumbente encontrada pelo solver Gurobi, chamada neste trabalho de abordagem MIP Sol, e uma heurística construtiva que se baseia na premissa da divisão dos problemas em subproblemas. A partir das soluções iniciais encontradas aplicou-se heurísticas de melhoria como: RINS (Relaxation Induced Neighborhood Search) e três diferentes estratégias da heurística Fix and Optimize (F&O). No que concerne aos resultados obtidos neste trabalho, para alguns problemas a heurística RINS apresentou desempenho satisfatório quando comparada à resolução do modelo matemático exato. Já quanto as estratégias que utilizam a heurística construtiva e estratégias de F&O., para casos em que se tem setup não dependente da sequência e duas máquinas por estágio, as estratégias Backward e Forward apresentam melhores resultados quanto a tempo e qualidade de solução, no entanto quando se tem setup dependente da sequência e aumenta-se o número de máquinas por estágio, a estratégia para dois períodos proposta neste trabalho, apresenta melhores resultados. Concluiu-se que as abordagens de resolução propostas são satisfatórias para problemas de até 15 itens, sendo que para os problemas mais complexos a estratégia de F&O para dois períodos apresenta o melhor resultado. Palavras-Chave: Dimensionamento de Lotes. Sequenciamento. Problema Multiestágio. Estoque intermediário. Abordagens heurísticas. Abstract: This work deals specifically with Multi-Stage Production Problems. Processes that occur in more than one productive stage are characterized by the need for synchrony and in general by the dependence between the stages. This configuration requires that lot-sizing and scheduling activities simultaneously performed, which makes both the models and the complex problems resolution. Thus, the aims of this work are to detect significant characteristics of multi-stage production problems, as well as to propose mathematical models and resolution methods for them. A systematic literature review on multistage problems addressed in the literature was carried out, to identify the most used resolution methods. This work presents two mathematical models for two stages with intermediate stock. We also proposed five different approaches to solving the problems, four of which are heuristic approaches. We presented two ways of finding an initial solution and four improvement heuristics. The initial solution taken is the first incumbent found by the solver, called in this work of MIP Sol approach. Besides that, we created a constructive heuristic based on the premise of the division of the problems into sub-problems. Improvement heuristics like RINS (Relaxation Induced Neighborhood Search) and three different strategies of the heuristic Fix and Optimize (F.O) were used to improve the initial solutions. Regarding the results obtained in this work, for some problems the RINS heuristic was satisfactory when compared to the resolution of the exact mathematical model. As far as the approaches that use constructive heuristics and F&O strategies are concerned, in cases where setup is not dependent on the sequence and two machines per stage, the Backward, and Forward strategies present better results in terms of time and quality of the solution. However, when the sequence-dependent setup is required, and the number of machines per stage is increased, the two periods F&O strategy proposed in this work presents better results. It is possible to conclude that the proposed resolution approaches are satisfactory for problems of up to 15 items, and for the most complex problems the F&O. For two periods have better results. Keywords: Lot-sizing. Scheduling. Multilevel Problem. Buffer. Heuristics approaches.
Collections
- Dissertações [120]