刘诚，孙远升，花军，姚嘉明

(东北林业大学机电工程学院，哈尔滨 150040)

定制家具发展快速，数字化制造成了家具企业发展核心竞争力所在，如何利用数字化信息技术提供高效率、低成本的定制化产品已成为其面临的主要问题[1]，因此探讨人造板数字化智能下料具有重要意义。人造板下料问题为可旋转和满足“一刀切”的二维矩形板排样(two-dimensional rectangular bin packing of rotate and guillotine，简称2RBPRG)，即在工件可90°旋转，且排样满足“一刀切”条件下获得最优下料方案，该问题变量较多，包括每个工件的下料顺序、尺寸、位置及摆放方向，极具复杂性，属于多项式复杂种树度的非确定性(non-deterministic polynomial，NP)完全问题，目前仅能通过穷举法精确求解，当问题规模倍数扩大时计算机也无法计算。对此大量学者采取启发式算法近似求解，常见算法为二叉树排样[2-5]、分块填充排样[6-7]和二阶段排样[8-9]等。其中树形搜索与分块填充排样算法时间复杂度接近O(nlgn)，速度较快，但其采取先“一刀切”划分后排样策略可能增大余料碎化程度，降低排样利用率，对此，通过对排样空位进行整合[4]，以及通过选择最佳排样分解方式[5]，在一定程度上降低余料碎化，提高利用率。二阶段排样算法则简化排样问题，采用“条带排样”策略，如通过在原料板上逐次剪切下矩形带后在其上排样[9]，工件规格不整齐程度较大时，余料碎化较为严重。

智能算法也大量应用在矩形排样问题求解中，其中遗传算法应用最为广泛，如Aurelio、赵新芳等[10-11]均在无“一刀切”约束的矩形排样中使用遗传算法，获得较高排样利用率，但这类算法求解具有随机性，收敛速度及求解效果较为依赖遗传策略的选择。……