王静静 瞿少成 李科林

(华中师范大学物理科学与技术学院电子信息工程系 湖北 武汉 430079)

0 引 言

二维不规则排样问题是指在给定的原材料板材空间上，合理放置若干不规则零件，使得零件之间互不重叠且板材利用率最大。该问题在服装裁剪[1]、印刷包装[2]、钣金零件加工[3]、玻璃切割[4]等行业应用广泛，是实际工业生产加工中的关键环节。同时，该问题可以归为一类复杂的NP完全问题[5]，因此，长期以来受到国内外众多学者的关注。

二维不规则排样问题涉及运筹学、几何数学等众多学科，属于典型的组合优化问题。近年来，二维不规则排样问题常采用启发式算法或智能优化算法求解。文献[6]提出了一种多目标启发式进化算法求解考虑批量问题的二维矩形件排样问题，文献[7]提出了一种基于重心临界多边形的启发式排样算法。可以看出，启发式算法实现简单，能够快速给出求解方案，但难以取得全局最优解。因此，目前常采用模拟退火算法、遗传算法等智能优化算法解决排样优化问题。

遗传算法通过模拟自然进化过程搜索最优解，全局搜索能力优秀，适合大规模空间求解复杂问题[8]，将其应用到排样问题的求解上可以取得较好的排样效果。文献[9]结合遗传算法和最低水平线算法求解矩形件排样问题，但其寻优能力有待进一步改进。文献[10]利用基于排挤机制的小生境遗传算法求解排样顺序优化问题，但是算法效率有待提高。

针对以上问题，本文提出了一种基于并行交叉遗传算法的排样优化算法。……