矩形件优化排样算法的研究与实现

论文摘要

矩形件优化排样问题是指在矩形的板材上,要排放多种不同尺寸的矩形件,如何使这些矩形件既不互相重叠,又不超出板材边界的条件下,使得材料的利用率达到最高。它广泛应用于玻璃、钢板、木材和皮革等。从数学计算复杂性理论看,优化排样问题属于具有较高计算复杂性的NP完全问题,至今还无法找到解决该问题的有效多项式时间算法[1]。好的排样结果可以提高生产效率,提高材料的利用率,降低生产成本,提高企业的竞争力。对矩形件优化排样问题的研究具有深远的理论意义和实际意义。本文在分析矩形件优化排样问题特点的基础上,建立了该问题的数学模型,描述了一些常见的优化算法和排样算法。在一定的约束条件下,应用遗传算法方法对矩形件排样问题进行优化求解,对算例的求解结果进行比较与分析。首先介绍了矩形件优化排样问题的数学模型和矩形件排样问题的排样算法,如剩余矩形匹配法、BL算法、下台阶算法、基于最低水平线的搜索算法。比较了这些算法的优缺点。其次介绍了在大规模生产中矩形件的下料工艺,如“一刀切”;为了提高生产效率,相同的零件尽可能排放在一起;在加工时,要有安全距离的保障等。再次介绍了遗传算法的基本原理,采用遗传算法对矩形件排样问题进行求解。在求解过程中,给出了遗传算法的编码与解码方法、适应度函数的定义方法、遗传算子的设计方法以及关键参数。通过对具体的算例进行求解,对求解的结果进行分析比较。最后,基于以上理论,用VB.NET开发了矩形件优化排样系统。其中包括用户登录模块,零件与板材管理模块,利用优化算法进行排样的模块等。本文将遗传算法与基于最低水平线的搜索算法相结合应用到矩形件排样优化中,产生的排样结果满足“一刀切”和相同的矩形件尽量排放在一起等工艺要求,并且使板材的利用率在94%左右,可以应用到企业的实际生产中。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 问题的提出
• 1.2 优化排样问题国内外研究现状
• 1.3 优化排样问题主要应用领域
• 1.4 课题的来源及主要研究内容
• 1.5 论文的创新点
• 第二章 矩形件排样问题的数学模型及优化排样算法
• 2.1 矩形件排样问题的数学模型
• 2.1.1 矩形件排样问题的描述
• 2.1.2 数学模型
• 2.2 优化排样算法分析
• 2.3 矩形件优化算法
• 2.3.1 枚举法
• 2.3.2 启发式算法
• 2.3.3 贪心算法
• 2.3.4 模拟退火算法
• 2.3.5 遗传算法
• 2.3.6 伪并行遗传算法
• 2.3.7 蚁群算法
• 2.4 矩形件优化算法的优缺点
• 2.5 矩形件排样算法
• 2.5.1 剩余矩形匹配法
• 2.5.2 BOTTOM-LEFT 算法
• 2.5.3 下台阶算法
• 2.5.4 最低水平线算法
• 2.5.5 基于最低水平线的搜索算法
• 2.6 矩形件排样算法的优缺点
• 本章小结
• 第三章 矩形件排样问题影响因素及约束条件
• 3.1 影响因素
• 3.1.1 几何因素
• 3.1.2 加工工艺因素
• 3.1.3 其他因素
• 3.2 约束条件
• 本章小结
• 第四章 遗传算法求解矩形件优化排样问题
• 4.1 遗传算法的简介
• 4.1.1 遗传算法的生物学基础
• 4.1.2 遗传算法的特点
• 4.1.3 遗传算法的应用
• 4.1.4 基本遗传算法描述
• 4.1.5 小生境遗传算法
• 4.1.6 混合遗传算法
• 4.2 矩形件优化排样的遗传算法
• 4.2.1 基因编码
• 4.2.2 解码
• 4.2.3 初始化种群
• 4.2.4 交叉算子
• 4.2.5 变异算子
• 4.2.6 适应度函数
• 4.2.7 选择算子
• 4.3 计算实例
• 4.3.1 进化代数改变时排样结果的对比
• 4.3.2 初始群体改变时的排样结果对比
• 4.3.3 交叉概率改变时结果比较
• 4.3.4 变异概率改变时结果比较
• 本章小结
• 第五章 矩形件优化排样系统的设计与实现
• 5.1 矩形件优化排样系统的总体结构
• 5.2 用户管理模块
• 5.3 数据管理模块
• 5.4 矩形件优化套料模块
• 本章小结
• 总结与展望
• 1. 总结
• 2. 展望
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢