Heurísticas de programação matemática para o problema de dimensionamento de lotes de múltiplos itens com restrições de capacidade e máquinas paralelas distintas

Abstract

Lot-sizing problems are among the most relevant in the production planning literature. This work addresses the Multi-Item Capacitated Lot-Sizing Problem with Unrelated Parallel Machines (CLSP-PM), classified as NP-hard and aiming to determine an optimal production plan that meets periodic demands without exceeding machine capacities while minimizing total costs. The problem is tackled through heuristic methods combined in three different ways: (i) Relax-and-Fix is applied to generate an initial solution, followed by Fix-and-Optimize as a local search procedure, in both static and dynamic versions. (ii) A Column Generation-Based Heuristic (HCG) is then used as a constructive method, combined with Fix-and-Optimize, comparing the resolution of the pricing problem via Dynamic Programming (DP) and Mixed Integer Programming (MIP). (iii) The HCG is further extended with a production transfer heuristic (TH) to ensure solution feasibility, maintaining the comparisons between DP and MIP, and using both static and dynamic versions of Fix-and-Optimize for each case. Experiments on 2,880 benchmark instances show that, in particular, the combination of HCG with DP, TH, and dynamic Fix-and-Optimize achieved near-zero gaps in several instance classes. These results outperform literature methods in solution quality, reaching average gaps of 0.51% for the static version and 0.42% for the dynamic version, with competitive computing times.