求解矩形件排样问题的启发式算法研究

《求解矩形件排样问题的启发式算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、广西师范大学硕士研究生学位论文求解矩形件排样问题的启发式算法研究学生：刘勇指导老师：崔耀东专业：计算机应用技术研究方向：计算机辅助设计与优化计算技术年级：2006级中文摘要排样问题是指在下料的过程中尽量减少材料的损失，使材料的利用率达到最高。它广泛存在于加工生产中，如板材切割、集装箱装载、服装和家具制造等。解决好这一问题，不仅可以节省原材料，降低企业生产成本，而且还可提高企业生产效率。矩形件排样问题是二维排样问题的一个分支。国内外许多学者对其进行过深入和广泛地研究，理论上证明其属于NP完全问题。当遇到较大规模时，势必会带来计算量的组合爆炸，因此很难在一定时间内取得最优解。针对上述问题，目前

2、解决的方法多为启发式方法。因此，研究矩形件排样问题既有实际应用价值，又有理论意义。启发式方法的特点是解决问题时，利用过去的经验规则，选择行之有效的方法。对于大规模问题的优化求解，其具有快速随机的全局搜索能力，大大减少了计算量，表现出比其它方法更优越的性能。除此以外，启发式方法简单易行、易于理解，具有良好的可扩展性，是解决排样问题的重要工具。本文研究的是二维矩形件排样问题，即在多张规格相同的矩形板材上排放一定需求量的毛坯，使得消耗板材的总面积达到最小。基于上述考虑，为了求解该问题，本文以“最小浪费优先策略”为基础，提出了一种分组搜索的启发式算法。与其它文献中报道的实例测试对比，板材利用率均有

3、所改善，验证了本文算法的有效性。本文所做的主要工作如下：第一，认真分析了中外学者提出的多种启发式算法，经过仔细比较，在总结其优缺点的基础上，对“最小浪费优先策略”进行了改造。“最小浪费优先策略”是从浪费区域的角度考虑，即毛坯排入后是否产生浪费区域以及产生浪费区域的大小。本文在其基础上提出了两种改造策略，第一，增加了一个限制条件，即毛坯排入后如果产生的浪费区域大于某值，则取消其排入。修改后的策略避免了一些不良方案的出现。第二，是毛坯排入的方向。早期的策略使用“最左原则”排入毛坯，取得了很好的效果。本文在其基础上进行改造，增加了一个“最右原则”。改造后可能会增加毛坯摆放的多样性，对提高板材的利

4、用率或许起到帮助。第二，考虑优化计算时间过长，以及排样方案不均衡等问题，本文提出了一种分组策略，即把所有的毛坯按面积大小均分三组，每次生成当前方式前，都从三组中各选择适当的块数，用于生成当前方式。在分组的过程中，有一些参数可以依据实际情况进行调整。例如，为了确定适当的块数，从一组中挑选出的毛坯面积和应该定为何值，本文规定其最大为1倍的板材面积，最小为0.3倍的板材面积。经过分组操作后，选择了一个毛坯集合的I广西师范大学硕士研究生学位论文子集，从而缩短生成当前方式所需时间。第三，将改造的最小浪费优先和分组策略相结合，提出了一种启发式算法——分组搜索算法。算法中如何产生排样序列是其关键步骤。在

5、现有的启发式算法中，有些学者应用遗传学的原理来生成排样序列，已经取得了较好的效果。本文引用随机局部搜索，利用随机交换两个毛坯的相对顺序，来生成新的排样序列。在随机操作中，需要使用一些技巧，当随机产生两个小矩形件的位置时，如果产生的位置相同，或者两个位置上小矩形件是同种，则把其中一个位置逐渐递加，直到位置上的两个小矩形件是不同种类为止，这样尽量增加序列的多样性，避免重复序列的生成。经过整体重复计算后，通过比较结果，保存较好的解，得到最终排样方案。分组搜索算法是一个组合算法，文中给出了其详细的伪码描述。第四，通过对矩形件优化排样系统框架的分析，分别实现了其四个主要模块功能。包括数据输入模块、优

6、化排样模块、排样结果显示模块、系统帮助模块。其中算法模块是整个框架的核心部分。本文选取了三组文献中的测试实例，其均与本文研究问题的排样规则相似，因此本文的算法与其测试结果具有可比性。经过测试后，并将实验结果与其进行了比较和分析，板材利用率均有所提升，验证了本文算法的有效性。第五，对己完成的工作进行了总结，提出了需要进一步改进之处。关键词：启发式算法，排样，矩形件，最优解II广西师范大学硕士研究生学位论文ResearchonheuristicalgorithmsfortherectanglepackingproblemsStudent:LiuYongTutor:CuiYaodongMajor

7、:ComputerApplicationandTechniqueResearchArea:OptimizationandComputationTechnology;ComputeraddeddesignGrade:2006AbstractThePackingproblemistoresearchhowtoreducethelossofmaterialasmuchaspossible,andmaximizetheusage