一维下料问题的快速计算方法研究

李秀丽,董春江

(1.青中景建设(青岛)有限公司,山东 青岛 266033;2.青岛新华友建工集团股份有限公司,山东 青岛 266101)

一维下料问题在机械、水利、电力、土木工程、航空航天等工程技术和工业生产领域有着重要和广泛的应用[1-2]。例如,机械工程中铝合金和棒材的下料、建筑行业中钢筋和型材的下料、家具制造业中板材的下料等。一种好的下料方案可以减少原材料的损耗,进而降低企业的生产成本。

近年来,随着计算机技术的发展和优化算法的进步,一维下料问题的研究也在不断深入[3-5]。针对不同工程问题,研究人员采用不同的优化算法来解决下料问题,目前已取得明显效果[6-9]。目前,许多学者研究方向主要针对零件种类和数量较少的问题。当切割规格较多或者切割数量较大时,切割方式数量呈爆炸增长,问题的复杂性剧增,计算机的计算量是巨大的,不能在极短的时间内找到最优解。因此,如何采用近似算法快速求解满意解或者近似最优解成为一维下料问题研究的一个重要方向[10]。

本文从实际工程的角度出发提出一种针对多规格切割问题的计算方法,利用该方法能够快速求解出一维下料问题的近似最优解,从而实现解决实际工程中一维下料问题的目标。

1 数学模型

单一规格原材料的一维下料问题具体数学描述如下:假设有足够多的长度为L的某种原材料,现需要切割n种数量不等的零件,长度为li的零件数量为bi,其中,i=1,2,…,n。求解如何下料使得所使用的原材料的数量最少。其中,L>max{li},i=1,2,…,n。Xj为第j种切割方式重复的次数,Aij为第j种切割模式切割出来第i种零件的数量。

一维下料问题的数学模型总结归纳起来可以分为两类:一类是以原材料消耗的总根数最少为目标函数,另一类是以余料总长度最短为目标函数。目前,各种数学模型大多是在这两类模型的基础上建立的。

数学模型1为以原材料消耗的根数最少为目标,具体如下:

(1)

(2)

(3)

数学模型2以余料最少为目标,具体如下:

(4)

(5)

(6)

式中,Xj≥0且Xj∈n,j=1,2,…,M;M为切割模式的种类;n为所需零件的数量。

对于所需零件的数量n较小的问题,数学模型1和数学模型2的直接求解还是比较简单的。但当所需零件的数量n较大时,也就是说切割模式的种类十分巨大时,要直接求解上述问题是十分困难的。本文通过对上述数学模型1进行改进,从而求解出一维下料问题的近似最优解。

2 计算方法

2.1 算法

从工程项目的实际考虑,当所需零件的数量n较大时,单根原材料的切割种类不能太多。如果单根原材料的切割种类不限制,一方面会导致切割过程的操作过于复杂,另一方面会极大地增加原材料加工的切割方式,这样都会极大地增加实际的加工成本。为限制单根原材料的切割种类,设置参数切割模式限值为NC,用于控制单根原材料的切割种类。切割材料时单根材料的余料不能过多,为限制单根原材料的余料,设置参数余料限值L0,用于控制单根原材料的余料值。

定义一个参数δj(i),使其满足如下条件:

(7)

对数学模型1进行改进,增加合理的约束条件,具体数学模型公式如下:

(8)

(9)

(10)

(11)

(12)

式中,L0是单根原材料的余料限值;NC是单根原材料切割模式限值。

具体的算法流程图如图1所示。

图1 算法的流程图

2.2 余料限值L0和切割模式限值NC

定义参数λi为全部切割模式中切割出来的第i种零件出现的次数。

定义函数f如下:

(13)

Nl=max{L-[L/l]·li}

(14)

式中,[L/l]是L/li的整数部分。

余料限值L0是优化算法中一个重要的参数,如果L0的取值过小,会导致筛选出的切割模式不能包含全部的切割零件;如果L0的取值过大,会导致筛选出的切割模式过多,会极大地增加计算量。在进行L0的取值时可以参考Nl的数值进行选取。

定义下料方案的原材料利用率为η,即

(15)

式中,M0为求解的原材料数量。

3 算例分析

某一实际工程项目需要切割一批钢管,所需钢管的尺寸和数量见表1,现库存有充足的长度为6 m的原材料,要求给出精确的下料方案(不考虑切开损失)。

表1 零件的尺寸和数量

当分别选取NC为1、2、3时,选取不同的参数L0获得15种不同的切割方案,切割方案见表2。从表2中可知,当L0的取值较小时,本文的方法会出现无解的情况,主要的原因是获得切割模式未包含全部零件。从表2中不难发现,随着L0取值的增加,切割模式的数量会增加,当L0增加到一定数值时,原材料利用率η不再增加。随着NC取值的增加,原材料利用率η不会增加,当NC选取1、2、3时,原材料利用率η分别为69.4%、94.5%和97.9%。

表2 计算的切割方案

通过上述分析,当NC为1和2时,原材料利用率η还没有达到最优,在实际使用本文方法切割下料时,建议NC的取值为3。当L0的取值较小时,计算会出现无解的情况,当L0的取值较大时,计算量会增加。因此,建议L0的取值策略如下:初始选取L0为100 mm,若经计算后f的数值为0,则依次选取L0为200 mm、300 mm……直到f的数值为1。

当NC选取3时,选取的L0不同会得到不同的切割方案,比较表2中的5种方案,当L0选取200 mm时得到的切割方案的模式数量最少为18种,是5种方案中切割模式种类数量最少的,可以减少切割的工艺。因此,在实际工程中可以选取方案13作为工程中的最终切割方案,最终的下料切割方案见表3。

表3 最终的切割方案

4 结语

本文结合实际工程通过改进原有的一维下料问题的数学模型,在满足零件需求量的情况下,使原材料的使用量最少。

1)本文采用方法结构简明,易于编程实现,对单一原材料问题均能在短时间内得到精度较高的近似最优解。本文的方法已经过实际工程的验证,可以用于一维下料问题。

2)实际应用效果表明,本文方法能够明显提高材料的利用率,是企业降低成本的有效途径,能够很好地指导现场生产,在土木、机械、电力、航空航天等领域具备广阔的市场应用前景和潜在经济效益。