（机械设计及理论专业论文）面向机械制造的计算机辅助排样系统的研究与实现.pdf

浙江大学硕士学位论文摘要 摘要 在机械制造行业里，排样主要研究零件的布局，目的是提高材料利用率， 同时满足加工工艺的要求。人工排样效率低，难以得到高质量的排样方案。计算 机辅助排样技术充分利用计算机的快速计算优势，可以在较短的时间内得到较优 的排样方案，从而提高生产效率，降低生产成本，增强企业竞争力。 本文研究了排样类别的划分方法，根据零件毛坯的种类、数量、加工工艺三 者之间的关系细化了每一大类排样问题。 本文总结了排样理论和算法的研究现状和发展趋势，分析了典型排样算法的 优点和不足。 本文详细论述了连分数算法，将连分数算法应用于单一矩形件排样，设计了 单一矩形排样的无约束排样、有约束排样、板材分割算法，可以达到单一矩形排 样的最优排样和板材的最优分割。 本文将连分数算法应用于条带单一排样，采用分区计算的方法精确计算板材 可以排放毛坯的最大个数，与分支定界算法结合，设计了单一条带排样的无约束 排样、有约束排样、板材分割算法，可以达到单一条带排样的最优排样和板材的 最优分割。 本文分析了冲裁条带排样研究中的两个极端情况，提出了根据条带在板材上 的排样结果来寻求最优的条带排样参数的方法，将两大领域有机统一起来，从而 实现条带排样参数的全局寻优。 本文分析了当前求解排样参数的几种典型算法的优点和不足，提出了结合平 行线化和顶点碰撞特性的思想，采用边界划分、子边界离散、予边界凸顶点信息 提取等方法，使计算具有目的性，使预处理信息具有可重用性，从而快速计算包 括嵌套排样在内的所有情况下的排样参数，这种方法同样适用于不规则零件排样 的解码计算和其它需要求解毛坯间距的情况。 关键词：排样：连分数；分支定界；矩形；条带；冲裁；优化 浙江大学硕士学位论文 摘要 a b s t r a c t i nt h ei n d u s t r yo fm e c h a n i c a lm a n u f a c t u r i n g ，p a c k i n gi st or e s e a r c hh o wt ol a y p a r t s o nt h es t u f ft oa c h i e v eh i g h e rm a t e r i a lu t i l i z a t i o nr a t i oa n db e t t e rp r o c e s s t e c h n i c s t h et r a d i t i o n a lm a n u a lp a c k i n gm e t h o di m p e d e sc o r p o r a t i o n sd e v e l o p m e n t b e c a u s eo f i t si n e 伍c i e n c ya n di t si n f e r i o rp a c k i n gq u a l i t y c o m p u t e ra i d e dp a c k i n gi s m u c hm o r ee f f e c t i v e ，c o u l dg a i np a c k i n gp r o j e c t sw h o s eq u a l i t ya l eb e t t e ri nm u c h l e s st i m e s oi tc a l le n h a n c ec o r p o r a t i o n sc o m p e t i t i o nb yi m p r o v i n go p e r a t i n g e f f i c i e n c ya n dr e d u c eo p e r a t i n gc o s t s t h em e t h o d ss o r t i n gp a c k i n ga r er e s e a r c h e d b a s e do nt h en u mo f p a r t ss o r t ，t h e u u mo f e v e r y p a r t ，t h ep r o c e s st e c h n i c ，e v e r ys o r to f p a c k i n gp r o b l e m i ss u b d i v i d e d s t a t e o f - t h e a r ta n df u t u r et r e n d so f p a c k i n gt h e o r ya n da l g o r i t h mi ss u m m a r i z e d t y p i c a lp a c k i n ga l g o r i t h m s m e r i ta n dd i s a d v a n t a g ea l ea n a l y z e d c o n t i n u ef r a c t i o n sa l g o r i t h mi sd i s c u s s e d b a s e do nc o n t i n u ef r a c t i o n sa l g o r i t h m ， a ne f f e c t i v ep a c k i n ga l g o r i t h mf o rr e c t a n g u l a rb l a n k so fas i n g l es i z eb a s e do nc u t t i n g c r a f ti sp u tf o r w a r d an e wa l g o r i t h ma p p l i e di i lc u t t i n gal o n gr e c t a n g u l a rs h e e ti n t o s e v e r a ls e c t i o n si sa l s od i s c u s s e d , ap a c k i n ga l g o r i t h mu s i n gi l lt h ec a s ew h e r et h e b l a n k sh u mi sc e r t a i ni sd e s i g n e d t h e ya l lc o u l dg e tb e s tr e s u l t c o n t i n u e df r a c t i o n sa l g o r i t h mi sa p p l i e di np a c k i n gf o rp u n c hs t r i p so fas i n g l e t y p e am e t h o du s i n gt o c a l c u l a t et h em o s tn u m b e ro fp i e c e st h r o u g ht h ew a yo f s u b d i v i d i n gt h es h e e ti n f os e v e r a ls e c t i o n si sd i s c u s s e d t w op a c k i n ga l g o r i t h m su s i n g i nt h ec a s et h en u m b e ro f p i e c e si sc e r t a i na n dn o ta r ep u tf o r w a r d as u b d i v i d i n gs t u f f a l g o r i t h mi so f f e r e d t h e ya l lc o u l dg e t b e s tr e s u l t t h et w oe x t r e m e n e s so ft h er e s e a r c ha b o u ts t r i pp a c k i n ga r ea n a l y z e d an e w m e t h o do p t i m i z i n gs t r i pp a c k i n gp a r a m e t e r sb a s e do nt h ep a c k i n gr e s u l to fs t r i po n t h es t u f f i sc o n s i d e r e d ，u n i f y i n gt w om a i nr e s e a r c ha r e a s t h em e r i ta n dd i s a d v a n t a g eo ft y p i c a lp a c k i n ga l g o r i t h m sf o rp u n c hs t r i pa l e a n a l y z e d a ni d e ai m e f a t i n gp a r a l l e la n dv e r t e xi sp u tf o r w a r d t h r o u g l l 翻d i n ga n d d i s p e r s i n gb o r d e r l i n e ，d i s t i l l i n gt h ei n f o r m a t i o no f p r o t r u d i n gv e r t e x e s ，t h ec a l c u l a t i o n i sp u r p o s e f u l ，t h ei n f o m a a t i o nc o u l db er e u s e d t h em e t h o dc o u l dg e ts t r i pp a c k i n g p a r a m e t e r si nm u c hl e s st i m e n om a t t e rn e s t i n gp a c k i n go rn o t t h em e t h o d i sa l s oi 1 1 p o i n ti nd e c o d i n gf o ri r r e g u l a r - s h a p e dp a r t sa n do t h e re a s en e e d i n gc a l c u l a t et h e d i s t a n c eo f t w op a r t s k e yw o r d sp a c k i n g ；c o n t i n u e df r a c t i o n s ；b r a n c h i n g - b o u n d i n g ；r e c t a n g u l a r ；s t r i p p u n c h ；o p t i m i z e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得堂姿盘堂或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 唐生象3签字日期：勿印7 年，月，j 日 学位论文版权使用授权书 本学位论文作者完全了解逝鎏盘茎有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权逝江盘堂可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 唐丝剁 签字日期：缈7 年月f ie l 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 砂拐 签字日期：7 纯印年 月，日 | 电话： 邮编： 浙江大学硕十学位论文 第一章绪论 第一章绪论 1 1 研究背景 计算机辅助排样( c a n ，c o m p u t e ra i d e dn e s t i n 曲是计算机辅助设计与制造 ( c a d c a m ，c o m p u t e r a i d e dd e s i g n c o m p u t c ra i d e dm a n u f a c t u r e ) 的重要分支之 一，在工程应用中，型材和棒材下料、冲载件排样、玻璃切割、报刊排版、家具 下料、服装裁剪、皮革裁剪、造船、车辆和发电设备生产中都存在大量的下料闯 题。在机械制造行业中，由于板类零件具有性能优越，制造工艺相对简单、成 本比较低廉等优点，因此板类零件被广泛应用，但板类零件存在共同问题：排样 问题。排样问题的主要目标是在满足相应加工工艺要求的前提下，最大程度地利 用原材料。【2 1 排样问题同样要求在许可的时间内给出较优的排样结果。 传统的手工排样效率低、劳动强度大，不仅耗费了企业技术人员大量的劳动， 而且人工排样受人的工作态度与能力所限制，很难给出材料利用率最高或接近最 高的排样方案，也难以在较短时间内获得较好排样方案，降低了企业的生产效率 和企业的市场反应能力，增加了生产成本。应用c a n ，可以充分发挥计算机强 大的计算能力，在较短的时间内经过大量排样方案的比较，选出材料利用率最高 或接近最高的排样方案，达到节约材料的目的。 3 1 下料排样问题的整体描述：有两组基本数据，一组是大的原材料的尺寸( 一 维或者多维) ，另一组是小的零件的尺寸；将小的零件在原材料上进行合理几何 组合，切割下料。如何确定下料排样方案以使材料利用率最高就是排样问题。i l l 有许多问题如下料问题、减少废料问题( c u t t i n gs t o c kp r o b l e ma n dt r i ml o s s p r o b l e m ) 、装箱问题、二维装箱问题、条料排样、背包问题i np a c k i n g 、d u a lb i n p a c k i n g 、s t r i pp a c k i n ga n dk n a p s a c kp a c k i n gp r o b l e m ) 、车辆装货、货盘装载、集 装箱装货、汽车装货问题( v e h i c l el o a d i n g 、p a l l e tl o a d i n g 、c o n t a i n e rl o a d i n ga n dc a r l o a d i n gp r o b l e m s ) 、分类、损耗、设计、分割、布局、排样、划分问题( a s s o r t m e n t ， d e p l e t i o n ，d e s i g n , d i v i d i n g ，l a y o u t ，n e s t i n ga n dp a r t i t i o np r o b l e m ) 、资金预算、换零 钱、最优平衡、内存分配、多处理调度问题( c a p i t a l b u d g e t i n g ，c h a n g em a k i n g ，f i n e b a l a n c i n g ，m e m o r ya l l o c a t i o na n dm u l t i p r o c e s s o rs c h e d u l i n gp r o b l e m ) 等都可以看作 下料问题。 1 2 排样问题的分类 对排样问题的科学分类和标示是全面了解和解决排样问题的基础。文献 4 将下料问题归为g e o m e t r i cc o m b i n a t o r i c s ，按照是否为空间尺寸划分为狭义下料 浙江大学硕士学位论文第一章绪论 问题和广义下料问题。狭义下料问题是指以空间尺寸作为排样依据的排样问题， 如切割下料、物料排放等，雨广义下料问题则不仅仅将空间尺寸作为排样依据， 排样考虑的因素可以是重量、时间、资金、内存等，车辆装货问题、多处理器调 度问题、资金预算问题、内存分配问题都是广义下料问题。当前研究的比较多的 还是狭义排样问题，而且广义排样问题可以转化为狭义排样问题。狭义排样问题 可以按零件的维数划分为：维排样、一维半排样、二维排样、三维布局。 1 2 1 一维排样 一维排样问题又称线材排样问题，是指在排样时只需考虑一个方向的尺寸。 例如，将较长的型材、管材、棒材等，分割成各种较短的毛坯。典型的应用领域 包括门窗、金属结构、金属制品、普通机械、专用设备、交通运输设备、电气机 械等制造行业，这些行业所属企业在制造过程中，需要将线材分割成较短的毛坯， 用于生产产品”。根据原材料长度是否相等，一维优化下料可以分为定尺线材排 样和不定尺线材排样。 1 2 1 1 定尺线材排样 只有一种线材可以使用。在一种线材上可以有多种排样方式，每种排样方式 含有的毛坯的种类和数量都不相同。定尺线材排样的目的就是选择若干种排样方 式，计算各种排样方式所需的线材数量，目的是线材价值最小即线材数量最少， 同时满足对毛坯的数量要求f 6 】。 设有m 种毛坯，第i 种毛坯的需求数量为n i ，长度为l i ；线材长度为l ，有 n 种线材排样方式，第j 种线材排样方式含第i 种毛坯马j 个，则毛坯的长度之和 不大于线材的长度即 巧l l j n j - i 设第j 种线材排样方式所需的线材数量为x i ，则定尺线材排样是求 z = _ i = 1 最小，同时满足 弓巧：m ，l i s m j = l 五，z ：，_ 为非负整数 显然，这是整数规划问题。 浙江大学硕士学位论文第章绪论 1 2 1 2 不定尺线材排样 如果线材是型材，市场上往往有热轧和冷轧型材之分。冷轧型材长度一样， 热轧型材则长短不一，其长度在一定范围内分布，称为不定尺型材。如果企业购 进的是热轧型材，每种长度都看作是一种线材，则线材数量会很大。一般的处理 是将线材按照某种间隔分组，处于某一组内的线材按照该组长度最短的线材来排 样。如果企业的库存里有多种长度不一的型材，也需要考虑不定尺线材排样问题。 目的是线材价值最小【3 】。 设有m 种毛坯，第i 种毛坯的需求个数为m i ，长度为l i ；有n 种线材，第j 种线材的库存数量为n j ，价值为c j ，长度为l ，有蝎种排样方式，第p 种排样 方式含第i 种毛坯的个数为p j p i ，则毛坯长度之和不大于线材长度即 句，l j n ，l t , 1 a i 如果a 不是整数，同理可得 q ：9 1 + 一i ，口2 1 所以 口2 吼+ 巳- j ：吼一l + 一1 ， 1 口“ 吼+ 口2 + + 丁 吼一1 + 吼 ( 2 1 ) 式2 1 就叫做连分数，简计为 q o ，q 。，g ：，q 。】，q 。称为连分数的部分商。如果 以一o o ，则为无限连分数，否则为有限连分数。【9 1 ，q ：，9 3 ，q 。】，七n 称为连分 数，矾】的第k 个渐进分数，用参表示。m 】 2 2 2 连分数的性质 浙江大学硕上学位论文 第二章连分数和连分数算法 定理2 1 任何有理数都可以表示为有限连分数。 定理2 2 连分数，吼，g ：，吼】的渐进分数的分子分母满足 只q 一，一只一，q = ( 1 ) k - i 七 0 定理2 1 和定理2 2 的证明见文献 9 9 】。 2 3 连分数算法 2 3 1 数学模型 在4 曰的矩形上剪切c d 的小矩形，小矩形的数目记为垒尝。 定理2 3 ( 雪) = m a x ( “+ d y l 口+ d y s 爿( b 龇j ，z y 2 0 ，则尝：墨。 c ac a 证明略。称a + ( 伊) 为c 、d 的不大于爿倒的最大突破点。 定舭4 当时，等= 脚+ l 纠黔。 l x j 表示不大于x 的最大整数， x 表示x 的小数部分，下同。其几何意义 见图2 1 。 图2 1 定理2 5 如果爿= r c + s d ，b = t c + u d ，s ，t ，“z ，r ，5 ，t ，“0 ，则 坐：，“州+ r e , t _ _ _ f f c + s d , u d c ，dc ，dc d l 阳i l 浙江大学硕十学位论文第一二章连分数和连分数算法 几何解释如图2 2 所示，数学证明见文献 2 6 】。 曰1 ci i d 一 硒 托一砖一 圈2 2 不失一般性地假设c 、d 的最大公约数g e d ( c , d ) = 1 。对于任意a e d c d ， 都可以表示为a = c x + d y ，x ，y z ，x ，y 0 。因此在连分数算法的讨论中假定 m i n ( a ，b ) c d c d 。对于a 、b ，我们寻求 a = m c d + r c + s d ，b = n c d 十纪+ u d ，0 r , t d ，0 s ，u c ，根据定理2 5 ，可 得 掣：n ( m c d 们+ s d ) + m ( t c + u d ) + r u + s t + r c , t c + _ s d , u d f ，ac ，ac d 因此，求磐可转化为两个问题 c a 】计算譬，_ s d , u d ，中m a x ( r , t ) d ，m a x ( s , u ) d ，c ，c ” - t , c s u o 注意到万cn 詈 c ”时，可将s ”与u 交换位置，再利用结论 2 6 一次，即可利用结论2 5 。 由以上结论可知，经过有限次的算术操作，我们可以不断地把( c ，d ) 转化为 b ，d 或者f c ”d 1 ，盲列d 、d t 、dn 中的个为1 然后相椐宦弹2 4 得m 嚣后 浙江大学硕士学位论文第二章连分数和连分数算法 结果。 根据定理2 2 ，当i 为奇数时，只。q f 一只级。= - 1 ，当i 为偶数时， 只。q f 一只q 。= 1 。而我们要求c d - c d = - 1 ，甜l c “d = 1 ，因此我们可以用 ( 最，q + ，) 来表示( c ，d ) ，在i 为奇数时用( p ，q ) 来表示( c ：d ，在i 为偶数时用 ( # ，q ) 来表示( c d i ) 。 算法步骤： c d - 【，o l ，a 。】；只q = 口o ，a 1 ，一，q 】； r = 0 ；s = 0 ： a l = n 姒o ，) u l = n 血o ，却) ；r l = l n s i x ( ，嘎t l # 画函( f ) ； 如r ( i = n 一1 ；i 一1 ；i 一一) j = s l ；u = u l ；r = r l ；t = t l ； i f ( i 为奇数1 s = s m o d p , ；u = u m o d ( 2 , s = s + l , l e , j u o , + 卜只j s q ； s l = m a x ( s ，“ ；“1 = m i n ( s ，u t 矿( ， q ) ，7 = r ；t = f ；g o t o e n d l ； r = f ( 瓯一，) q q 一( q + 。一r ) ；矗= 置+ f ( 足一r ( q 。- r ) i q ， p a ； f ( t q ) f = 以g o t o e n d l ； f = f ( q 。：- t ) l q , 1 q , 一( q 。一r ) ；r = 胄+ ，( 只，一( ! 易，一f ) q 只) ； e n d l ：r l = m a x ( r ，t 3 ；t l = m i n ( r ，t t ) 浙江大学碗士学位论文第二章连分数和连分数算法 e l s e r ”= r r o o dq f ；f ”= t r o o d q r = r + l r l q + j i p , + l t q , j r l 只； r l = m a x ( r 。，f ) ；n = m i n ( r 。，f ； f ( s 0 ) 扣。= s ；u “= “；g o t o e n d 2 ；) s 1 = ( 最，一, ) 4 1 4 一( 最。一s ) ；s = s + “( q f 。一f ( b ，一s ) 只 q ) ； 矿 o ，a ，c ，d z + ，根据文献 1 ，在方程( 2 1 ) 的解中： 最小的工= l 爿c y c j d 一爿d ，与之相搭配的j ，= a 厂- o x = 爿f m o d c ； 最小的y = l a d 1 d j c 一4 c 一，与之相搭配的x = a - d y = 彳d “m o d d 。 如果方程( 2 1 )