A Simple Heuristic Algorithm Based on Segmentation to Solve Multilevel Lot-sizing Problems

We have developed an effective heuristic algorithm based on segmentation to solve the multilevel lot-sizing problems in a series assembly product structure (Kaku and Xu 2006, Kaku, Li and Xu 2008). The heuristic algorithm segments the solution space and guides the search direction in which a better solution is able to exist, by using the solution structure information of the multilevel lot-sizing problem, so that better performance can be achieved. In this paper, we extend the heuristic algorithm to general case of multilevel lot sizing problem with time-invariant cost structures and no restrictive assumption on the product structure. Comparing with the results obtained by the genetic algorithm (developed by Dellaert and Jeunet 2000, Dellaert, Jeunet and Jonard 2000), the effectiveness of the heuristic algorithm is shown by simulation experiments.