Combining relax-and-fix and fix-and-optimize approaches to solve the Multi-Item Capacitated Lot-Sizing Problem with Unrelated Parallel Machines

Lot-sizing problems play a central role in production planning. This work addresses the Multi-Item Capacitated Lot-Sizing Problem with Unrelated Parallel Machines, an NP-hard problem that consists of determining an optimal production plan that satisfies periodic demands, respects machine capacity constraints, and minimizes total cost. In this paper, we propose a two-phase heuristic approach in which: (i) a feasible solution is constructed using a relax-and-fix strategy, and (ii) a fix-and-optimize procedure is applied as a local search in the second phase. More specifically, we consider two variants of the fix-and-optimize procedure: a static version and a dynamic version. The static variant corresponds to a traditional implementation, in which the parameters remain unchanged throughout the execution. In contrast, the dynamic version adaptively adjusts its window and step sizes during the search, allowing the method to expand or restrict the search space according to the observed improvements. To our knowledge, this is the first study to combine relax-and-fix with a dynamic fix-and-optimize framework for solving the Multi-Item Capacitated Lot-Sizing Problem with Unrelated Parallel Machines. This adaptive mechanism enables a more effective exploration of the solution space and improves the ability of the method to escape from locally optimal solutions. Computational experiments conducted on a benchmark set of 2880 instances show that the proposed approaches consistently outperform state-of-the-art methods. Specifically, the static and the dynamic approaches were able to find 372 and 528 optimal solutions, respectively, with maximum optimality gaps of 2.28% and 2.26%, and average gaps of 0.45% and 0.39%. Overall, the static approach achieved a 76.9% improvement in optimality gap compared to the best approach from the literature, while also reducing the average computational time by 19.4%. In turn, the dynamic approach achieved an 80% improvement in optimality gap and, despite being slightly slower, required only 1.4 × the runtime of the best method from the literature. • We present two-phase approaches combining relax-and-fix and fix-and-optimize heuristics. • A backtracking procedure for relax-and-fix is applied to avoid infeasibility. • A dynamic variant of fix-and-optimize is devised for intensified local search. • Up to 80% of average gap improvement over the best literature results is obtained. • Detailed computational results are made publicly available for reproducibility.