Combining relax-and-fix and fix-and-optimize approaches to solve the Multi-Item Capacitated Lot-Sizing Problem with Unrelated Parallel Machines
针对多物品有产能限制的无关并行机批量问题，提出两阶段启发式方法，先松弛-固定构造可行解，再固定-优化局部搜索，动态版本自适应调整参数，在2880个实例上优于现有方法。
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.