满足“一刀切”约束的卷型材矩形件排样方法研究

发布时间：2017-10-07 23:22

  本文关键词：满足“一刀切”约束的卷型材矩形件排样方法研究

  更多相关文章： 卷型材排样 一刀切 启发式算法 交互式排样 切割线

【摘要】：卷型材矩形件排样问题是一类经典的NP完全问题,主要研究如何将矩形工件排放在长度可变的矩形原材料上,以获得高的材料利用率。受某些制造过程和工艺的影响,卷型材矩形件排样方案必须满足“一刀切”约束——“从矩形板材的一端,沿直线方向切割到另一端,将其分割成两个独立的矩形件”；受生产过程的约束,某些工件之间有配对要求,需要尽可能排放在一起。这些工艺约束和生产约束给卷型材矩形件排样问题的求解带来新的要求。卷型材矩形件排样问题在制造业中广泛存在,诸如造纸、薄钢板的加工或切割。对这一问题的有效求解方法直接影响企业的原料成本。 本文重点研究工件可旋转的“一刀切”卷型材矩形件排样问题。提出了一种基于组块策略的启发式排样搜索算法GBHSA(Group-Based Heuristic Search Approach)。算法将二维矩形件排样问题分解成工件定位问题和工件组合问题,将多个工件的组合工件组当成一个整体作为排样的基本单元；进而,提出一种构造性的排样递归搜索方法：利用“左下优先”原则解决工件的定位问题,将排样过程转化为“排放→切割”基本步骤的组合,并以利用率阈值作为回溯条件进行回溯。算法同时在切割方案的选择、排放工件的选择上运用了一系列的启发式规则。组块策略、启发式规则的使用有效缩减了搜索的解空间,提升了算法的速度,构造性的递归搜索在一定程度上保证了算法的全局寻优能力。通过使用国际上通用的一批标准测试案例进行测试,算法具有一定的先进性。 同时,论文还研究了满足“一刀切”约束的矩形件交互式排样系统,开发了具有矩形件增、删、旋转和移动功能的交互式排样组件；定义了原材料有效利用率这一核心概念,提出了一种以切割线总路径为优化目标的切割线生成算法；以自动生成排样方案的切割线,并保证切割方案的“一刀切”约束。 最后,论文依据上述研究内容,开发了二维排样软件。
【关键词】：卷型材排样 一刀切 启发式算法 交互式排样 切割线
【学位授予单位】：广东工业大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TH162
【目录】：

• 摘要4-5
• ABSTRACT5-12
• 第一章 绪论12-22
• 1.1 研究背景12
• 1.2 排样问题的分类12-15
• 1.2.1 一维排样问题12-13
• 1.2.2 二维排样问题13-14
• 1.2.3 三维排样问题14-15
• 1.3 二维排样问题的国内外研究现状15-20
• 1.3.1 排样方法16-17
• 1.3.2 优化算法17-19
• 1.3.3 一刀切矩形件排样算法19-20
• 1.4 研究内容与意义20-22
• 第二章 2DSPP-RG问题的模型及求解思路22-28
• 2.1 引言22
• 2.2 问题模型22-25
• 2.2.1 二维矩形件排样问题的数学模型23-24
• 2.2.2 二维矩形件排样问题的几何模型24-25
• 2.3 求解思路25-26
• 2.4 小结26-28
• 第三章 基于组块策略的启发式排样算法28-51
• 3.1 引言28
• 3.2 算法设计思路28-29
• 3.3 启发式算法设计29-37
• 3.3.1 预处理形成切片组30-31
• 3.3.2 切片组Group相对原片的适应度值31-32
• 3.3.3 定位递归结构32-33
• 3.3.4 水平垂直切割33-34
• 3.3.5 解空间限制34-35
• 3.3.6 Group快速推荐策略35-36
• 3.3.7 算法流程36-37
• 3.4 算法测试与对比37-50
• 3.4.1 测试案例及效果38-45
• 3.4.2 与其他算法对比45-50
• 3.5 小结50-51
• 第四章 交互式排样方法51-57
• 4.1 引言51
• 4.2 交互式排样功能的必要性51-52
• 4.3 交互式排样方法52-54
• 4.3.1 矩形件碰撞检测算法52-53
• 4.3.2 交互式排样功能53-54
• 4.4 交互式排样案例演示和说明54-56
• 4.5 小结56-57
• 第五章 切割线生成算法57-66
• 5.1 引言57
• 5.2 切割线描述57-59
• 5.3 切割线生成算法59-65
• 5.3.1 数据预处理61
• 5.3.2 切割线生成算法61-65
• 5.4 切割线切割顺序生成方法65
• 5.5 小结65-66
• 第六章 系统架构与研发66-73
• 6.1 引言66
• 6.2 开发工具选择66-67
• 6.3 系统功能模块67-69
• 6.4 系统简介69-72
• 6.5 小结72-73
• 结论73-75
• 参考文献75-80
• 攻读学位期间发表的论文80-82
• 致谢82

【引证文献】

中国期刊全文数据库 前1条

1 张帆;刘强;张浩;王磊;;面向多规格板材的矩形工件排样优化方法[J];计算机集成制造系统;2015年11期

中国硕士学位论文全文数据库 前1条

1 张帆;面向多规格板材件的矩形工件排样方法的研究[D];广东工业大学;2015年

，

本文编号：990675