基于三块结构的圆形片剪冲排样算法

论文摘要

计算机辅助优化排样问题就是在给定的材料上最优的排放一系列形状各异的零件,找出零件的最优布局,使得原材料利用率最高。在实际生产中,优化排样问题广泛存在于机械制造业、家具制造业以及皮革制造业等行业。传统的排样工作都是依靠人工经验,耗时长且下料利用率低,加大了生产成本。因此,设计有效的优化排样算法是提高下料效率和利用率的关键。在优化排样问题中,国内外学者对二维下料问题的研究给予了足够的重视,特别是针对矩形毛坯和二维不规则毛坯的排样问题提出了很多算法,比如确定性算法:动态规划、线性整数规划以及分枝定界等传统排样算法;不确定性算法:禁忌搜索、模拟退火算法、遗传算法、神经网络算法等现代排样算法。然而,针对圆形排样问题的研究较少,实际生产当中常遇到圆形片排样问题,而且圆形片排样问题是二维下料问题的一个分支,圆形毛坯具有特殊的几何性质,研究一个合适的圆形片排样算法非常必要。本文研究的圆形片剪冲排样问题,是指在长和宽给定的板材上,运用剪冲下料工艺,首先用剪床将板材切割成水平或竖直条带,每根条带中含相同直径的圆片;再将条带送至冲床冲出圆片。在满足圆形毛坯需求的前提下,使板材的消耗尽可能少,达到节约生产原材料的目的。本文借鉴矩形三块排样方式的生成算法,提出了基于圆形片的三块结构剪冲排样算法,包括两部分:第一部分设计了无约束三块排样方式算法,采用两条相互垂直的分割线将板材分割成三块子板材,每块子板材包括一组方向和长度都相同的条带。用动态规划算法确定子板材中条带的最优布局,用枚举法确定两条分割线的位置,使整张板材价值达到最大。第二部分将无约束三块结构排样算法作为基础算法,和线性规划算法(LP)结合来求解大规模二维圆片剪冲下料问题:已知库存板材尺寸、各种圆片的尺寸和需求量,确定下料方案,使得满足全部圆片的需求所消耗的板材总面积最小。LP法通过反复迭代求解,在每一次迭代时,首先根据改善目标值的需要,计算出各种圆片的当前价值,然后调用无约束三块结构排样算法,生成一个可能使目标值改善的排样方式,继续迭代。通常需要求解大量的无约束三块结构排样方式,才能找到最优解。由于LP在寻求最优解过程中需要不断调用无约束三块排样方式算法,因此无约束三块排样方式算法的有效性直接决定了整个算法的效率,本文引入了突破点及减少搜索条带范围的策略来提高算法的运行速度,以缩短求解时间。规划和设计了排样系统的基本功能模块,开发了一个基于三块结构的圆形片优化排样系统。采用文献中的例题、随机生成的例题以及生产实例对算法进行试验。对文献中例题的计算结果表明,本文算法生成的最优三块排样方式在板材利用率上比T型排样方式有所提高,生成排样方式的时间基本接近,在大部分情况下比多段排样方式利用率高;对随机生成例题的计算结果表明,本文算法的计算时间可以满足一般实践应用的要求,具有现实的意义。对生产实例的计算结果表明,本文算法在解决实际生产问题时与多段排样方式相比,可以得到较好的排样效果,而且切割工艺简单。

论文目录

• 中文摘要
• ABSTRACT
• 第1章 绪论
• 1.1 计算机辅助优化排样简介
• 1.1.1 CAN 的主要应用领域及意义
• 1.1.2 优化排样问题的类型
• 1.2 圆形片排样问题
• 1.2.1 研究的目的和意义
• 1.2.2 国内外研究现状
• 1.2.3 问题难度和研究的必要性
• 1.3 本文的主要工作
• 1.4 本文的组织结构
• 第2章 圆形片优化排样问题
• 2.1 圆形片排样问题的描述
• 2.1.1 问题的定义
• 2.1.2 问题的难度
• 2.2 圆形片优化排样的理论基础
• 2.2.1 动态规划理论
• 2.2.2 背包算法
• 2.3 圆形毛坯排样的线性规划模型
• 第3章 圆形片排样问题的典型排样方式
• 3.1 圆形片条带
• 3.1.1 毛坯在条带上的排列方式
• 3.1.2 条带的宽度和价值向量
• 3.2 典型的排样方式
• 3.2.1 直切排样方式
• 3.2.2 T 型排样方式
• 3.2.3 两段排样方式
• 3.2.4 多段排样方式
• 3.2.5 多级排样方式
• 第4章 基于圆形片的三块结构生成算法
• 4.1 无约束三块结构生成算法UTBCC
• 4.1.1 算法的描述
• 4.1.2 算法的时间复杂度分析
• 4.2 算法UTBCC 的改进策略
• 4.3 圆形片三块排样方案生成算法TBCCLP
• 第5章 圆形片优化排样系统的开发与实验计算
• 5.1 圆形毛坯排样系统的研发
• 5.2 实验测试
• 5.2.1 测试一：UTBCC 算法和无约束T 型算法的实验对比
• 5.2.2 测试二：TBCCLP 算法与T 型及直切线性规划算法的实验对比
• 5.2.3 测试三：TBCCLP 算法生成的排样方案与多段排样方案的实验对比
• 5.3 实验结果分析
• 第6章 总结与展望
• 参考文献
• 攻读硕士学位期间发表的论文
• 致谢