面向多规格板材件的矩形工件排样方法的研究

摘要

面向多规格板材件的矩形工件排样问题(2DVSBPP)就是指给出多种规格的矩形工件与板材，要求选出合适的板材组合，将矩形工件逐一排放在板材上，力求板材的总耗损最小，总利用率最高。作为一个经典的NPC问题，2DVSBPP在工件的排样过程中，通常面临两种工艺约束:“一刀切”约束和工件可旋转性约束。本文针对多规格板材件的矩形工件排样问题，提出了一种放宽式搜索算法(RelaxedSearch Algorithm，RSA)，该算法支持“一刀切”约束和矩形工件可旋转约束，具体包括:
　　1)多规格板材组合的构造算法。依据矩形工件的总面积，选择出可行的板材件组合，并将该组合按面积的增序方式排列。
　　2)单块板材件的排样算法。提出了一种基于组化策略的单板材排样算法，将矩形工件组合成一个单元体代替工件作为排样的基本单元，再设定对工件组的定位规则，在板材件满足“一刀切”约束的条件下，对板材件进行切割;进而，使用一种“排样——切割”的递归排样结构，以利用率是否低于给定的最低利用率作为回溯条件，配合最低利用率的二分遍历式收敛，提高了单块板材件的利用率。
　　3)放宽式搜索算法。在对板材件组合进行选取与单块板材件排样算法生成之后，按初始组合的板材件的顺序尝试排样，并逐步放宽组合的面积，从而逐步更换板材件，并使工件全部排放。
　　4)后处理算法。通过良劣集交换的方式，对已排样板材件上矩形工件的拆分与重组，进一步提高材料利用率。
　　使用国际通用的Benchmark案例进行测试，RSA算法于若干文献报道的算法，求解质量有所提升。
　　基于RSA算法与企业实际生产需求，开发了一套面向多规格板材件矩形工件排样的计算机辅助排样系统。

目录

摘要

第一章 绪论

1．1 研究背景与意义

1．2 二维排样问题的描述

1．2．1 二维排样问题的来源

1．2．2 二维排样问题的分类

1．3 国内外研究现状与发展趋势

1．3．1 单规格板材件排样问题研究现状

1．3．2 多规格板材件排样问题研究现状

1．3．3 二维排样问题的发展趋势

1．4 本文的研究内容与结构安排

第二章 2DVSBPP问题的模型与求解思路

2．1 2DVSBPP问题的描述

2．2 2DVSBPP问题的模型

2．2．1 板材件组合选取的数学模型

2．2．2 单块板材件排样的数学模型

2．3 求解2DVSBPP问题的思路

2．4 本章小结

第三章 板材件组合选取与单块板材件排样

3．1 板材件组合选取的描述

3．2 板材件组合的选取算法

3．3 单块板材件排样算法的设计背景

3．4 单片板材件的排样算法

3．4．1 矩形工件的组化

3．4．2 排样及切割方式

3．4．3 算法的递归结构

3．4．4 二分精确求解算法

3．5 本章小结

第四章 放宽式搜索算法求解2DVSBPP问题

4．1 放宽式搜索算法的描述

4．2 基于放宽式搜索算法的求解

4．3 后处理算法的描述

4．4 后处理算法的实现

4．5 测试案例

4．6 本章小结

第五章 计算机辅助排样系统设计

5．1 系统描述

5．2 系统功能规划

5．3 系统设计

5．4 本章小结

第六章 总结与展望

6．1 论文工作总结

6．2 今后工作展望

参考文献

攻读学位期间发表的论文

声明

致谢