Hybrid algorithm for the two-dimensional rectangular layer-packing problem

Abstract

In this paper, a rectangular layer-packing algorithm (RLPA) combined with modified genetic algorithm (GA) or particle swarm optimization (PSO) algorithm is developed to solve the problem with emerging restraints, which is raised from the two-dimensional rectangular packing problem with some small rectangles that need to be packed into a fixed rectangular object. RLPA is designed from the BL algorithm and lowest horizontal line algorithm. GA and PSO are also modified to satisfy the constraint conditions. Best GA or PSO parameters are obtained by conducting experiments on some typical instances. The results are also compared, which validate the quality of the solutions and show the effectiveness of the modified algorithm.

Keywords:

• packing
• genetic algorithm
• rectangular layer problem
• particle swarm optimization

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant No. 70971093), Program for New Century Excellent Talents in University (NCET-09-0594), Humanities and Social Sciences Planning Foundation of the Chinese Education Commission (09YJA630111) and Tianjin Foundation for Philosophy and Social Sciences (YJGLWT11-17). We wish to acknowledge the very valuable contribution of a referee and editor to the improvement of the paper.