基于排样矩形的直角边零件下料算法①

郭百海,隋 毅

(青岛大学 计算机科学技术学院,青岛 266071)

直角边零件的轮廓由直角边组成,并且任意相邻两边之间的夹角都是直角,对这种零件的排样布局称为直角边零件下料问题.直角边零件在许多领域中都有广泛的应用,如普通机械、专业设备等制造行业的型材、金属切割、木材加工、建筑行业的平板玻璃切割等,但直角边零件加工普遍存在余料剩余较多,加工效率较低,原材料浪费等问题[1,2].因此,优化直角边零件排样布局,使直角边零件下料后产生的废料最少,即板材的利用率最高,对降低企业生产成本具有重要意义和实用价值.

目前直角边零件下料布局优化问题已有大量相关研究,Gilmore 和Gomory[3]利用动态规划算法求解矩形零件的布局被认为是解决二维切割问题的基本方法；张燕玲等[2]基于改进的Basely 模型[4]设计实现了一种可用于直角边下料问题的整数规划模型；戚得众等[5]提出了一种基于工艺与形状特征的下料零件分组下料优化模型；Fabio Furini 等[6]通过建立混合整数线性规划模型表示二维切削问题中一般切刀约束的问题；葛志辉等[7]提出一种基于工艺约束策略的二维不规则排样算法；张旭等[8]给出了一种基于最大移动距离的启发式算法,改善了排样结果.然而,由于直角边零件下料布局优化是NP-Hard (Non-deterministic Polynomial Hard)[9]问题,不能在多项式时间内解决,多数研究获得的结果只能趋近于最优解而很难达到最优解；即便获得最优解,由于现有研究普遍将材……