杨 畅，杨 林，沈竹楠

(沈阳工业大学 机械工程学院，辽宁 沈阳 110870)

0 引言

目前，下料问题的求解方法主要是各种近似法和智能计算方法。下料问题由于存在大量的局部最优解，且实际问题一般规模较大，多为线性规划问题[1-2]。本文分析比对循环首次适用算法NF(Next Fit)、最佳适应算法BF(Best Fit)、首次适合下降算法FFD(First Fit Decreasing)[3]等多种算法，最终确定采用多叉树遍历算法，设置剪枝条件进行全局搜索，以求得全局最优解。

1 问题描述

对多规格一维下料的问题描述如下：被切割原材料共有M种，其长度分别为Lq(q=1,2,…，M)，每种原材料数量以实际情况为准。待切割工件共有m种规格，其长度为lj，需求量为nj(j=1,2,…，m)。设计合理的优化下料方案，使所需要原材料的利用率最高，即废料最少[4]。在优化下料过程中，充分利用余料是提高原材料利用率的有效手段。尺寸过小的余料无法再利用，在余料总长度一定的情况下，下料方案中要尽量产生尺寸大的余料，以便余料再利用[5]。其数学模型可表示为：

(1)

其中：N为原材料的使用数量；L(i)为下料结果中第i根原材料的长度，aij为第i根原材料上第j件坯料的数量；ti为第i根原材料的余料；tmax为所有原材料上余料的最大值。本文讨论的下料方法暂不考虑切缝问题，按精确下料进行考虑。

多规格下料可看成是单规格下料基础上的扩大搜索，即树与森林的关系。当原材料的型号只有一种时，利用多叉树遍历算法可得到最优化的下料方式，即余料最小且末根被切割的原材料剩余最大。

2 算……

登录APP查看全文