'Problema de Dimensionamento de Lotes: uma abordagem via Relaxação Lagrangiana'

Abstract

A lot-sizing problem (LSP) is a production planning problem. Given a planning horizon discretized into time periods, the goal is to determine when and how many products should be produced in each period, aiming to minimize operational costs. The objective of this work is to solve an NP-hard LSP by applying Lagrangian Relaxation. This technique simplifies the problem by dualizing constraints and introducing penalties. The challenge is to determine the optimal penalties that bring the solution closer to optimality, using the subgradient method. In addition, heuristics for feasibility and improvement are proposed to obtain high-quality solutions. Finally, the efficiency of the technique for the problem under study will be evaluated based on tests performed with instances from the literature, considering the resolution time, duality gap, and the solutions obtained by the proposed approaches.