《基于三块结构的圆形片剪冲排样算法》由会员分享，可在线阅读，更多相关《基于三块结构的圆形片剪冲排样算法（40页珍藏版）》请在金锄头文库上搜索。
1、广西师范大学 硕士学位论文 基于三块结构的圆形片剪冲排样算法 姓名：陈菲 申请学位级别：硕士 专业：计算机应用技术 指导教师：崔耀东 20090401 广西师范大学硕士研究生学位论文 I 基于三块结构的圆形片剪冲排样算法基于三块结构的圆形片剪冲排样算法 学生：陈菲 指导老师：崔耀东 专业：计算机应用技术 研究方向：优化计算技术与 CAD 年级：2006 中中 文文 摘摘 要要 计算机辅助优化排样问题就是在给定的材料上最优的排放一系列形状各异的零件，找 出零件的最优布局，使得原材料利用率最高。在实际生产中，优化排样问题广泛存在于机 械制造业、家具制造业以及皮革制造业等行业。传统的排样工作都是依靠
2、人工经验，耗时 长且下料利用率低，加大了生产成本。因此，设计有效的优化排样算法是提高下料效率和 利用率的关键。 在优化排样问题中，国内外学者对二维下料问题的研究给予了足够的重视，特别是针 对矩形毛坯和二维不规则毛坯的排样问题提出了很多算法，比如确定性算法：动态规划、 线性整数规划以及分枝定界等传统排样算法；不确定性算法：禁忌搜索、模拟退火算法、 遗传算法、神经网络算法等现代排样算法。然而，针对圆形排样问题的研究较少，实际生 产当中常遇到圆形片排样问题，而且圆形片排样问题是二维下料问题的一个分支，圆形毛 坯具有特殊的几何性质，研究一个合适的圆形片排样算法非常必要。 本文研究的圆形片剪冲排样问题，
3、是指在长和宽给定的板材上，运用剪冲下料工艺， 首先用剪床将板材切割成水平或竖直条带，每根条带中含相同直径的圆片；再将条带送至 冲床冲出圆片。在满足圆形毛坯需求的前提下，使板材的消耗尽可能少，达到节约生产原 材料的目的。 本文借鉴矩形三块排样方式的生成算法，提出了基于圆形片的三块结构剪冲排样算 法，包括两部分： 第一部分设计了无约束三块排样方式算法，采用两条相互垂直的分割线将板材分割成 三块子板材，每块子板材包括一组方向和长度都相同的条带。用动态规划算法确定子板材 中条带的最优布局，用枚举法确定两条分割线的位置，使整张板材价值达到最大。 第二部分将无约束三块结构排样算法作为基础算法，和线性规划算
4、法（LP）结合来求 解大规模二维圆片剪冲下料问题：已知库存板材尺寸、各种圆片的尺寸和需求量，确定下 料方案，使得满足全部圆片的需求所消耗的板材总面积最小。LP 法通过反复迭代求解，在 每一次迭代时，首先根据改善目标值的需要，计算出各种圆片的当前价值，然后调用无约 束三块结构排样算法，生成一个可能使目标值改善的排样方式，继续迭代。通常需要求解 大量的无约束三块结构排样方式，才能找到最优解。 由于 LP 在寻求最优解过程中需要不断调用无约束三块排样方式算法，因此无约束三 块排样方式算法的有效性直接决定了整个算法的效率，本文引入了突破点及减少搜索条带 范围的策略来提高算法的运行速度，以缩短求解时间。
5、 广西师范大学硕士研究生学位论文 II 规划和设计了排样系统的基本功能模块，开发了一个基于三块结构的圆形片优化排样 系统。采用文献中的例题、随机生成的例题以及生产实例对算法进行试验。对文献中例题 的计算结果表明，本文算法生成的最优三块排样方式在板材利用率上比 T 型排样方式有所 提高，生成排样方式的时间基本接近，在大部分情况下比多段排样方式利用率高；对随机 生成例题的计算结果表明，本文算法的计算时间可以满足一般实践应用的要求，具有现实 的意义。对生产实例的计算结果表明，本文算法在解决实际生产问题时与多段排样方式相 比，可以得到较好的排样效果，而且切割工艺简单。 关键词：关键词：圆片切割，剪冲下
6、料，两维切割，三块排样方式 广西师范大学硕士研究生学位论文 III A cutting and punching algorithm of circles based on three blocks pattern Student: Chen Fei Tutor: Cui Yaodong Major: Computer Application and Technique Research Area: Optimization and Computation Technology; Computer aided design Abstract The purpose of the compute
7、r aided optimal layout of the parts with different shapes is to find the arrangement of parts and maximize material usage of the pattern. In real production, cutting stock problems appear in many industries, such as mechanical, furniture and leather manufacturing, etc. Traditional works depend on th
8、e manual experience. It increases the cost of the product because of long working time and low material usage, consequently the design of efficient algorithms for generating cutting patterns is important for improving the productivity and material usage. In the cutting problems, academicians in and
9、abroad work on two-dimensional cutting problems deeply, especially advance many algorithms for rectangle and irregular packing problems. There are deterministic and non- deterministic algorithms. Deterministic algorithms include those based on traditional techniques such as dynamic programming, inte
10、ger programming, linear programming, branch-and-bound approach, etc. Non-deterministic algorithms include those based on such techniques as tabu search, simulated annealing, genetic algorithms and neural networks, etc. However, there are few algorithms for the circle cutting problem. The circle cutt
11、ing problem appears widely in the real world. Meanwhile, the circle cutting problem is a branch of the two-dimensional cutting problem. The circular blank has special characteristics on geometry. As a result, it is necessary to design a suitable algorithm for the circle cutting problem. This paper w
12、orks on the circle cutting problem. The width and length of the sheet is fixed, and the shearing and punching process is applied in the manufacturing. First the sheet is cut into horizontal or vertical strips by a guillotine shear, where each strip includes circular blanks of the same diameter. Then
13、 the blanks demanded are cut from the strips by a stamping press. The objective is to minimize the sheet cost required to fulfill the blank demands. This paper presents the algorithm for generating three-block patterns of circular blanks, where the shearing and punching process is applied. The algor
14、ithm uses the idea of the algorithm for three-block patterns of rectangular blanks. The main work includes two parts: The first part designs an algorithm for the unconstrained three-block circle cutting problem (UTBCC). The algorithm cuts the sheet into three sub sheets using two dividing lines whic
15、h are 广西师范大学硕士研究生学位论文 IV perpendicular to each other. Each sub sheet contains a group of strips which have the same orientation and length. The algorithm uses dynamic programming algorithm to determine the optimal layout of the strips in the sub sheets, and uses an enumeration method to determine th
16、e position of the two dividing lines so as to maximize the value of the whole sheet. The second part takes the algorithm for the UTBCC as a basic algorithm, and combines it with linear programming (LP) approach to solve the two-dimensional circle cutting problem, in which the size of the sheet, the size and demands of all circular blanks are known, the objective is to determine the cutting plan so as to minimize the sheet cost required to fulfill the blank demands. The LP approach solves t
