A hybrid optimization approach for multi-level capacitated lot-sizing problems

Solving multi-level capacitated lot-sizing problems is still a challenging task, in spite of increasing computational power and faster algorithms. In this paper a new approach combining an ant-based algorithm with an exact solver for (mixed-integer) linear programs is presented. A MAX-MIN ant system is developed to determine the principal production decisions, a LP/MIP solver is used to calculate the corresponding production quantities and inventory levels. Two different local search methods and an improvement strategy based on reduced mixed-integer problems are developed and integrated into the ant algorithm. This hybrid approach provides superior results for small and medium-sized problems in comparison to the existing approaches in the literature. For large-scale problems the performance of this method is among the best.