曲默丰， 辛 炜， 宋华强

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

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

相比于精确求解，上述算法虽然在运算速度与原材料利用率等方面有了较大提升，但是仍然存在一定的改善空间。目前，大多数算法针对多规格一维套料问题的求解一般仅考虑原材料长度大于目标材料的情况，而未对部分原材料长度小于目标材料的情况进行讨论。……