黎凤洁，胡小春，陈 燕

(1.广西大学 计算机与电子信息学院 广西多媒体通信与网络技术重点实验室 广西 南宁 530004；2.广西财经学院 信息与统计学院 广西 南宁 530003)

0 引言

从计算复杂性上分析，优化下料问题属于具有较高复杂性的NP-Hard问题[1]，常见的优化算法主要有遗传算法、启发式算法、蚂蚁算法、模拟退火算法和混合算法等。在实际工程应用领域中，大规模、多尺寸的矩形件优化下料问题广泛出现于皮革套裁、金属板材切割、木材冲压等制造过程中。生成排样方式时考虑切割成本可以降低生产总成本[2]。综合考虑材料利用率高以及切割加工路径短两大优化目标对矩形件的生产加工具有重大的实际应用价值[3]。

目前，已有众多学者对大规模、多尺寸矩形件优化问题进行研究。文献[4]提出一种支持一刀切工艺约束的放宽式搜索算法。文献[5]采用蚁群算法解决大规模矩形件排样问题。文献[6]针对大规模矩形件正交排样问题，提出一种快速高效的启发式排放算法。文献[7]提出优化二叉树的启发式算法。文献[8]提出一种解决大规模二维剪切下料问题的有效方法。文献[9]采用遗传算法对大规模矩形零件优化套排。文献[10]针对大规模下料问题，提出基于零件相似性特征的分组优化方法。以上文献均只考虑提高材料利用率为优化目标。文献[11]提出大规模二维下料问题的禁忌搜索算法。文献[12]提出基于下料特征的大规模零件分组优化方法，考虑缓解排样算法在时间效率和材料利用率上的矛盾。……