二维非规则一刀切排样问题研究

论文摘要

二维一刀切排样问题,即给定若干个形状不规则的待排件和多个相同规格的矩形可排区域(二维箱子),在满足相互不重叠的情况下,把待排件放至可排区域内,并满足切割时的一刀切约束,使得所使用的箱子个数最小。二维一刀切排样问题主要应用在家具行业的非规则玻璃切割工业中,是典型的组合优化问题,也是NP完全问题,有着很高的计算复杂度,并具有深远的理论研究价值和实用价值。本文提出了二维非规则一刀切排样问题的启发式算法,该算法同时兼顾了排样的质量和速度,取得了良好的效果。主要内容如下:(1)针对文献中使用NFP进行定位时,存在计算复杂度高、计算量大,需要大量预处理的缺点,给出了新的启发式定位算法——移动装箱算法;(2)对一刀切切割顺序提出了多叉切割树的概念来减少计算量,以避免重复操作。并对可排件排样的先后顺序问题,提出了推广了的二维最大矩形算法。新算法利用优先队列对可排区域进行处理,同时给出了局部最优排样选择的启发式规则,利用更换切割顺序的方式巧妙实现了对部分区域的合并;(3)针对实际应用中非规则件可切割边数量可能过大,所引起的切割边数数量增加,计算耗时也随之增长的情况,本文利用一刀切规则中不同的切割顺序组合之间互不影响、对不同可排区域的选择顺序互不影响的条件,结合Golang语言层面对协程的支持而提出了相应的并行算法;(4)最后给出了完整的非递归启发式排样算法。并对其进行了数值实验及对比分析,验证了所提算法的正确性和有效性。数值结果表明,本文所提算法能够在保证材料利用率的同时极大地降低了整体时间消耗。

论文目录

摘要

Abstract

第1章绪论

1.1 本课题的研究目的和理论意义

1.1.1 研究目的及意义

1.2 二维排样问题研究现状

1.2.1 二维矩形件排样问题研究现状

1.2.2 二维非矩形件排样问题研究现状

1.3 本文的主要研究内容

第2章基础知识

2.1 排样问题定义

2.2 定序规则

2.3 定位规则

2.3.1 临界多边形（NFP）

2.3.2 最左最下算法（Bottom left）

2.4 一刀切（Guillotine）算法

2.4.1 矩形合并提升算法（The Rectangle Merge Improvement）

2.4.2 关于Guillotine算法的一刀切规则

2.5 最大矩形算法（The Maximal Rectangles Algorithms）

2.6 本章小结

第3章二维非规则一刀切排样算法

3.1 二维非规则一刀切排样问题的定义及特点

3.1.1 二维非规则一刀切排样问题的定义

3.1.2 二维非规则一刀切排样问题的特点

3.2 定位规则

3.2.1 移动装箱算法

3.2.2 满足一刀切约束的可排区域合并算法

3.3 非规则件一刀切排样算法

3.4 并行算法

3.5 算法分析

3.6 本章小结

第4章数值实验结果与对比分析

4.1 实验环境和算例介绍

4.2 实验结果

4.3 本章小结

结论

参考文献

攻读学位期间发表的学术论文

致谢

文章来源

类型: 硕士论文

作者: 何秋澄

导师: 王俊明

关键词: 一刀切,非规则排样,启发式算法,二维排样问题

来源: 哈尔滨理工大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 哈尔滨理工大学

分类号: O221.3

总页数: 60

文件大小: 1832K

下载量: 63

二维非规则一刀切排样问题研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢