（机械电子工程专业论文）基于余料的五金零件排样系统研究与开发.pdf

摘要 摘要 计算机辅助排样是根据一定的优化原则，利用计算机图形学和相关的计算 机技术，将传统的排样作业计算机化，把排样工人丰富的经验和计算机具有的快 捷、方便、灵活等特点结合起来，从而快速获得较高的材料利用率的一种排样方 法。 五金专业镇中小型零件加工企业为了节省成本，通常购买大型企业加工后的 余料作为自己的原材料。一方面因为小五金零件尺寸较小，余料可以满足加工要 求；另一方面余料价格只有整材的三分之一左右。但由于材料成本往往占n d , 五 金产品总成本的6 0 - 8 0 ，进一步优化材料的利用率对中小企业而言意义重大。 本文对基于余料的五金零件排样系统进行了研究。对于基于余料的排样系统 来说，板材并非是完好的，而且同时限定板材的长度和宽度，对可排的区域有严 格的限制。可以这样解释基于余料的排样，即在固定长宽的矩形余料上，摆放尽 可能多的零件，使余料的利用率尽可能的大。 本文在现有二维排样的基础上，提出了“余料分区半自动优化排样方法”。 该方法首先找出待排样零件的包络矩形，以该包络矩形作为排样的对象，把复杂 形状的排样问题转化为了矩形件排样。然后对余料已加工位置计算包络矩形，基 于“分块结构模式”和“排样区域连续 原则，将余料分割为几个单独的矩形区 域。接下来，在各个矩形分区内，根据“b l 策略”和“剩余平面集中策略 ，自 动实现矩形件的排样。最后进行交互式操作，添加零件，调整零件位置，得到合 理的排样结果。 系统设计了与a u t o c a d 之间的接口，用来输入和输出d x f 格式文件。在导入 余料和零件的d x f 文件基础上，进行基于包络矩形的半自动优化排样；然后，利 用交互式排样工具作交互式修改，得到相对合理的排样结果；显示最后排样结果， 输出排样d x f 文件。 系统的实施可为企业降低成本，提高材料利用率，对中小型五金零件加工企 业具有较好的实用价值。 广东下业人学硕l j 学位论文 关键词：排样系统；余料；交互式排样 木本课题获得国家科技支撑计划项目( n o 2 0 0 6 b a f 0 1 a 4 1 ) 资助。 a b s t r a c t a b s t r a c t t h ec o m p u t e ra i d e dn e s t i n gi sam e t h o dt h a tu s e st h ec o m p u t e rg r a p h i c s ，t h e r e l a t e dc o m p u t e rt e c h n o l o g ya n dt r a d i t i o n a ll a y o u to p e r a t i o n s i ti sa c c o r d i n gt os o m e o p t i m i z e dp r i n c i p l e s t h ec a ns y s t e mi sc o m b i n i n gt h ew o r k e r se x p e r i e n c ea n d t h e c o m p u t e r sq u i c k ，c o n v e n i e n t ，f l e x i b l ec h a r a c t e r i s t i c s ，w h i c hc a nq u i c k l yg e th i g h e r m a t e r i a lu t i l i z a t i o nr a t e t h es m e so ft h eh a r d w a r ep r o f e s s i o n a lt o w nb u yl a r g ee n t e r p r i s e sr e m a i n d e r m a t e r i a la st h e i rr a wm a t e r i a l si no r d e rt os a v ec o s t s t h e yl i k et op r o c e s st h e m e c h a n i c a lp a r t sb a s eo nt h er e m a i n d e rm a t e r i a l sh a st h ef o l l o w i n gr e a s o n s ：o no n e h a n d ，t h es m a l lm e t a lc o m p o n e n t sa r er e l a t i v e l ys i m p l es m a l li ns i z e ，t h er e m a i n d e r m a t e r i a lc a nm e e tt h er e q u i r e m e n t s ；o nt h eo t h e rh a n d ，t h ep r i c eo ft h er e m a i n d e r m a t e r i a l si so n l yo n e t h i r do ft h ec o m p l e t e l ym a t e r i a l s a sf a ra st h e s es m e sa r e c o n c e r n e d ，t h er a wm a t e r i a lc o s t su s u a l l yo c c u p y6 0 8 0 o ft h et o t a lc o s t s ，s o ，t h e f u r t h e ro p t i m i z a t i o no ft h em a t e r i a lu t i l i z a t i o nr a t ei ss i g n i f i c a n t t h i sp a p e rh a ds t u d i e dt h e n e s t i n gs y s t e mo fm e t a lc o m p o n e n t sb a s e do nt h e r e m a i n d e rm a t e r i a l ”t h em a t e r i a l sf o r ”n e s t i n gs y s t e mb a s e do nt h er e m a i n d e r m a t e r i a l ”，i sn o tc o m p l e t e ，t h eb o a r da l s ol i m i t st h el e n g t ha n dw i d t h ，t h ea r e at h a t c a nb en e s t e di ss t r i c t l yr e s t r i c t e dt o o w ec o u l de x p l a i nt h en e s t i n gb a s e do n r e m a i n d e rm a t e r i a ll i k et h a t ：o nt h er e c t a n g u l a rr e m a i n d e rm a t e r i a lw h i c hl i m i tt h e l e n g t ha n dw i d t h ，p u ta sm u c hc o m p o n e n t sa sp o s s i b l e ，a n dm a k ea sh i g h e ru t i l i z a t i o n r a t ea sp o s s i b l e b a s e do nt h ee x i s t e n tr e s e a r c h e so n2 dl a y o u t ，t h i sp a p e rp r o p o s e sam e t h o d w h i c hc a nb ec a l l e d ”t h er e m a i n d e rm a t e r i a ld i v i s i o ns e m i - a u t o m a t i c0 p t i m a ll a y o u t m e t h o d ”t h e r ea r es p e c i f i cs t e p s ：t h ef i r s ts t e p ，f o u n dt h ep a r t s r e c t a n g u l a re n v e l o p e ， g o tt h e s er e c t a n g l e sa st h el a y o u to b j e c t s t h e n ，t h ec o m p l e xs h a p e sl a y o u tp r o b l e m t r a n s f o r m e dt or e c t a n g u l a rp i e c e sl a y o u tp r o b l e m t h e ng o tt h ep r o c e s s e dp o s i t i o n s r e c t a n g u l a re n v e l o p e b a s e do n ”b l o c ks t r u c t u r em o d e ”a n d ”c o n t i n u o u sl a y o u ta r e a ”， t h er e m a i n d e rm a t e r i a lw i l lb ed i v i d e di n t os e p a r a t e dr e g i o n s i ne a c hr e g i o n ，w e 广东t 业人学硕i j 学位论文 c o u l dd on e s tu s e dt h ee x i s t e n tr e c t a n g u l a rp i e c e sl a y o u tm e t h o d f i n a l l y , g o t i n t e r a c t i v eo p e r a t i o n s ，h a dat o t a lc o n t r o l ，a d d e dn e wc o m p o n e n t sa n da d j u s t e dt h e p o s i t i o no f e a c hp a r t s p e c i f i c a l l y , t h ep a p e rs t u d i e do nt h en e s t i n gs y s t e mo fm e t a lc o m p o n e n t sb a s e d o nt h er e m a i n d e rm a t e r i a l i th a dd e s i g n e dt h ei n t e r f a c eb e t w e e na u t o c a da n dt h e s y s t e mi t s e l f t h i si n t e r f a c ec o u l di n p u ta n do u t p u tt h ed x ff i l e s b a s e do nt h ed x f f i l e so fr e m a i n d e rm a t e r i a l sa n dc o m p o n e n t s ，t h es y s t e mg a v eas e m i - a u t o m a t i c n e s t i n go ft h er e c t a n g u l a re n v e l o p e t h e n ，p e o p l ec o u l dm o d i f yt h er e s u l t s ，a n d d i s p l a y i ti ns p e c i a lf o r m ，o u t p u ti t sd x ff i l e s t h i ss y s t e mi sv a l u a b l ef o rs m e sw h i c hm a c h i n i n gt h em e t a lc o m p o n e n t s k e yw o r d s ：n e s t i n gs y s t e m ；r e m a i n d e rm a t e r i a l ；i n t e r a c t i v en e s t i n g 掌t h i ss u b j e c t s u p p o r t e db yn a t i o n a ls c i e n c e & t e c h n o l o g yp i l l a rp r o g r a m ( n o 2 0 0 6 b a f o l a 4 1 ) i v 独刨性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论文 成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 指导教师签字： 论文作者签字： 6 9 2 0 0 9 年5 月3 0 日 第一章绪论 1 1 引言 第一章绪论 排样问题主要是指需要下料的工件在板料上的布置和开切方式。传统的排样 是由排样工人按照经验，手工将样片进行排列，排料的效率低、速度慢、劳动强 度大、差错率高，且效果不理想。而计算机辅助排样( c a n ，c o m p u t e r a i d e dn e s t i n g ) 是根据一定的优化原则，利用计算机图形学知识和相关的计算机技术来完成的。 它把传统的排样作业计算机化，把排样人员丰富的经验和计算机具有的快捷、方 便、灵活等特点结合起来，从而快速获得较高的材料利用率。 在国民经济的许多行业中，都会遇到材料的分割问题。计算机辅助排样的作 用就是生成高材料利用率的材料分割排样方案，因此，凡是需要进行材料分割的 行业，都可以应用c a n 技术，达到节约材料，降低成本的目的。 需要进行材料分割的行业有很多，如服装制造业、皮革制造业、家具制造业、 五金制造业、电子制造业等。 计算机辅助排样与传统手工排样相比，其优势在于： ( 1 ) 计算机排样可多次试排，并精确地计算各种排样方案的材料利用率，以寻找 最佳排样组合方式，从而获得较高的材料利用率，比手工排样提高3 一5 。同 时，由于计算机高度的精确性，不会漏排或重排，降低了差错率。 ( 2 ) 排样操作人员在计算机屏幕上进行排样，一方面可减轻手工排样时工人的劳 动强度；另一方面可通过换屏等操作纵观全局，以进行较好的排样布局。 ( 3 ) 计算机排样可大大减小手工排样时占用较大的厂房面积，同时排样的信息有 助于用来进行其他各方面的管理，如估计用料、核算成本等。 ( 4 ) 计算机排样生成的结果可以直接传输给加工设备。 随着先进制造技术的发展，实现下料排样的自动化已成为必然趋势。在下料 生产中采用下料优化排样技术，可以降低成本、提高材料利用率、改善排样工人 的劳动条件。下料优化排样由于具有高效性强、省时等优点，受到人们越来越多 的重视。因而对优化排样系统的开发和研究具有重要意义。 广东t 业人学硕l ：学位论文 1 2 背景与意义 1 2 1 五金专业镇的特点 在广东、江浙等沿海经济发达省份普遍存在一种专业镇经济模式，因产品一 般按区域行政镇划分而得名。在这种经济模式中，许多中4 , n 造企业通过集散效 应和分工效应组成企业集群，并形成专业镇市场。专业镇市场非常有利于中小企 业的发展。在专业镇的范围内，该行业的整个产业链非常完整，企业采购和销 售都十分便利。但是专业镇市场同时存在着很多问题，例如： ( 1 ) 企业规模小。以广东省五金专业镇制造企业集群内的中小制造企业为例，几 十人的企业普遍存在，在当前竞争环境下，这些企业必然面临着国际跨国 企业和国内企业的双重竞争压力。因企业观念陈旧，信息不畅，加工手段 落后，生产效率低，在全球竞争中处于劣势。 ( 2 ) 信息化基础差。因资金短缺的问题，在企业信息化方面投入不足，除部分企 业应用财务系统外，企业在生产管理、计算机辅助设计分析等系统的应用方 面基本不能满足需求，甚至对信息技术都不甚了解。 ( 3 ) 专业人才短缺。在人才方面，中d , n 造企业也面临严重短缺的问题，技术人 才的短缺导致企业技术创新能力不足，管理人才的短缺使企业缺乏管理创 新，企业发展受到制约。 综合以上几点，可以看出五金专业镇中小企业集群不具备在当前全球市场中 保持持续竞争力的能力。要实现五金中4 , n 造企业竞争力的提高，关键就是通过 企业信息化手段，提高企业设计能力和生产制造能力，实现企业管理流程的规范 化，促进企业核心竞争力的培养和提升。 1 2 2 基于余料的五金零件排样系统的意义 如前所述，专业镇企业主要是中小企业，它们在与供应商的交易活动中，由 于采购量小，缺少讨价还价的筹码，导致材料采购成本偏高，这对材料成本占总 成本比重较大的传统制造业( 如五金) 专业镇企业来说，无疑是个致命的痛处。 2 第一章绪论 为了改变这种现状，企业采用了以下几种办法。一是专业镇许多企业联合起来， 集中采购，增强与供应商讨价还价的能力，从而获取相对低廉的采购成本。二是 些加工小五金零件的企业购买大型企业加工后的余料作为自己的原材料，而这 些余料的价格远低于完整材料。三是提高企业自身的设计生产能力，在整个设计、 加工、管理过程中运用先进信息技术，尽量节省人力，物力，如运用c a x 技术、 d f x 技术、p d m 技术等。 在一般的五金生产中，材料费用是主要的生产成本，一般占总成本的6 0 9 6 到 8 0 。所以说提高材料利用率是降低五金零件生产成本的主要途径，而材料利用率 的高低主要取决于五金零件的排样。选择合理的排样方式和适当的搭边值，是提 高材料利用率、降低生产成本和保证工件质量的有效措施。 此时，计算机辅助排样技术的运用可以为解决该问题提供一个很好的选择。 因而，对五金专业镇中小型制造企业而言，针对基于余料的五金零件排样技术的 研究，显得更有实际意义。具体来说，有如下几个方面的意义： ( 1 ) 有效的提高材料利用率，这是运用计算机辅助排样技术的最基本，也是最主 要的目的。 ( 2 ) 减少了人力资源成本。特别是当前新劳动法的实施，再加上全球金融危 机的影响，企业经营总体上不景气。对劳动密集型的专业镇企业来说，减少 人力资源花费，无疑是提高了他们的竞争力，更容易让他们在当前的不利环 境下继续发展。 ( 3 ) 提高企业的信息化水平。计算机辅助排样系统的应用也是企业信息化的一个 方面，对提高企业的核心竞争力有一定帮助。 当然，除以上所述三条外，以余料作为生产原材料，本身就避免不必要的资 源浪费。 1 3 二维排样问题研究现状及相关算法 1 3 1 排样问题及排样系统的分类 排样问题可以分为三大类：一维下料、二维排样和三维布局口1 。现阶段的排 样系统主要有3 种：人机交互式排样系统，全自动智能排样系统，半自动排样系 3 广东t 业大学硕j j 学位论文 统h 1 。 ( 1 ) 人机交互式排样系统 交互式排样是指按照人机交互的方式由排样操作人员利用鼠标和键盘的输 入，根据他们的经验和一定的排样规则将待排样零件排放在合适位置的方法。同 时他们可以利用鼠标或键盘对该排样零件进行平移、旋转等操作。 ( 2 ) 全自动智能排样 全自动智能排样是指用计算机自动完成所有的排样工作。计算机按照用户预 先设定好的条件，利用一定的算法，以一定的规则进行排样位置的计算并输出排 样结果。该类型系统一般采用最新的模糊智能技术，并结合专家排样经验，能实 现全自动优化排样，高效自动调节，可以大大提高材料利用率。 ( 3 ) 半自动排样 半自动排样是介于交互式排样和全自动智能排样之间的一种排样方式。将待 排样零件做好相应的处理以后，导入相关的数据，系统首先自动进行初步的排放， 之后由操作者进行交互式操作，完成整个排样过程。该类系统充分的利用了排样 工人丰富的经验和计算机具有的快捷、方便、灵活等特点，具有很好的可操作性。 1 3 2 国内外研究现状 国外有关下料排样问题的研究起步比较早。于1 9 3 9 年就提出了一维下料问 题；2 0 世纪6 0 年代初，g i l m o r e 等发表了4 篇著名的文章，提出了一维下料方案 和二维排样优化问题；7 0 年代至今，众多学者针对排样问题的一个或几个方面提 出算法和解决方案。由于即使是矩形零件在一张板材上的排放问题也是n p 完全问 题陆3 ，加上实际的限制条件，问题会更加复杂，因此排样问题具有多样性特点， 至今没有通用的标准方法来解决。1 9 8 8 年，在e u r oi x t i m sx x v i i i 国际会议 上，专门成立了下料问题兴趣小组s i c u p ( s p e c i a li n t e r e s tg r o u po nc u t t i n ga n d p a c k i n gp r o b l e m ) 。 本文最主要是研究二维排样问题，以下简要介绍有关二维排样问题的研究动 态和进展。 2 0 世纪9 0 年代以前，对矩形件排样的求解以各种近似方法为主，如基于一维 装箱的f f d 算法、b f d 算法；基于最左最下原则的算法( b o t t o ml e f t ，b l ) 嘲；双 4 第一章绪论 向背包算法；相近图形组合算法、动态规划算法等。二维下料问题可以归结为以 零件排放状态为结点、以废料增加为权值的带权有向图的最短路径问题。 2 0 世纪9 0 年代后，随着智能优化算法( 如模拟退火算法、遗传算法、禁忌搜 索、神经网络等方法) 的日益成熟及其在t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) 问题、 空间分配、任务调度等组合优化问题方面的成功应用畸1 ，这些算法与排放算法相 结合被用于排样问题的求解。而将模拟退火算法( s i m u l a t e da n a e l i n g ，s a ) 、遗传 算法( g e n e t i ca l g o r i t h m ，g a ) 、随机搜索法( r a n d o ms e a r c h 尽s ) 、进化算法( n a i v e e v o l u t i o n ，n e ) 与不同排放算法结合也是方法之一h 1 。对不同问题实例的综合性能 评价的结果，有两点主要结论：( 1 ) 复合算法的结果优于单纯排样算法的结果，并 且排样算法效果越好，复合算法在同等条件下的效果也越好；( 2 ) 任何算法都有效 果不佳的问题实例，即对矩形件排样目前还没有完全有效的方法。 在对矩形件进行研究的同时，人们也对不规则零件的排样进行研究。对异形 件排样问题的求解方法可以分为三大类：( 1 ) 以矩形件排样为基础的算法；( 2 ) 侧 重于图形运算、基于规则的方法；( 3 ) 采用智能优化算法。这三类方法分别侧重于 异形件排样问题的不同侧面进行求解，相互联系，共同反映了排样问题的几何特 性与组合特性。 一些学者以矩形件排样算法为基础进行异形件排样1 。通过对零件的形状进 行推理，采用启发式规则的方法研究异形件排样，通常是将零件图形简化处理为 多边形( 如基于临界多边形的方法，通过零件间的图形运算、拼合推理的方法， 基于扫描碰撞的方法等。) 例如，采用轮廓边的匹配方法，按照一组基于零件面积、轮廓周长和复杂性 的性能参数进行排序，选择两个具有最高指标的零件，按照逆时针方向匹配每一 条边之后，以形成的最小包络矩形确定排放位置。这个过程不断重复，直到所有 的零件排放完毕。由于存在许多可匹配的边需要进行大量的测试，因此这种算法 计算量大，速度慢。然而通过固定一个零件不动，让另一个零件围绕着固定零件 的边移动一圈，形成临界多边形( n o f i tp o l y g o n ，n f p ) ，然后将n f p 用于异形件 排样则是很好的方法。 2 0 世纪9 0 年代后，一些学者将智能优化算法用于异形件排样问题睁1 。他们 采用s a 算法通过减少能量函数来确定图形的排样。能量函数表明了图形之间的 重叠程度，即图形之间的重叠面积之和与零件图形间重心距离的加权和。尽管模 广东t 业人学硕f ：学位论文 拟退火算法给出了令人满意的结果，但由于能量函数中的参数与待排放零件的形 状复杂程度相关，该方法需要的时间较长，而且有得到不可行解的可能。同时他 们也采用禁忌搜索方法来减少n p 完全问题的优化搜索空间。 国内对于排样问题的研究始于2 0 世纪8 0 年代，主要集中在高等院校和研究 所等。对冲裁件排样从2 0 世纪8 0 年代开始研究，以华中科技大学、上海交通大 学的工作最有代表性，主要有人机交互法、边界加密方法和不相交判别法等，借 助人机交互方式进行图形的旋转和平移以达到优化排样的目的n 引射。围绕着冲裁 件自动排样，采用将零件处理为多边形的方法或采用碰撞算法直接对零件进行排 样1 5 16 1 。 对矩形件排样的研究始于2 0 世纪9 0 年代，主要采用启发式算法，动态规划 法，整数规划方法，g a ，s a 算法进行求解。 近几年来，国内学者开始对异形件排样问题进行研究乜蝴1 。从算法看，主要 是采用一定规则将异形件处理为矩形，按矩形件排样方法进行排放；采用基于图 形运算的移动算法、碰撞算法；基于规则样图的方法、神经网络方法、基于学习 的遗传算法等进行求解。 上述的众多研究工作，都是在完好的板材上进行的。同时，限定板材的宽度 而不限长度或者是不限宽度也不限长度。辛征在论文中对有瑕疵的板材的排样优 化问题进行了初步的研究，他将板材的所有瑕疵初始化为矩形，将待排样的零件 也初始化为矩形，从而将该问题简化为矩形件排样问题啪1 。但是，只有当瑕疵较 小时，将瑕疵简化为矩形才可以被认为是合理的。瑕疵较大时，用矩形对瑕疵的 替代会产生较大的空隙，不能达到尽可能提高材料利用率的目的。在这种情况下， 需要进行其他相关的处理。比如，可以加入强大的交互式修改与调整功能模块， 利用人机交互方法，对具体的排样位置进行总体控制，在较大的间距处加入可以 排放的零件。 众多学者在研究排样算法的同时也开发了一些排样软件，从早期的交互排样 到自动排样，排样系统也在随着排样算法研究的深入而发展。华中科技大学最早 开发了冲裁件排样系统；曹炬推出了一维优化、矩形件排样、异形件排样的优化 排样系统软件等n 引。 目前排样问题己成为研究的一个热点。 6 第一章绪论 1 3 3 计算机辅助排样的算法分析 计算机辅助排样技术经过多年的发展，已经形成了很多应用于计算机辅助排 样的算法，大致可以归纳为如下几个大类：人机交互法、数学优化法、人工智能法、 启发式算法、几何计算算法、几何表达算法等。上述各类算法在解决排样问题时 将发挥不同的作用。 一般来说，它们存在如下图1 1 所示的层次关系。 图l l 排样算法层次图 f i g 1 - 1h i e r a r c h i c a lg r a p ho f l a y o u t a l g o r i t h m s ( 1 ) 数学优化法 数学优化法是利用线性规划、动态规划等数学优化方法来解决排样问题的方 法。它首先将排样问题抽象成某种数学优化模型，然后利用计算机计算该数学模 型而获得优化解。由于较复杂的排样问题并不能抽象出某种可以利用数学优化方 法直接计算，求解的数学优化模型，所以这类方法只能解决相对简单的排样问题， 如一维或一维半排样问题等，但对不规则零件的直接排样等复杂排样问题就无能 为力了。另外，利用线性规划或动态规划算法求解种类较多的零件和板料排样问 题时，求解方程所消耗的计算时间和空间将呈指数增长，计算效率不高。 ( 2 ) 人机交互法 人机交互法是利用计算机的图形显示能力，通过人机对话( 如用键盘或鼠标 广东- t 业大学硕l ：学位论文 等操作图形的旋转、平移，以及完成对图形的添加等操作) 完成排样。其本质是一 种手- r t j 样的计算机表达方法，不属于自动优化排样的范畴。目前，这种方法常 常作为计算机自动排样后，对优化结果进一步调整的手段。 人机交互法在算法层次图中处于第一层是因为它将人的能动性作为优化行为 的驱动器，负责所有零件的合理排放，而图形在计算机中的表达、旋转、移动等 是利用下层的算法来完成的。人机交互模块是排样系统的重要组成部分。 ( 3 ) 人工智能 人工智能法一般包括神经网络算法、模糊算法和遗传算法等，它们是目前解 决复杂非线性系统、控制和优化问题的主要工具。尽管这三种方法各不相同。但 实际上它们是紧密相关、互为补充和相互促进的。近年来的研究发现：神经网络 反映了大脑思维的高层次结构；模糊系统模仿低层次的大脑结构；遗传算法则是 对生物种群进化过程的模拟。目前，神经网络法和遗传算法在排样中已经有了一 定的应用。 人工智能法在算法层次图中处于第一层，是优化算法的驱动器，负责算法的 整体优化过程，运行中会调用下一层算法。它总是考虑全局的、整体的性能，一 般不涉及具体图形的组织问题，也不涉及具体图形的表达。 ( 4 ) 启发式算法 启发式算法在排样中负责待排样零件的组织工作，目的是形成排样图。零件 按照事先制定的启发式策略逐个地放人板料，最终形成排样图但这种策略一般不 是完备的，其对问题的搜索范围是局部的。 目前，对启发式算法的研究很多，如经典的b l ( b o t t o ml e f t ) 策略被广泛应用 于矩形零件排样，但它不能直接处理不规则零件，需要对零件进行特定的几何表 达( 如包络矩形等) 后才适用；边界进化法和拟合法是人工排样思想的模拟，虽 然规则表达复杂排样效果还不好，但有很好的发展前景。 启发式算法在算法层次图中处于第二层，一般还没有涉及对单个或几个图形 的几何计算问题( 如图形间的不相交处理、图形的旋转处理等) ，它主要负责确定 所有零件的排放次序与组织方式。 ( 5 ) 几何计算算法 几何计算算法在算法层次图中处于第三层，在解决排样问题时，负责实现零 件的移动、旋转等几何操作以及满足排样要求中的零件之间不重叠但靠接的要求 8 第一章绪论 等。这类算法属于图形学领域的研究内容，但它也是排样工作必须解决的问题， 并且通常占总排样时间的比重最大。目前在这方面的算法有：平行线一步平移法、 n f p ( n of i tp o l y g o n ) 算法、顶点碰撞法等。 ( 6 ) 几何表达算法 几何表达算法在算法层次图中处于第四层，是几何计算算法的基础，如采用 水平线的几何表达，往往对应于平行线一步平移法或者它的变形算法来计算图形 之间的判交计算等。目前在排样中常见的几何表达方法有如下几类：带曲线的原 始图形表示法、多边形表示法、包络法、栅格表示法、水平线组表示法等。 1 4 本文的研究内容 1 3 节前半部分介绍的几种排样系统类型，是根据排样过程中计算机的参与 程度来分类的，没有涉及到具体的排样约束条件。其中大部分的排样系统都是基 于完好的板材来进行排样工作的。并且一般仅限定板材的宽度，对长度不作限定。 但是对于“基于余料的排样系统 来说，板材并非是完好的，而且同时限定 板材的长度和宽度，对可排的区域有严格的限制。可以这样解释基于余料的排样， 即在“外轮廓为固定长宽的矩形，内边界未知”的余料上，排放尽可能多的待排 样零件，使余料的利用率尽可能大。现有的一些研究思路无法很好的解决该问题。 本文的主要工作就是对基于余料的五金零件排样系统展开研究并进行系统的 开发。叙述如下： ( 1 ) 基于余料的五金零件排样方法的研究 根据1 3 3 节所总结的有关排样算法的组成部分，为解决基于余料的排样问 题，本文将采用矩形包络法、碰撞判交检测算法、启发式b l 策略和人机交互式算 法。 本系统首先依据据“四块结构模式 将余料进行分区。然后用矩形包络法将 余料的内边界( 即已加工位置) 初始化为矩形，同时，将待排样的零件用其最小 包络矩形替代，将基于余料的排样问题转化为基于四个矩形区域的矩形件排样问 题。将该问题转化为矩形件排样问题后，虽然简化了计算，提高了排样效率，但 是，因为用矩形替代待排样零件和余料的内边界时，会产生很多空隙，利用此过 程得到的排样结果不是最优解，仅仅将排样进行到这一步，还达不到尽可能提高 9 广东t 业人学硕l j 学位论义 材料利用率的目的。因而系统提供了较完善的交互式修改模块，由排样人员根据 自己的经验，对半自动排样模块所得结果进行交互式修改，在总体上对零件的排 样位置进行控制，使排样的结果得到进一步的完善。 ( 2 ) 基于余料的五金零件排样系统的开发 系统将主要用于中小型五金零件生产企业，这就要求系统易于安装，使用方 便，因而选择v i s u a lb a s i c 6 0 作为开发工具，数据库采用a c c e s s 。系统将对余料 进行管理，识别其d x f 文件，并完成图形的导入，调用相应的算法进行排样工作， 得到最后的排样结果。 1 5 本章小结 本章首先介绍了计算机辅助排样技术的优点，以及五金专业镇在排样方面的 相关需求，提出了运用计算机辅助排样技术是满足该需求的一个选择。然后在参 考了大量文献的基础上讨论了国内外排样问题的研究现状，并对相关算法进行了 归纳总结。最后，提出了本文的研究内容及思路。 i o 第二章二维排样算法 2 1 二维排样问题 第二章二维排样算法 从数学上讲，排样问题属于非确定性多项式完备( n o n d e t e r m i n i s t i cp o l y n o m i a l c o m p l e t ep r o b l e m ，简记n r c ) l 苗q 题。这类问题是通过拟物方法，将优化布局转化 为弹性势能函数来描述，求解函数的极值，即获得最优布局1 。但是这类n p c 问 题至今仍无法找到其解析算法。 排样问题一般表述为：寻找平面最优布局的优化问题，即将一系列二维不规 则形状的零件，弓，最，只合理的排放在原料p 中，使原料的利用率最 高，并要满足下列约束条件： ( 1 ) e ，只互不重叠；f ，j = 1 , 2 ，l 且f j ( 2 ) 只必须放在p 内；i = 1 , 2 ，刀 ( 3 ) 满足一定的工艺要求。 因此排料问题可以归结为数学规划问题，也可以归结为以零件排放状态为起 点，以废料增加为权值的带权有向图中的最短路径问题畸3 。但是，由于约束条件 很难用可操作的数学公式表达，使得排料问题的求解不能套用现有的数学规划求 解算法。另外，图论中最短路径问题的己有算法，只对图的结构固定且清晰，一 个状态结点的后继结点个数有限的情况有效，对于不规则形状零件的排料，该方 法是不适用的。 在实际的排样工作中，需要排样的各种零件形状不一样，板材的规格也不一 样，而且，加工的方式以及设备的要求也对排样有影响。这就要求在排样研究之 前要对实际的情况进行抽象简化，作以下一些假设和规定： ( 1 ) 不考虑板材的厚度影响，假定零件厚度和板材一样，研究在板材个数不 限的情况下，排样所需零件的优化排样。 ( 2 ) 不考虑板材在下料中的应力影响及零件的轧制纤维方向的因素。 ( 3 ) 假定零件外形光滑，把零件外形的一些很小的凹槽除去，使零件外形尽 量简化。 广东t 业人学硕 ：学位论文 ( 4 ) 对生产实际中必须考虑的一些因素( 如切割的割距和冲压中的搭边值等) 统一通过一种权值对零件外形预处理来解决，排样直接考虑经过预处理 的零件。 优化排样是以提高材料的利用率作为目标函数，使材料利用率最大。材料利 用率是零件的实际面积s ，与原材料面积s 的百分比。即板材的利用率为 y j r r 5 2 1 1 0 0 ，其中n 为已排样零件的个数，s 为所选择的材料的面积， 墨为单个待排样零件的面积。 当然，排样区域可以是板材，也可以是条料等。而且根据排样方式的不同， 材料利用率的公式( 即目标优化函数) 可以进一步的进行转化。 2 - 2 二维排样算法 通常，我们所说的二维排样都是指“不规则零件无约束排样”，即加工方法为 可以任意走线、排样零件形状不规则情况下的排样问题。它是二维排样中最复杂 的问题，也是目前排样问题的研究热点。 如1 3 3 节所述，涉及不规则零件无约束排样问题的具体算法很多，人工智能 法、启发式算法、人机交互法等都有应用。特别是启发式算法和人机交互算法。 经典的b l ( b o t t o ml e f t ) 策略被广泛应用于矩形零件排样，但它不能直接处理 不规则零件，需要对零件进行特定的几何表达( 如包络矩形等) 后才适用。对于 不规则的零件的排样问题，如何表达“不规则零件”与排样算法的效率密切相关。 因此，需要对处于整个算法第四层的几何表达算法作必要的说明。 人机交互算法将人的能动性作为优化行为的驱动器，负责所有零件的合理排 放，而图形在计算机中的表达、旋转、移动等是利用下层的算法来完成的。人机 交互模块是排样系统的重要组成部分。 以下将详细描述上述的几种算法。 2 2 1b l 算法与矩形件排样 2 2 1 1b l 算法 第二章二维排样算法 b o t t o m l e f t ( b l ) 算法由j a c o s 在1 9 8 0 年提出。他提供了一种矩形件排放的策 略。矩形件排样是二维排样的基础。b l 算法将待排样的举行沿着板材的长度和 宽度进行放置，要求被放置矩形尽可能快的到达板材底部的同时尽可能快的到达 板材的左侧陋1 ，不用确定放置点的坐标，因而是研究比较多的方法之一。基于b l 策略的排样方法一直以来都是研究排样问题的基本策略1 。 b l 算法在本质上是一种启发式算法( h e u r i s t i ca l g o r i t h m ) 。启发式算法可以 按照如下的描述来定义：该算法是一个基于直观或经验构造的算法，在可接受的 花费( 指计算时间，占用空间等) 下给出待解决组合优化问题每个实例的一个可行 解，该可行解与最优解的偏离程度不一定事先可以预计。 基于排样的启发式搜索算法的启发信息确定的依据是模仿人工排样的过程。 通过对人工排样过程的分析对比和总结。我们可以确定以下信息： 对形状特征对的可吻合性和吻合程度进行判断，比较，实现凹凸互补和对 排样零件的挑选； 对待排样零件的面积和复杂程度进行估计后排序，排样运算时先找大的零 件，与人工排样处理方法一致； 利用对排放方向的限制，实现优先从原材料的一侧开始摆放； 确定“排样质量好”的衡量标准，在试排后进行判断，符合要求则确认为 最终摆放，否则变换摆放位置或选择其它零件重新摆放。 关于b o t t o m l e f t 算法，说明如下。 ( 1 ) b l 条件 矩形正交排样的解空间是无限的，因为在一个排样图中任一个矩形排样位置 的微小变化就可得到一个新的排样图。为有效地减少解的数量，引入使排样图规 格化的所谓b l 条件( b o t t o m l e f tc o n d i t i o n ) ，即若排样图中任何一个矩形件在不干 涉或不超出板材边界的情况下，均不能向下、向左移动，则满足b l 条件。引入 了b l 条件以后，矩形件正交排样问题的解的个数变为有限个，从而大大地减少 了解的数量口1 。 ( 2 ) b l 策略的步骤 从一般意义上来说，在矩形放置时每次都会引起排放模式的变化，而从图形 拓扑学上来看，它们有着类似的排放模式，b l 算法就是一种利用相同的排放模 式来处理每次矩形放置位置及过程的算法。它要求，当前要放置的矩形从板材的 广东t 业大学硕 ：学位论文 右上角进入，以尽可能快的速度到达容器底部的同时，还要尽可能快的到达容器 的左侧。如果用r 来表示每一个放置矩形，用r 的排列加上序号表示矩形排列次 序。r = r ( 1 ) ，月( 2 ) ，尺( 3 ) ，r ( n ) ，则算法步骤可以描述如下： 步骤( 1 ) ：放置r o ) 到板材的左下角； 步骤( i ) ：移动r ( o ，从板材的右上角开始，尽可能快的到达底部，到达底 部以后尽可能快的到达左侧，如图2 1 所示。图中a b c d 为矩形区域，1 、2 、3 、 4 分别是待排样的矩形。 b a c d 图2 - 1b l 算法步骤 f i g 2 1t h es t e p so fb la l g o r i t h m 2 2 1 2 矩形件优化排样 矩形件排样不仅可以解决矩形零件的排样，同时也是解决二维不规则零件排 样的重要方法。从数学计算复杂性理论上说，该类问题属于n p 完全问题，计算复 杂度很高，是目前最复杂、最困难的问题之一，至今还没有找到求取最优解的多 项式时间算法。 矩形件排样是指在矩形的板材上，要排放多种不同类型的矩形零件，每种矩 形零件有多个，如何在这些矩形零件既不相互重叠，也不超出板材范围的条件下， 尽可能多地在板材上排下这些矩形零件，以使材料被最大限度的利用，达到降低 成本减少浪费的目的。 设排样所用的板材的长为l ，宽为b ( l b ) ，板材的数量足以排下所有要排 的矩形件。所有要排的矩形件共有t 种，第f 种矩形的个数为拧；长度为，宽度为 r b , 0 i 丁) 。则全部要排的矩形件总数为：n = 刀，。 1 4 第二章二维排样算泫 基本目标是：使排样所用的板材数尽可能的少，尽可能的提高材料的利用率。 排样规则为b l 规则：每一个矩形零件可按板材的长或宽进行正排( 正排即 矩形零件的长或宽总是与板材的长或宽平行) ，从板材的最左下角开始排至板材的 右上角结束。 排样的基本约束条件为：矩形件之间不能有相互重叠的区域，并且矩形件不 能有排出板材之外的部分。 排样坐标系的选取：以板材的左下角点为排样坐标系原点( 0 ，o ) ，且为排样起 点，排样过程中不得有任何排样点落在此点左侧；板材的右上角点为( l ，b ) ，且排