基于填充式启发式算法的二维矩形排样问题

摘要

当今计算机技术、CAD技术和人工智能的飞速发展,为人们进行计算机辅助优化排样提供了可能性。优化排样在理论上属于具有最高复杂性的NP完全问题,是一个属于在理论上非常困难,但在实际生活中有广泛应用的亟待解决的课题。
　　 本文针对在一定的矩形材料上的小矩形切割的二维排样问题进行了研究,尤其是对军车制造中的钢板或者底板等材料在切割时定向一次性切割到头的排布,综合蚂蚁算法和模拟退火算法思想,提出一种最低水平线与填充式算法相结合的启发式排样算法。通过对计算机上随机产生的实验数据进行模拟,实现自动排样。并根据优化排样的特点,以及它们在实际应用中的不同要求构造了具有针对性的优化排样算法。
　　 本文通过实际钢板下料等切割工艺的过程,从在实际排样过程中所积累的经验出发,为矩形排样问题的高效快速求解提出了一种新颖的填充启发式算法。材料在切割时定向一次性切割到头的约束下,综合蚂蚁算法和模拟退火算法思想,提出一种最低水平线与填充式算法相结合的启发式排样算法。通过对计算机上随机产生的实验数据进行模拟,实现自动排样。在多种类、大批量军车制造生产中底板切割等的单次切割材料利用率上有所突破,得到较好的排样效果。

目录

文摘

英文文摘

第一章 绪论

1.1 优化排样的问题概述

1.1.1 优化排样问题的意义

1.1.2 优化排样问题的类别

1.1.3 排样问题的研究趋势

1.2 优化排样问题国内外研究概况

1.3 本文的主要研究工作

第二章 矩形件排样问题的研究

2.1 前言

2.2 矩形件下料工艺优化排样分析

2.3 模拟退火算法[30]

2.3.1 模拟退火算法概述

2.3.2 模拟退火算法的构造及步骤

2.4 蚂蚁算法

2.4.1 蚂蚁算法概述

2.4.2 蚂蚁算法原理[31]¨

2.4.3 基本蚊群系统模型[32][33]

2.4.4 背包问题

2.4.5 蚂蚁算法求解

2.5 本章小结

第三章 二维矩形件排样问题的研究

3.1 二维矩形件排样问题的求余算法

3.1.1 算法描述

3.1.2 算法步骤

3.1.3 实验结果与结论

3.2 进化规划算法

3.2.1 进化规划算法的基本结构论

3.2.2 下料问题的进化规划算法

3.2.3 算法步骤

3.3 本章小结

第四章 基于填充式启发式算法的二维矩形排样问题

4.1 矩形件优化排样问题

4.1.1 矩形什优化排样问题的定义

4.1.2 矩形件排样问题的数学模型

4.2 优化排样问题的近似算法

4.2.1 邻域搜索算法

4.2.2 预处理

4.3 排样步骤

4.4 填充式启发式算法的基本策略

4.5 本章小结

第五章 总结与展望

致谢

参考文献

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