An effective heuristic algorithm based on segmentation for solving a multilevel lot-sizing problem

This paper presents an effective heuristic algorithm for solving the multilevel lot-sizing problem, which is an important decision making process in manufacturing production systems and a well-known benchmark of combinatorial optimization problems. The heuristic algorithm is based on the soft optimization approach, which was reported recently that it can lead to a good enough solution with a high probability in solving the multilevel lot-sizing problem. However, its performance in value was not satisfying. This paper will develop an algorithm based on segmentation to use the structure information of the lot-sizing problem in sampling so that a better performance can be achieved. The effectiveness of the heuristic algorithm is shown in comparative computing experiments with the soft optimization approach and the genetic algorithm.