张 娜 赵 罘 龚堰珏 刘玲玲

(北京工商大学材料与机械工程学院 北京 100048)

0 引 言

矩形排样问题属于二维排样，是NP完全问题，计算复杂度高。矩形排样在现代工业的原材料切割中有着大量的应用，如玻璃切割、钢板下料、纸张剪裁等，即使是排样高度的微小降低，也能极大地节约原材料。

鉴于矩形排样问题的复杂性和重要性，研究者们做了长期的研究，但尚无统一有效的求解算法。目前求解矩形排样问题主要由两部分相互配合实现：(1) 利用智能优化算法计算矩形排入顺序，如遗传算法、模拟退火算法、蚁群算法等；(2) 利用启发式算法计算矩形排放位置，如IBL法、BLF法、最低水平线法[1]、剩余矩形法[2]等。Hopper等[3]分别用遗传算法和模拟退火算法配合BLF法，计算出较优解；Liu等[4]采用分阶段遗传算子的遗传算法配合改进的最低水平线法，能快速计算出解；周家智等[5]将遗传算法和模拟退火算法组合并配合修改的最低水平线算法，取得较好的排样结果；蒋兴波等[6]提出的基于环形交叉和变异算子并引入模拟退火算法的自适应模拟退火遗传算法配合IBL法,也能在较短时间得到解。但上述几种算法未能同时平衡求解时间和排样高度，存在排样高度小的，却求解时间长；求解时间短的，却排样高度大的情况。

本文在最低水平线法基础上作改进，提出动态最低水平线法，能弥补最低水平线法易产生材料空余的缺陷，减少空余产生。采用具有较好全局搜索性的蚁群算法[7]计算矩形排入顺序，并作适当改变使其更好适应排样问题。……