A matheuristic approach for the multi-level capacitated lot-sizing problem with substitution and backorder

The lot-sizing problem aims at determining the products to be produced and their quantities for each time period, which is a difficult problem in production planning. This problem becomes even more complicated when practical aspects such as limited production capacity, bill of materials, and item substitution are considered. In this paper, we study a new variant of the lot-sizing problem, called the multi-level capacitated lot-sizing problem with substitution and backorder. Unlike previous studies, this variant considers substitutions at both the product and component levels, which is based on the real needs of manufacturers to increase planning flexibility. Backorders are allowed, but should be delivered within a certain time limitation. We formulate this problem using a mathematical programming model. A matheuristic approach is proposed to solve the problem. This first generates an initial feasible solution using a relax-and-fix algorithm, and then improves it using a hybrid fix-and-optimise algorithm. The proposed algorithm is calibrated with a full factorial design of experiments, and its efficiency is well validated. Finally, through extensive numerical experiments, we analyse the properties of this new lot-sizing problem, such as the effect of substitution options, and the influence of backorder time limitation, and provide several useful managerial insights for manufacturing companies to save costs in production planning.