Combining population-based and exact methods for multi-level capacitated lot-sizing problems

Abstract

We present an ant-based algorithm to solve multi-level capacitated lot-sizing problems. We apply a hybrid approach where we use the ant system to optimize the decomposition of the problem into smaller subproblems. These subproblems, containing only a few items and periods, are solved using CPLEX. Then the overall solution is derived by consolidating the partial solutions. This hybrid approach provides superior results with respect to solution quality in comparison with the existing approaches in the literature.

§This research emerged from the PhD thesis of Rapeepan Pitakaso during his stay at the University of Vienna.

Keywords:

• Ant colony optimization
• Multi-level lot sizing
• Material requirements planning
• Problem decomposition
• Mixed-integer program

Acknowledgements

We would like to thank Regina Berretta, Horst Tempelmeier, and Hartmut Stadtler for providing the test data. Furthermore, we are grateful to Martin Romauch for helpful comments concerning the use of CPLEX. Finally, financial support from the Austrian Exchange Office (ÖAD) to the first author is gratefully acknowledged.

Notes

§This research emerged from the PhD thesis of Rapeepan Pitakaso during his stay at the University of Vienna.

† The results of Berretta and Rodrigues (2004) were evaluated on a Sun UltraSPARC 60. Since the computational speed of this machine is not included in the paper of Dongarra (2005), we used the similar Sun UltraSPARC 80 for comparison. Hence, the computer we used is approximately 5.7 times faster.