关键词: 矩形件排样, 启发式递归算法, 遗传算法

Abstract: Based on heuristic recursive algorithm and genetic algorithm, this paper presents an algorithm of solving rectangular packing problem. A recursive algorithm of heuristic is proposed and all rectangle parts are converted to the strips with high utilization ratio. Then the optimal sequence of these strips is obtained by using genetic algorithm for minimizing the utilization of boards. Finally, in order to maximize the total utilization ratio of boards, the sequence of rectangular parts is optimized by using genetic algorithm again before they are generated to be the strips. Two typical instances are tested and the results are compared with related papers, it indicates the effectiveness and efficiency of this algorithm.

Key words: rectangle packing, recursive algorithm of heuristic, genetic algorithm