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

摘要： 提出一种启发式递归与遗传算法相结合的混合启发式算法求解矩形件优化排样问题。首先给出一种启发式递归算法，利用该算法逐个从待排矩形件中生成局部利用率高的条料，直到所有待排矩形件均生成条料；利用遗传算法全局搜索能力强的特点，对这些条料序进行搜索重组，使其所用的板材数最少；最后再次利用遗传算法，对条料生成之前的矩形件种类序进行全局最优搜索，使总的板材利用率达到了最大。对两个典型实际算例进行计算，并与相关文献比较，结果表明了该算法的有效性。

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