贪心策略在电站锅炉管材套料优化的应用研究

曲默丰， 辛 炜， 宋华强

(上海锅炉厂有限公司， 上海 200245)

一维套料问题普遍存在于电站锅炉受热面制造过程中，即将一种或多种规格的一维原材料管材通过切割的方式重新组成一种或多种规格的目标材料管材[1]。一维套料问题属于NP-hard问题，其目标一般为原材料的利用率最大化，目前可以通过精确或启发式算法进行求解[2]。当原材料种类单一且数量较少时，采用线性规划法、分支定界法等[3]可以得到准确解；而当原材料种类和数量较多时，切割的组合数量将会呈现爆炸式增加，使得求解变得非常困难，因此通常采用启发式算法获得近似最优解。近年来，启发式算法由于具有效率高、精度高的优点受到国内外学者的广泛关注。贾志欣等[4]运用遗传算法优化下料问题，其主体思路为视目标材料的一种顺序为一个方案，将不同种方案进行组合优化运算(简称算法1)；王小东等[5]利用多级序列线性优化的方法求解下料问题，属于改进的启发式算法(简称算法2)；祝胜兰[6]对单一规格与多规格下料问题分别进行研究，最终采用先汇总切割然后按照约束条件搜索最优途径的方法(简称算法3)。

相比于精确求解，上述算法虽然在运算速度与原材料利用率等方面有了较大提升，但是仍然存在一定的改善空间。目前，大多数算法针对多规格一维套料问题的求解一般仅考虑原材料长度大于目标材料的情况，而未对部分原材料长度小于目标材料的情况进行讨论。在电站锅炉水冷壁、过热器及再热器的制造过程中，上述的第二种套料情况十分普遍，针对同时适用于两种套料方式且高效省料的算法展开研究具有十分重要的科研价值和工程意义。为此，笔者综合考虑贪心策略与实际工程经验，提出了适用于电站锅

炉管材套料的新求解方法(简称算法4)。

1 数学模型

目标函数为：

(1)

约束条件为：

(2)

式中：F为消耗原材料总长度的最小值；Xin为与Dn相对应的第i种排列组合数量；Pim为与dm相对应的第i种排列组合数量；Yi为第i种排列组合重复次数。

2 求解方法

2.1 贪心策略

贪心策略属于启发式算法范畴，在一维多规格管材套料问题中，贪心策略首先将消耗原材料总长度最小这一全局目标拆解为多个子目标，然后按照某种顺序和策略依次对各个子目标进行优化，从而获得局部最优解，最后将局部最优解串联起来并认为得到全局最优解。贪心策略虽然不能准确地计算得出全局最优解，但是其最终结果仍然是全局最优解的较佳近似值之一[7]。

2.2 算法流程

采用贪心策略求解多规格一维套料问题分为以下步骤：

(1)将原材料管材[Ln,Dn]和目标管材[lm,dm]分别按照管材长度从大到小的顺序排列。

图1 原材料管材切割

(3)设置偏差最大值界限(可参考原材料管材总长与目标管材总长之间的偏差，根据实际情况适当调整)，并取最小偏差所对应的组合作为局部最优解。

(4)汇总所有局部最优解并得到最终计算结果。

算法流程见图2。

图2 算法流程

3 计算结果及分析

该算例均在主频为1.6 GHz、内存为8 GB的计算机上运行。

3.1 与相关公开套料数据的对比

采用文献[5]中的经典一维管材切割套料算例进行计算并与其他学者采用不同算法计算得到的结果进行对比。该算例可简述为：原材料管材长度为3 m，数量若干，目标管材长度与数量见表1。

表1 目标管材信息

算法1～4的计算结果[4-6]分别见表2～5。对比表2～5可以看出：4种算法均消耗了8根原材料管材，但是算法4计算得到的前7根原材料管材的余料长度均为0，利用率最高，第8根原材料管材的余料长度为2.4 m，长于其他3种算法结果，更有利于后续套料使用，结合算法4运行时间较短，仅为0.25 s，可知算法4较佳。

表2 算法1计算结果

表3 算法2计算结果

表4 算法3计算结果

表5 算法4计算结果

3.2 与S公司实际套料数据对比

S公司是全国领先的电站锅炉生产制造公司，在锅炉制造领域拥有雄厚的技术实力和丰富的生产经验。笔者运用算法4对该公司某容量П形锅炉后烟井包覆管套料进行计算，并与该公司实际套料数据进行对比，原材料管材与目标管材信息分别见表6与表7。

表6 S公司原材料管材信息

表7 S公司目标管材信息

S公司实际套料结果与算法4计算结果分别见表8与表9。

表8 S公司实际套料结果

表8(续)

表9 算法4计算结果

表9(续)

由表8与表9对比可以看出：采用算法4套料产生的单根管余料普遍较少，并且第32种切割方式得到的管材余料较长(长度为3.15 m)，方便后续套料再次使用。此外，假设长度大于1 m的原材料管材可作为后续套料使用，则S公司实际结果中满足该条件的有6.723 m原材料管材1根，算法4计算结果中满足该条件的有3.150 m和6.000 m原材料管材各1根，其中6.000 m原材料管材为未进行任何切割操作的整根管，综合考虑余料长度与余料属性，算法4在提高原材料管材利用率方面略胜一筹。结合算法4计算时间仅为1.36 s可知，其在工程实际的多规格一维管材套料计算中表现良好。

4 结语

笔者采用贪心策略与实际工程经验相结合的方式，对电站锅炉管材套料问题提出了一种新的求解方法，该算法能够明显提高原材料的利用率且运算速度较快，具有原理简单、结构简洁、易于实现等特点。综合考虑求解质量、速度以及编程的难易程度，该算法是求解工程应用问题的实用方法。