Modelos e técnicas de local branching para o problema de abastecimento de linhas de montagem

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