Neighborhood search techniques of evolutionary algorithms for solving multilevel lot-sizing problems

The multi-level lot-sizing (MLLS) problem has been widely studied but still plays an important role in the efficient operation of modern manufacturing and assembly processes. The MLLS problem without restrictive assumption on the product structure is difficult to be solved because it is NP-hard and the situation is even exacerbated by the increasing structure complexity of modern products. Several evolutionary algorithms have been developed recently in literature to solve acceptable solutions for the MLLS problem within reasonable time, such as genetic algorithm, simulated annealing, swarm particle optimization, soft optimization based on segmentation, ant colony optimization and variable neighborhood search. In this paper we investigate the implemental techniques used by these evolutionary algorithms for solve the MLLS problem. We found that the distance and change range are two main factors that influence much the effectives of these neighborhood-search-based evolutionary algorithms. These insights can help developing more efficient evolutionary algorithms, and as an example, we developed an iterated neighborhood search(INS) algorithm which shows its good performances when tested against two benchmark problem sets(small-sized and medium-sized).