文档介绍：广西师范大学
硕士学位论文
解一维下料问题的一种改进的启发式算法
姓名:刘睿
申请学位级别:硕士
专业:计算机应用技术
指导教师:崔耀东
20090401
广西师范大学硕士研究生学位论文
解一维下料问题的一种改进的启发式算法
学生:刘睿指导老师:崔耀东
专业:计算机应用技术研究方向:优化计算技术与 CAD 年级:2006
中文摘要
在国民经济生产中,存在着大量的切割下料问题。一维下料问题是指原材料和所需坯
料维数都为一维时,在供应条件已知的情况下考虑如何优化切割下料,使得坯料需求满足,
并且最大限度的提高材料利用率、减少切割损失。一维下料问题在工程技术和工业生产中
有着重要和广泛的应用,讨论该问题是研究二维、三维等多维下料问题的基础。伴随着信
息化产业和计算机技术的快速发展,先进的计算机辅助设计技术也越来越多地应用于下料
过程中。因此,对该问题求解方法的研究在实际应用中和理论上都具有重要的意义。
本篇论文讨论的是多种长度线材上的下料问题,在对启发式算法进行分析和研究的基
础上,使用一种改进的顺序启发式算法进行一维下料问题的求解。根据实际生产环境的需
要,通过一系列的改进策略,对算法进行进一步优化,在保证较高材料利用率的同时考虑
减少排样方式、增加最后一根材料上余料长度、优先使用短材料等多个优化目标。通过大
量的实例测试,证实了本文算法的有效性。本文的主要工作和创新点如下:
首先,针对所研究的问题,给出求解当前最优排样方式的数学模型,在该模型的基础
上介绍算法的基本思想以及实现流程。本文使用的是一种基于顺序价值修正的启发式算
法。顺序价值修正是指每生成一个新的排样方式前,都利用以前的信息,修正各种毛坯的
价值,并多次重复该过程,最终使其价值系数达到较为合理的状态。通过适当调整毛坯价
值,将他们的相对受欢迎程度体现出来,对不好排的毛坯赋予较高的优先权,使之优先被
选择。这样做有助于生成较好的排样方式,并利用前面方式的信息,指导后面的排样过程,
从而有效的提高原材料的利用率。
基于当前最优排样方式的计算模型,求解背包问题,生成总价值最大的排样方式。考
虑增加有效排样方式的数量,加大选择空间。因此,在已经获得的排样方式中,选择影响
其重复次数的毛坯进行替换,得到更多效果较好的排样方式。进行判断,依次选取合适的
排样方式组成当前排样方案。多次迭代执行该过程,保存较好的排样结果。
进一步完善和改进本文算法。通过采用多种启发式策略和参数优化的方法,提高材料
利用率、减少排样方式数以简化生产工艺。对待排毛坯进行预分组,每次使用候选组中的
坯料生成当前排样方式,坯料子集的选取可有效的减少排样方式的数目;设计排样方式的
选择标准,优先使用较短的原材料,以减少库存容量;记录每个排样方案中最后一个排样
方式的余料长度,算法反复执行多次,较好的一部分排样方案进行保存,优先选用余料较
长的方案来实现,达到方便余料回收并再次利用、降低生产成本的目的。考虑到问题的多
样性,对算法涉及的参数采用循环方式控制计算。对应每一组参数值,算法迭代执行多次,
生成大量的排样方案。通过多次计算,选取最好的结果。
I
广西师范大学硕士研究生学位论文
最后,规划和设计下料系统的基本功能模块,开发出基于改进的顺序启发式算法的一
维优化下料系统。通过大量的实验测试,并将实验结果与多个较新的优化算法的实验结果
进行比较和分析,结果表明,本文算法的材料利用率较高,并实现了排样方式数目少、优
先使用短材料、最后一根材料上余料长度长等多个优化目标,是一种有效的求解一维下料
问题的启发式算法。
关键词:切割下料;一维下料;启发式算法;多目标优化
II
广西师范大学硕士研究生学位论文
An improved heuristic algorithm for one-dimensional
cutting stock problem
Student: Liu Rui Tutor: Cui Yaodong Major: Computer Application and Technique Research
Area: Optimization putation Technology; Computer Aided Design
Grade: 2006
Abstract
In national economical production, there have a lot of cutting stock problems. The
One-Dimensional Cutting Stock Problem (1D