基于层排样方式的矩形毛坯下料算法

论文摘要

在国民经济的许多行业中,都会遇到材料分割问题,需要进行大量的排样工作,如何给出材料利用率最高或者接近最高的排样方案是一项非常有意义的工作。传统的做法都是由人工完成,存在时间耗费大而且下料利用率低等缺点。随着近代优化计算技术和计算机的不断发展,计算机辅助排样CAN (Computer Aided Nesting)应运而生。CAN的作用,就是生成高利用率的材料分割方案,通过节约材料、减少排样工作量和简化切割工艺,最终达到降低产品成本的目的。矩形毛坯二维下料问题是指在满足全部矩形毛坯需求的前提下,所使用的板材总面积最小,在工业生产中有着重要而广泛的应用,并且讨论该问题是解决不规则形毛坯下料问题的基础,因此,对该问题的讨论不论是对实际应用还是理论上都具有重要的意义。矩形毛坯二维下料问题的解是一个排样方案,该排样方案由多个排样方式组成,并明确采用各排样方式的板材的张数。国内外学者对该问题进行了广泛的研究,通常采用顺序启发式算法、线性规划算法或者一些模拟优化算法来求解。随着生产的发展,企业下料环节影响排样的因素不断变化,具有新特征的排样问题不断出现。例如在解决矩形毛坯二维下料问题时,针对尺寸较大的板材,部分企业采用双时段下料工艺,第一时段利用具有多把平行刀具的自动机床将板材分割为多个板块,第二时段使用普通设备将尺寸较小的板块分割为毛坯。在这种下料工艺中,保证材料利用率的同时,要考虑充分发挥自动机床的效率,减少人工操作量,毛坯布局时采用适合的排样方式尤为重要。本文将板材简单块排样方式和解决带排样时采用的层排样方式结合,产生板材最优层排样方式,并与线性规划结合,解决采用双时段下料工艺的矩形毛坯二维下料问题。主要内容包括以下三方面：第一,采用动态规划实现无约束排样方式生成算法,解决单张板材所含毛坯价值最大问题。排样时使用一组平行的剪切线将板材分割为多个层,层的宽度等于最左边主毛坯的高度。除主毛坯外层的其余部分,按简单块排样方式生成规则排入毛坯。采用该排样方式,在第一时段具有尽可能多的剪切线,能充分发挥自动机床的效率。采用动态规划求解问题,根据多阶段决策过程的最优化原理,在得到某个尺寸板材最优层排样方式的同时,得到了所有小于该尺寸板材的最优层排样方式,而不用重复计算,大大提高了算法的效率。第二,将无约束排样方式生成算法与线性规划结合,解决矩形毛坯二维下料问题。采用线性规划求解下料问题时,计算结果含小数部分,但其表示按各排样方式切割的板材的张数,所以必须取整。传统的做法是将向上取整后的结果保存为最优排样方案。由于取整操作使结果存在误差,一些学者提出对取整结果进行检查优化。本文在此基础上做出以下改进：在线性规划模型求解过程中,对每次迭代计算得到的结果向上取整,都是一个可行的排样方案。对每一个结果进行检查优化,并将第一次迭代计算的优化结果作为当前最好排样方案,将每一次迭代计算的优化结果与之比较,不断更新当前最好排样方案。当线性规划计算结束后,将当前最好排样方案保存作为该下料问题的最优排样方案。第三,设计实现矩形毛坯下料系统。对大量的数据进行测试,并与相关文献的实验计算结果相比较。结果表明,本文算法在满足双时段下料工艺要求的同时,具有较高的下料利用率,是一种有效地求解矩形毛坯下料问题的算法。

论文目录

• 中文摘要
• Abstract
• 目录
• 第1章 绪论
• 1.1 引言
• 1.2 矩形毛坯二维下料问题的概述
• 1.3 本文的主要工作
• 1.4 本文的组织结构
• 第2章 矩形毛坯二维下料问题
• 2.1 矩形毛坯二维下料问题的描述
• 2.2 矩形毛坯二维下料问题的典型求解模式
• 2.2.1 顺序启发式算法
• 2.2.2 线性规划
• 2.2.3 模拟优化算法
• 2.3 矩形毛坯典型排样方式
• 2.3.1 剪切方式与非剪切方式
• 2.3.2 k阶段排样方式
• 2.3.3 两段与T形排样方式
• 2.3.4 简单块排样方式
• 2.3.5 带排样中采用的层排样方式
• 2.3.6 板材最优层排样方式
• 第3章 基于层排样方式的矩形毛坯下料算法
• 3.1 排样方式生成算法
• 3.1.1 动态规划算法原理
• 3.1.2 板材层排样方式生成规则
• 3.1.3 板材层排样方式生成算法的实现
• 3.2 排样方案生成算法
• 3.2.1 基于层排样方式的矩形毛坯下料算法
• 3.2.2 对最优排样方案的选择
• 第4章 矩形毛坯二维排样系统的开发与实验计算
• 4.1 矩形毛坯二维排样系统的开发
• 4.2 实验计算
• 4.2.1 本文排样方式和两阶段、三阶段排样方式的对比
• 4.2.2 本文排样方式和简单块排样方式的对比
• 4.2.3 本文算法生成排样方案和两阶段、T形排样方案的结果比较
• 4.2.4 不同取整方法的下料结果比较
• 4.3 实验结果分析
• 第5章 总结与展望
• 参考文献
• 攻读硕士学位期间发表的论文
• 致谢