A variable neighborhood decomposition search algorithm for multilevel capacitated lot-sizing problems

The multi-level capacitated lot-sizing problem (MLCLSP) has been an important part of material requirement planning (MRP) system. In this paper we combine variable neighborhood decomposition search and accurate mixed integer programming (VNDS-MIP) to solve MLCLSP. This method is based on the variable neighborhood search, and with the use of exact LP/MIP solvers ILOG CPLEX, it's proved to be very efficient in solving MLCLSP problem. Computational experiments are carried out on three classes of benchmark instances and VNDS-MIP shows good performance in solving the lot-sizing problem. For the 300 small-sized instances, the VNDS-MIP algorithm can find 97.67% of the optimal solutions in several seconds; for the 150 medium-sized instances, the VNDS-MIP algorithm is better than the other methods.