Modelos Matemáticos e Métodos de Solução para Problemas de Dimensionamento de Lotes - Fiorotto, Diego Jacinto [UNESP] (2015)
The lot sizing problem is a production optimization problem and consists of determining the quantity of products to be produced in each period of a nite time horizon, in order to meet the demand and optimize an objective function, for example, to minimize costs. In this thesis we address two di erent extensions of the standard lot sizing problem. In the rst part we consider the capacitated lot-sizing problem with multiple items, setup time and unrelated parallel machines and, in the second one, the capacitated lot sizing problem with multiple items and setup crossover. For the rst part of this thesis where we study the lot sizing problem with unrelated parallel machines, the aim is to apply di erent solution methods that use Lagrangian relaxation and Dantzig-Wolfe decomposition to obtain high quality lower bounds and develop Lagrangian heuristics to obtain good feasible solutions (upper bounds). Based on a strong reformulation of the problem as a shortest path problem and unlike in the traditional approach in which the linking constraints are the capacity constraints, we use the ow constraints, i.e. the demand constraints, as linking constraints. The aim of this approach is to obtain high quality lower bounds and for this we have used three di erent solution methods. In the rst one the Lagrangian relaxation is applied to the ow constraints. For the other two we solve the master problem applying solution methods that combine Lagrangian relaxation and Dantzig-Wolfe decomposition in a hybrid form. Two primal heuristics, based on transfers of production quantities, are used to generate feasible solutions. Computational experiments using data sets from the literature are presented and show that the solution methods produce lower bounds of excellent quality and competitive upper bounds, when compared with the bounds produced by other methods from the literature and by a high-performance MIP software...