一维下料问题的一种启发式算法及其应用

一维下料问题是把长条形的原材料加工成若干不同长度坯料的问题。一维下料问题在工程技术和工业生产中有着重要和广泛的应用。一维下料问题求解方法的研究无论在理论上还是在实际应用上都具有重要的意义。一维下料问题是组合优化中一个经典问题,从计算复杂性上看属于NP-Hard问题。因此,只有小规模一维下料问题可以找到最优解,根据一维下料问题的类型可以用整数规划方法、动态规划方法和分支定界法求解。对大规模一维下料问题一般用启发式方法找到近似最优解。本文设计一种启发式算法解决马鞍山钢铁股份有限公司车轮公司实际一维下料问题。 本文首先概述一维下料问题,然后综述一维下料问题国内外研究现状,接着介绍几种典型一维下料算法,分析他们在应用中存在的问题,根据马鞍山钢铁股份有限公司车轮公司实际下料情况,建立一维优化下料模型,设计启发式算法并用Visum C++实现算法。用该企业连续四周下料数据模拟计算,其结果表明:优化算法计算钢锭的利用率比经验算法计算钢锭的利用率平均提高了近7个百分点,且其配尺表个数比经验算法少。