隗平平，刘 斌

(华侨大学机电与自动化学院，福建 厦门 361021)

0 引言

排样优化普遍存在于钣金、钢结构、航空、船舶、服装、皮革和纸制品以及玻璃加工等行业生产过程中，是制造业自动化中从设计到板料切割过程中的一个关键环节。排样优化是指在给定规格的原材料上，互不重叠地尽可能多地排放各种形状的待排零件，使原材料的利用率最高。因此，实现排样优化将最大限度地节约材料，提高工业生产效率，具有重要的现实意义。

在数学计算复杂性理论上，排样优化问题属于NP完全问题。对于这类问题，以目前已成熟的计算理论和算法，或者根本无法求解，或者求解的计算量是爆炸性的。

矩形件排样优化是排样优化问题中较为基础的一类问题，近几十年来，国内外众多学者都是以矩形件排样优化问题为基础，深入研究各种不规则零件的排样问题。到目前已经提出多种切实可行的用于排样优化的近似算法［1-7］。Baker等人在1980年最早提出了最下最左(bottom-left，BL)算法［1-2］，之后的一些学者在 BL 算法的基础上进行了改进，提出了基于BL的填充(bottomleft filling，BLF)算法［3］、下台阶算法［4］及最低水平线法［5］等排样算法。随着智能优化算法的日益成熟及其在TSP问题、空间分配等组合优化问题上的成功应用，遗传算法(GA)［2-5］、模拟退火算法(SA)［6］、粒子群算法(PSO)［7］等优化算法与以上排样算法相结合，广泛应用于矩形件排样问题的求解，并取得了很好的效果。

文献［2］研究了矩形件正交排样的遗传算法求解，其基本思想是将个体的编码视作一个排列，通过BL(Bottom Left)算法将编码转化为相应的排样图。……