Effective matheuristics for the multi-item capacitated lot-sizing problem with remanufacturing

摘要

Effective Mixed Integer Programming (MIP) based matheuristics for the multi-item capacitated lot-sizing problem with remanufacturing (CLSP-RM) are proposed in this paper. This NP-hard problem consists of determining an optimal plan for the capacitated production and remanufacture of multiple items in order to satisfy their deterministic dynamic demands over a discrete time horizon. Two constructive approaches are proposed: a column generation rounding heuristic followed by a Linear Programming (LP)/MIP repairing mechanism, and a relax-and-fix method. A fix-and-optimize local search procedure is also applied to improve the quality of the solutions obtained by the constructive techniques. Computational results show that the new approach combining a column generation rounding heuristic with a fix-and-optimize local search procedure is very competitive with the state-of-the-art heuristic. Specifically, the obtained solutions are at least as good as the best known in the literature for 86.85% of the instances, with new best solutions encountered for 69.72% of them. Moreover, all obtained solutions are within 5.54% of optimality, showing the robustness of the newly proposed approach. (C) 2018 Elsevier Ltd. All rights reserved.