钢板二维切割问题的分析-工业工程专业论文.docxVIP

东北大学硕士学位论文 东北大学硕士学位论文 摘要 摘要 本文研究的目的在于改进在钢铁企业中二维切割问题的优化模型。所做的 主要工作在于加强模型所能表达的功能和针对优化问题的算法求解的改进。我 们所研究的二维切割问题是十分有意义的，由于当产品的数量比较大的时候， 在进行切割规划时即使微小的改进也能导致节省大量的原材料和能源。 解决此类切割问题，尽管有许多的方法可以使用，但在本文中只研究了一 种针对大规模切割问题非常有效的求解算法——列生成。此算法事先产生初始 切割模式并将它作为变量插入到模型中。此算法能考虑到每种可行切割模式， 其最主要的贡献在于当切割模式的数量巨大时，能给出切割模式的长度的界限。 而在其它所提出的算法中，控制切割模式的长度是非常困难的。 通过参考文献给出基准结果。使用列生成算法解决我们所提出的模型，通 过与文献原始问题比较发现在库存板的利用率上有很大提高。另外，在模型中 提出了诸如Guillotine切割和产品优先权等特性。然而，在模型中增加这些特 性会增加收敛时间。 在本文中我们只是利用Wang所提出的启发式得到列生成的初始解，应用 动态规划求解二维切割问题的子问题——背包问题。实质上，对于其它解决此 类问题的数学启发式做进一步研究是非常有意义的。分类优化理论用于优化切 割模式长度被证明是有价值的。其减少优化时间的贡献主要在于剔除一些不必 要的松弛变量和模型中的不必要约束。因此它能计算出尽可能紧的界，这点非 常重要。然而，太紧的界可能剔除解空间中有用的部分。如果那样，最好也只 能得到次优解。 在PentiumlII系列主频1000的计算机上，使用c++语言实现了上述全部算 法，并进行实验仿真。实验结果表明列生成算法能够有效地求解二维切割问题。 关键词：=维切割问题，背包问题，列生成，动态规划，分支定界 II 东北大学硕士学位论文 东北大学硕士学位论文 摘要 Abstract The purpose of this research is to improve an optimization model of a two·dimensional cutting stock problem in the steel industry．The improvements address the functionality ofthe model and solution times ofthe optimization problem． The research problem is important，since even small improvements in the cutting layouts result in large savings of raw material and energy when the amount of produced material is huge． Although numerous solution methods for solving cutting stock problems available，only specific algorithmic method is valid for the particular problem being studied in this research．In this method，cutting patterns are generated beforehand and inserted in the formulation as parameters．This approach makes it possible to take into account each feasible cutting pattern．Most important attributes are bounds on the cutting pattern lengths when the number of cutting patterns is large．In some other representations of cutting patterns，controlling cutting pattern lengths is much more dimcult． The ben