学位论文 > 优秀研究生学位论文题录展示

圆形件下料启发式算法

作　者: 侯桂玉
导　师: 崔耀东
学　校: 广西师范大学
专　业: 计算机软件与理论
关键词: 切割下料二维下料圆形件下料启发式算法有约束排样算法
分类号: TP391.7
类　型: 硕士论文
年　份: 2010年
下　载: 88次
引　用: 0次
阅　读: 论文下载

内容摘要

切割下料问题广泛存在于国民经济生产的各大行业中,例如机械制造业、服装加工业、家具制造业、木材加工业以及皮革制品制造业等。随着信息化产业和计算机技术的快速发展,先进的计算机辅助设计技术被越来越多的应用于优化下料过程中,成为提高下料效率和利用率的关键。二维下料问题是指原材料和毛坯维数都为二维时,考虑如何优化切割下料,使得满足毛坯需求,并且最大限度的提高材料利用率、减少切割损失。二维下料问题是日常生产中广泛存在的一种下料问题。目前,国内外学者对二维下料问题的研究给予了足够的重视,特别是针对矩形件和二维不规则件的排样问题提出了许多行之有效的算法,比如动态规划算法,分支定界算法,禁忌搜索、模拟退火算法,遗传算法,神经网络算法等等。然而,对另一种在实际生产中广泛存在的二维下料问题——圆形件下料问题研究相对较少,特别是对圆形件下料的有约束排样算法更是有限。对于排样算法的研究有两个方向的分支:有约束排样算法和无约束排样算法。无约束排样算法是指已知要排入毛坯的尺寸和价值,实现其在单张板材上的排样,使得排入毛坯的总价值最大,这种排样算法通常与线性规划技术相结合,以求解下料问题。有约束排样算法用于确定毛坯在单张板材上的排样方式,使得在满足毛坯数量上限约束的条件下,单张板材上排入毛坯的总价值最大;它通常与顺序法结合,以求解下料问题。本文研究有约束排样算法及基于顺序法的排样方案生成算法,以求解圆形件剪冲下料排样问题,即以剪冲下料方式为工艺基础,确定一个排样方案,该排样方案满足如下条件:(1)排样方案由一个或多个排样方式组成;(2)排样方式必须是可行的;(3)精确满足各种毛坯的需求量;(4)排样方案要使所消耗的板材的总面积最小。所谓剪冲下料工艺就是把给定长度和宽度的板材首先用剪床把板材切割成水平或竖直条带,并且每根条带中包含的圆片具有相同的直径,再将每根条带送至冲床冲出圆片。在对启发式算法进行分析和研究的基础上,使用顺序价值修正法对圆形件下料问题进行求解。本文的主要工作如下:第一,针对研究的问题,给出求解圆形件在单张板材上的最优排样方式生成算法,并以此算法为基础,结合顺序启发式策略设计排样方案生成算法,使得在精确满足各圆形件需求量的前提下,最大限度的提高材料利用率。第二,进一步完善和改进本文算法。由于传统的顺序启发式策略具有一定的贪婪性质,因此使用此方法生成的排样方案容易造成排样方案的局部最优而不是整体最优,所以本文结合了基于顺序价值修正的启发式策略和参数优化的方法,提高材料的利用率。顺序价值修正是指初始化圆形件毛坯的价值为圆形件的面积,每生成一个新的排样方式前,都运用价值修正公式以修正前的毛坯价值为基础加以计算,修正各种毛坯的价值,并多次重复该过程,最终使其价值系数达到较为合理的状态。通过适当调整毛坯价值,将他们的相对受欢迎程度体现出来,对不好排的毛坯赋予较高的优先权,使之优先被选择。这样做有助于生成较好的排样方式,并利用前面方式的信息,指导后面的排样过程,从而有效的提高原材料的利用率。第三,规划和设计下料系统的基本功能模块,设计开发了基于顺序价值修正法的圆形件下料排样系统。并用已有的下料系统对本文算法进行有效性检验,通过对实验结果的比较和分析,结果表明,本文算法的材料利用率较高,是一种有效的求解圆形件下料问题的有约束排样算法。

全文目录

中文摘要  4-6
Abstract  6-10
第1章绪论  10-15
  1.1 问题的概述  10
  1.2 优化排样问题的分类  10-12
  1.3 二维下料问题当前应用中存在的问题  12
  1.4 圆形件下料问题的研究现状  12-13
  1.5 本文的主要工作  13-14
  1.6 章节组织  14-15
第2章圆形件下料问题  15-22
  2.1 圆形件下料问题的描述  15-16
  2.2 圆形件优化排样的理论  16-19
    2.2.1 动态规划理论  16
    2.2.2 背包算法  16-17
    2.2.3 线性规划  17-19
  2.3 圆形件排样问题的典型排样方式  19-22
第3章改进的顺序启发式算法  22-28
  3.1 相关概念  22-23
    3.1.1 有约束排样问题  22
    3.1.2 条带宽度和条带价值  22-23
    3.1.3 排样方式和排样方案  23
  3.2 算法原理  23-25
    3.2.1 启发式算法  23
    3.2.2 顺序启发式算法  23-24
    3.2.3 顺序价值修正策略  24-25
  3.3 算法实现  25-28
    3.3.1 条带生成算法GenStp  25-26
    3.3.2 排样方式生成算法Rec  26
    3.3.3 最优排样方式生成算法GBP  26-27
    3.3.4 排样方案生成算法GetPat  27-28
第4章圆形件下料系统的结构和实验结果  28-36
  4.1 圆形件下料系统的结构  28
  4.2 圆形件下料系统的实验结果  28-31
  4.3 实验结果分析  31-36
第5章总结与展望  36-37
参考文献  37-39
攻读硕士学位期间发表的论文  39-40
致谢  40-41

圆形件下料启发式算法

内容摘要

全文目录

相似论文