A scatter search approach for uncapacitated multilevel lot-sizing problems

The multilevel lot-sizing (MLLS) problem is a key production planning problem in material requirements planning (MRP) systems. The MLLS problem deals with determining the production lot sizes of various items appearing in the product structure over a given finite planning horizon to minimize the production cost, the inventory carrying cost and the backordering cost. In this paper, a new evolutionary technique called scatter search (SS) is adopted to solve uncapacitated MLLS problems since SS is able to provide a wide exploration of the search space through intensification and diversification. Experiments are conducted to test the performance of SS by using 146 benchmark instances, of which there are 96 small size problems, 40 medium size problems and 10 large size problems. Comparison analysis of the SS approach with other classical heuristics and algorithms in the literature is presented. Simulation results showed that, for small-sized testing problems, SS performs the best by achieving 94 optimums out of 96 instances; for medium-sized problems, SS still shows its adaptation by finding 7 best known solutions (BKS) and 33 near-BKS solutions with small deviation; for large-sized problems, SS seems not very optimistic compared with genetic algorithm (GA) and ant systems (AS), but it still remains competitive and makes a large improvement on the initial solutions provided by Wagner-Whitin algorithm (WW) in the acceptable average runtime.