Matheuristics for the lot sizing problem with back-ordering, setup carry-overs, and non-identical machines

Abstract In this study, the capacitated lot-sizing problem (CLSP) with back-ordering, setup carry-overs between periods, and non-identical parallel machines (CLSP-BOPM) is considered. The problem is one of the most general extensions of the well-known economic lot scheduling problems (ELSPs). Three matheuristics are designed and implemented starting from the ideas of variable neighborhood local search, local branching, and feasibility pump (FP), adapted and improved by considering the specific characteristics of the problem. Algorithms are tested on a set of medium to large problem instances. The FP algorithm outperforms all other algorithms and two different mixed-integer programming solvers as it requires a shorter computational time. To test the robustness of the algorithm, tests on three particular cases of the general problem, belonging to the family of discrete ELSPs, have been performed. Results from the proposed solver and a known specific state-of-the-art algorithm demonstrate substantial improvements.