（机械制造及其自动化专业论文）面向多原料多零件的大规模优化下料技术研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 可持续发展是当今世界发展的主题，资源的优化利用是具体要求。制造业量大 面广，在创造社会财富的同时，也造成了巨大的资源浪费。优化下料是制造业中 的一项基础技术，也是控制资源浪费的重要环节。大规模下料是其中的一类特殊 问题，由于其较多的原料和零件种类数，使得目前的诸多优化算法陷入性能危机， 造成巨大的资源浪费。鉴于解决大规模下料问题的重要意义，本文针对具有多种 原料的下料问题( 多原料下料问题) 、具有多种零件的下料问题( 多零件下料问题) 和既具有多种原料又具有多种零件的下料问题( 多原料多零件下料问题) 分别展 开研究。 对于多原料下料问题，一般的算法难以实现对所有原料组合方式进行探索，但 又缺乏有效的原料选择理论或技术，故而往往难以得到原料利用的更优解。为此， 提出迭代结构的筛选法、交叉组合法和最速下降法。这三种方法从不同的侧面提 出假设，并制定规则，提高了探索的精确性，有利于获得更优的原料组合，进而 达到提商材料利用率的目的。阐述了它们的前提假设、基本思想、实现流程和算 法实现等，并分析了它们的求解效果。 针对诸多优化算法在处理多零件下料问题时易于陷入局部最优解和时间效率 低下的问题，提出一类基于下料特征的分组优化方法。该类方法通过考察下料的 相关特征将原大规模问题拆分为若干小规模问题，各小规模问题优化后的结果合 并即为原问题的下料方案。在分析该类方法的可行性的基础上，建立了分组优化 的数学模型，阐述了该类方法的结构体系，指出优化高效性、分组宏观性、分组 闭环性和结构开放性是该类方法的重要特征，具体研究了分组个数确定、分组策 略、并列优化技术和补偿策略等构成技术。在具体上，利用零件相似性特征，提 出基于零件相似性特征的分组优化方法，阐述了该方法的实现流程，并研究了其 关键技术。 对于既具有较多原料又具有较多零件的大规模下料问题，分析了大规模下料的 系统求解结构，给出了路径控制点的定义及评价形式，提出了优化路径的n 段控 制模式，并将对优化路径的控制问题总结为o - 1 目标规模问题，建立了该0 - 1 目标 规划的数学模型，简要介绍了目标规划的求解方法。通过优化路径控制，可以实 现多方面技术的协调运作，达到综合最优的求解效果。 为了检验大规模下料技术的有效性，针对多原料和多零件的下料问题分别采用 交叉组合法和基于零件相似性特征的分组优化方法进行了若干实验，实验结果表 明：最速下降法能够较快地找到目标原料组合，可以稳健地提高材料利用率；相 重庆人学硕士学位论文中文摘要 对于不分组优化，基于零件相似性特征的分组优化方法可以实现对原零件集合的 较优拆分，在提高时间效率的同时，能够维持和提高材料利用率。进而证明了原 料选择技术和基于下料特征的分组优化方法的有效性。 最后，将本文提出的部分大规模下料技术对“建筑金属结构计算机辅助设计与 生产管理集成系统”( 国家8 6 3 c 1 m s 目标产品) 中的优化下料子系统进行升级， 提高了该软件的优化性能和处理问题的能力。目前，升级后的优化下料系统已成 功应用于数百家企业，取得了较好的应用效果。 关键词：下料；大规模；下料特征；分组；优化路径控制 u 重庆大学硕士学位论文英文摘要 a b s t r a c t s u s t a i n a b l ed e v e l o p m e n ti st h es u b j e c ti nc u n e n tw o r l d ，a n dt h eo p t i m i z a t i o no f r e s o u r c eu t i l i z a t i o ni sad e t a i l e dr e q u i r e m e n t m a n u f a c t u r i n gi n d u s t r yi n v o l v e sm a n y a r e a s ，a n dl e a d st ov a s tr e s o u r c ew a s t ew h i l et u r n so u tp r o d u c t sa n dc r e a t e sw e a l t h o p t i m i z e dc u t t i n gi so n eo fb a s i ct e c h n o l o g i e si nm a n u f a c t u r i n gi n d u s t r y , w h i c hi sa l s o n i li m p o r t a n tr i n go fw a s t e c o n t r 0 1 a sas p e c i a lt y p eo fc u r i n gs t o c kp r o b l e m ( c s p ) ， l a r g e - s c a l ec u t t i n gs t o c kp r o b l e m ( l s c s p ) t r a p sm o s to ft h eo p t i m i z a t i o na l g o r i t h m s a v a i l a b l ea tp r e s e n t a sar e s u l t ，l a r g eq u a n t i t i e so fr e s o u r c e sa r ew a s t e d i no r d e rt o s o l v et h el s c s p ，t h i sd i s s e r t a t i o nw i l ld os o m er e s e a r c hw o r ki nt h r e ed i f f e r e n t d i r e c t i o n s ，i n c l u d i n gc s pw i t hm a s sm a t e r i a l ( m m c s p ) ，c s p 诵t l li d _ a s sp a r t s ( m p c s p ) a n dc s pw i t hb o t hm a s sm a t e r i a la n dp a r t s ( m m p c s p ) w h e nd e a l i n gw i t hm m c s p ，g e n e r a la l g o r i t h m sc a nh a r d l yp r o b ei n t oa l lt h er a w m a t e r i a lc o m b i n a t i o nm e t h o d s ，f u r t h e rm o r e ，t l i e ya r el a c ko fe f f e c t i v et h e o r i e sa n d t e c h n o l o g i e so nm a t e r i a lc h o s e n , h e n c eu s u a l l yl e a d st of a i lo no p t i m a ls o l u t i o no n m a t e r i a lu t i l i z a t i o n t h u s ，t h r e em e t h o d sf o rs o l v i n gt h em m c s pa r e p r o p o s e d ： s e l e c t i o nm e t h o d ，e x c h a n g e - c o m b i n a t i o nm e t h o da n ds t e e p e dd e s c e n tm e t h o d t h e s e t h r e em e t h o d sp r o p o s eh y p o t h e s i si nd i f f e r e n tw a y sa n dm a k ec o r r e s p o n d i n g r u l e s b y i m p r o v i n gt h ea c c u r a c yo fs e a r c h i n gu s e f u lm a t e r i a lc o m b i n a t i o n , m o r ce f f i c i e n t c o m b i n a t i o n sa r eg o ta n dt h em a t e r i a lu t i l i z a t i o nr a t ei s i m p r o v e d t h ep r e m i s e h y p o t h e s i s ，b a s i ct h i n k i n g , w o r kf l o wa n di m p l e m e n t a t i o no fa l g o r i t h mo ft h et h r e e m e t h o da t ee x p o u n d e di nt h ed i s s e r t a t i o n an o vc l a s so f g r o u p i n go p t i m i z a t i o nm e t h o db a s e do nt h ec u t t i n gc h a r a c t e r i s t i c s ( c c g o m ) i sp r o p o s e d w h i l em o s to ft h eo p t i m i z a t i o n a l g o r i s m s a r el o wi n t i m e - e f f i c i e n c ya n da r el i k e l yt of a l li n t ol o c a lo p t i m u mw h e nf a c e dw i t l im p c s et h e n e wm e t h o dd i v i d et h em p c s pi n t os e v e r a ls m a l l s c a l ec s p s ，a n dt h ec o m b i n a t i o no f a l lr e s u l t so fc s p si sj u s tt h er e s u l to fm p c s ea f t e ra n a l y z i n gt h ef e a s i b i l i t yo f c c g o m ，t h em a t h e m a t i c a lm o d e lo fg r o u p i n go p t i m i z a t i o ni se s t a b l i s h e d , t h es t r u c t u r e o ft h ec c g o mw a se x p o u n d e d ，a n dt h ed i s t i n c t i v ef e a t u r e si n c l u d i n go p e ns t r u c t u r e , c l o s e d l o o pn a t u r e ，a n dm a c r o s c o p i cg r o u p i n gw e r ee m p h a s i z e d t h e ns o m ed e t a i l e d t e c h n o l o g i e s ，s u c ha st h et e c h n o l o g yf o rd e c i d i n gt h em t m b e ro fg r o u p s ，g r o u p i n g s t r a t e g y , p a r a l l e lo p t i m i z a t i o na n dc o m p e n s a t es t r a t e g ya r es t u d i e d a sad e t a i l e d c c g o m ，g r o u p i n go p t i m i z a t i o nm e t h o db a s e do nt h es i m i l a r i t yo fp a r t s ( s g o m ) i s 1 1 1 重庆大学硕士学位论文 英文摘要 p r e s e n t e d ，a n dt h ew o r kf l o wa n ds o m e c r i t i c a lt e c h n o l o g i e sa r ee x p o u n d e dt o o t od e a lw i t hm m p c s p , as y s t e m a t i cs o l u t i o ns t r u c t u r ei sa n a l y z e d ，a n dan p h a s e p a t hc o n t r o lm o d ei sp r o p o s e d t h ep a t hc o n t r o lp r o b l e mh e r ei ss u m m a r i z e da sa 0 - i g o a lp r o g r a m m i n gp r o b l e m ，w h o s em a t h e m a t i c a lm o d e li se s t a b l i s h e d ，a n dt h es o l u t i o n m e t h o d sa l ei n t r o d u c e di nb r i e f t h r o u g ht h ep a t hc o n t r o l ，d i f f e r e n tt e c h n o l o g i e si n d i f f e r e n ta s p e c t sc a nh a r m o n i z ew e l l ，t h u sac o m p r e h e n s i v eo p t i m a le f f e c tc a l lb e a c h i e v e d s e v e r a le x p e r i m e n t su s i n gt h es t e e p e dd e s c e n tm e t h o da n dt h es g o ma r ec a r r i e d o u tt op r o v et h e i rv a l i d i t y t h ee x p e r i m e n tr e s u l t si n d i c a t et h a tt h es t e e p e dd e s c e n t m e t h o de a r lf i n dab e t t e rm a t c 耐a lc o m b i n a t i o nr a p i d l y , a n dc a ni m p r o v et h em a t e r i a l u t i l i z a t i o nr a t es t a b l y c o m p a r e dw i l l lt h eg e n e r a lo p t i m i z a t i o na l g o r i t h m s t h es g o mi s h i 曲l ye f f e c t i v eb o t hi nt i m e - e f f i c i e n c ya n du t i l i z a t i o nr a t i oo fm a t e r i a l sw h e ns o l v i n g m p c s et h u s ，t oac e r t a i ne x t e n t , t h ev a l i d i t yo ft h et e c h n o l o g i e sp r o p o s e di nt h e d i s s e r t a t i o ni sp r o v e d a tl a s t ，t h et e c h n o l o g i e sp r o p o s e di nt h ed i s s e r t a t i o nw e r eu s e dt ou p g r a d et h e o p t i m i z a t i o nc u t t i n gs u b s y s t e m i n t h e c o m p u t e ra i d e dd e s i g na n dp r o d u c t i o n m a n a g e m e n ti n t e g r a t es y s t e m ( c a d p m ) ”n o w , t h en e wu p g r a d e do p t i m i z a t i o n c u t t i n gs u b s y s t e mp e r f o r m a n c e sw e l la n da r ea p p l i e di nh u n d r e d so f e n t e r p r i s e s k e y w o r d s ：c u t t i n gs t o c k , l a r g e - s c a l e ，c u t t i n gc h a r a c t e r i s t i c s ，g r o u p i n g , o p t i m i z a t i o np a t h c o n t r o l i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 锝的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庆太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：彳妻l 毪 签字日期；沙。7 年月1 日 学位论文版权使用授权书 本学位论文作者完全了解重庆太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重废太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( ) 。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名：甲壶f 也 导师签名： 签字日期：沙吖年6 月i e l 签字日期：叮年钼l e l 重庆大学硕士学位论文 1 绪论 1 绪论 1 1 论文的选题背景和意义 1 1 1 课题的选题背景 制造业因其量大面广而在国民经济活动中发挥了十分重要的作用。然而，制 造业一方面消耗着大量人类社会有限的资源，另一方面也造成较大的环境污染【l 】。 开源节流是解决有限资源的辩证方法，但无论新的替代资源是否出现，对现有资 源的优化利用始终具有巨大价值。优化利用资源可以减少原料消耗，降低对环境 的负面影响，这是符合社会可持续发展的时代主题的。 优化下料作为资源优化利用的重要组成部分，在机械、钢铁、船舶、车辆、 建筑、造纸、家具、玻璃、皮革等制造业领域中有广泛的应用，因此其技术水平 的高低对社会的影响十分巨大。早在上个世纪3 0 、4 0 年代，国外部分学者已经 意识到下料技术潜在的巨大社会价值，并开始利用运筹学中的相关技术方法对它 展开研究，我国的科研人员也在上世纪7 0 、8 0 年代开始了该领域的研究。经过几 十年国内外学者的不懈努力，优化下料领域中的新成果不断涌现，并逐步走向应 用。然而，优化下料问题是具有最高计算复杂性的n p c o m p l e t e 难题1 2 ，可行的 组合方案的数量巨大，以目前的计算方法和硬件水平根本无法找到全局最优解， 只能不断地构造规则，花尽量少的代价获得更优的结果。 在人们积极探索更优的求解方法的同时，制造加工行业正发生深刻而剧烈的 变化。激烈的市场竞争时刻威胁着企业的生命，企业一方面要积极提高业务量， 提升企业柔性以适应市场变化的节奏；另一方面要努力控制成本，提高效率。如 此，摆在企业面前的问题便是，如何低成本、高效率地处理大量的、形式多样的 任务。相应的，对于下料部门则是面对规模远远超过以往的下料问题，却有着苛 刻的资源限制。但令人担忧的是，目前的下料技术在处理这类大规模问题时性能 十分的低劣。固然采购高性能计算机，铺设网络等措施能解燃眉之急，但下料技 术内部的性能问题始终是瓶颈。基于此，本文针对大规模下料问题展开技术研究 以期提高求解效果。 1 1 2 课题的研究意义 大规模问题主要指具有较多的原料种类、较多的零件种类或者二者兼有的下 料问题。这类问题由于原料或零件种类的增多，使得可能的下料方式呈现爆炸性 的增长。面对这种情况，目前诸多优化算法一方面时间效率变得十分低下，另外 一方面算法更容易陷入局部最优解【州1 1 ，而造成更大的资源浪费。着对此类问题无 有效解决办法，将明显有违企业提高竞争力的需要，也给社会带来了资源浪费与 重庆大学硕士学位论文1 绪论 环境问题。因此，越来越突显的大规模下料问题变得亟待解决，其实际意义也变 得十分重要。 在科技高速发展的今天，不同领域内的研究成果，也许会对不同领域内的新 问题的解决有着意想不到的推动作用。对于大规模下料问题，计算机性能的不断 提高，网络的普遍应用，数学、人工智能等领域的新进展，还有系统科学、复杂 性科学内的新方法论的提出，都有可能促进其解决。多方技术以及对下料问题内 部的深入剖析，都有可能在大规模下料问题内得到综合。如此，大规模下料技术 的研究在学术上的意义也可见一斑了。 综上所述，由于对大规模下料问题的有效解决将会提高企业竞争力，更能满 足社会需求，节约社会资源和减少环境问题，而具有巨大的实际意义。又因为它 将加深对下料问题的本质的认识并促进多学科技术的综合，而具有重大的学术价 值。 1 2 优化下料的研究现状与共性特征 1 2 1 优化下科的研究现状 优化下料是指在一定的工艺条件限制下，将一批尺寸有别的零件互不重叠地、 合理地排布到具有一定尺寸的原料之中，使得材料利用率尽可能高【l “。优化下料 应用范围非常广泛，在工程应用领域中，如棒材下料、冲裁件下料、玻璃切割、报刊 排版、家具下料、服装裁剪、皮革裁剪、造船、车辆和发电设备生产中都存在大 量的下科问题。下料问题可以分为一维下料、二维下料和三维布局等三大类。 k a n t o r o v i c h t 3 1 于1 9 3 9 年就提出了一维下料问题；2 0 世纪6 0 年代初，g i l m o r e 1 4 - 1 7 】 等发表了4 篇著名的文章，提出了一维下料方案和二维下料优化问题；在2 0 世纪 8 0 年代中期，研究人员对三维布局展开了研究。然而，从计算复杂性理论上，优化 下料问题是具有最高复杂性的n p 完全问题，且实际情况复杂多样，因此下料问题 至今尚无有效的求解方法。从下料问题提出至今，众多学者针对下料闯题不同方 面，不同层次展开了大量的研究，大致可以分为如下几个阶段。 传统方法阶段。该阶段的方法特点是采用典型的运筹学方法进行求解。从数学 模型看，下料问题往往是一个整数规划问题。常用的优化方法是将整数变量进行 松弛，视为线性规划，采用单纯形方法求解，然后对结果进行圆整。但这样做并 不能保证缛到最优解，而且圆整之后会产生一种或几种零件过量生产或不足量， 需要对其进一步处理；或采用针对整数规划求解的分支定界法与割平面求解，但 这只在变量数目较少时适用。当零件的尺寸相对于原材料尺寸较小且种类数量较 多时，零件的组合搭配数目增大，列生成问题从组合角度看是一个背包问题，背 包问题也是一个n p 完全问题【2 】。因此，这一阶段的方法的优化效果并不理想，新 2 重庆大学硕士学位论文 1 绪论 方法的提出往往以之为原理性方法或者参照标准。 近似算法阶段。近似算法主要思路是从组合优化的角度将下料问题当作装箱问 题，利用装箱问题的相关规则来构造近似的下料算法【l 引。对于一维下料，2 0 世纪 7 0 8 0 年代研究人员提出多种近似算法，如首次适应降序算法( f i r s tf i t d e c r e a s i n g ，f f d ) 、下次适应降序算法( n e x tf i td e c r e a s i n g ，n f d ) 、最优适应降序 算法( b e s tf i td e c r e a s i n g ，b f d ) 等。对于二维矩形件下料，2 0 世纪9 0 年代以前的 下料算法主要处于该阶段1 9 1 ，如基于一维装箱的f f d 算法、b f d 算法、基于最 左最下原则的算法( 8 0 t t o ml e f t ，b l ) 、双向背包算法、相近图形组合算法、动态规 划算法等。 启发式方法阶段。考虑到实际下料问题的约束条件往往较多、人们也积累了较 多的感性知识，因此提出易于融合各种限制条件和具体目标的启发式方法。这类 方法的特性使得它们在实际生产下料中起着重要的作用。文献 2 0 1 结合人工智能与 运筹学方法，提出了基于知识求解矩形件、异形件下料问题的系统概念模型。文 献 2 1 1 采用来自有经验的下料师的启发式规则以及冲孔、剪床下料等限制条件存储 在知识库中的方式，指导模型生成图案组合。 智能优化算法阶段。2 0 世纪9 0 年代后，随着智能优化算法( 如模拟退火算法、 遗传算法、禁忌搜索、神经网络、蚁群算法等方法) 的日益成熟及其在t s p ( 旅行 商) 问题、空间分配、任务调度等组合优化问题方面的成功应用，这些方法逐步楷 书与排放算法相结合被用于下料问题的求解 5 , 7 , 9 - 1 1 , 2 2 - 2 5 1 。目前，关于智能算法在优 化下料领域中的应用正在被广泛研究。 综合化方法阶段。研究人员意识到纯粹依靠提出某种算法来有效解决所有的下 料问题的可能性十分小，因此希望通过综合多种方法和技术来更好地解决实际问 题，主要表现在三个方面：多算法的复合化。一方面，结合不同算法的优点提 出新的复合算法，如文献【2 3 】提出将模拟退火算法和遗传算法相结合来高效逼近全 局最优解的新算法；另一方面，在某一求解体系内采用多种算法并行运算的模式， 文献【3 提出了基于a s p 模式的多软件协同优化下料方法，探讨了如何利用网络实 现多方法的综合。多技术手段的综合。典型的是利用网络技术进行分布式下料 1 2 5 1 。下料与其它生产环节的联合，如优化下料方法与数控切割工艺相结合【2 6 】。 综合化方法目前还处于起步阶段，形成了当前的研究趋势。 综上所述，由于优化下科问题的n p 复杂性，无法确定找到最优解，所以，国 内外的众多学者针对优化下料的不同层次、不同侧面和不同的特征展开了大量的 研究。目前该领域的研究方向正朝着综合化、集成化的方向发展。 1 2 2 优化下料的共性特征 如上文优化下料技术研究现状所述，经历几十年的研究，优化下料技术有了较 重庆大学硕士学位论文1 绪论 大的发展，学者们针对不同的下料种类，从不同侧面提出了很多的优化下料方法， 形成了百花齐放的格局。然而，时至今日，并没有一种理论能必然得到全局最优 解，也没有一种算法能必定有效地求解形式各样的下料问题。究其根源，当然首 推优化下料问题的n p 复杂性，此外，由此衍生出来的和其它部分特征同样广泛地 影响了优化下料技术，或者它们也被几乎所有的下料技术所证明，这些共性包括： n p 复杂性。这是优化下料问题最基本的特征，是形成当今优化技术格局的 根源。 形式多样性。优化下料种类包括一维、二维和三维这三大种类，各大类之 中还有繁杂的小类划分，即使任意一小类问题中不同的原料和零件组合方式都让 一般的优化方法难以全面应付。 局部最优性。目前的优化算法都是局部最优算法，即使有些算法虽具有全 局搜索能力，如遗传算法，但限于时间效率等实际条件而只能以局部最优解近似 代替全局最优解。这一特征还包括了对原料组合选择的局部最优性。 单一算法求解不稳定性。无论是何种算法，都有其比较适合的求解类型， 但同时也有其效果不佳的问题实例，诸多的启发式算法在这一点上尤为明显。 时间效率与材料利用率在算法层面上的矛盾性。在有限的时间内，算法只 能完成一定量的搜索；如果要想提高材料利用率，必须扩大搜索范围，这需要时 间的保证。 大规模下料问题作为优化下料中的一类特殊问题，自然将具备上述共性特征， 对这些共性特征的把握与利用是本文解决问题的一个重要思路。因此，优化下料 的共性是本文提出的方法的理论基础。 1 3 本文的主要工作 1 3 1 本文研究工作的原则 由于大规模下料问题的普遍存在，且目前尚不具备定形的理论方法，所以在 对优化下料具有一定认识之后，在展开对此问题的研究工作之前，预先制定如下 四条研究原则： 基础性原则：本文的研究工作所希望的是，在大规模下料这样一类特殊的 优化下料问题，针对优化下料的共性特征，提出基础性的解决方法，将对不同种 类的下料问题具有普遍有效性。 综合性原则：本文提出方法将尽量综合多方面的技术，并且视诸多的优化 算法作为不可再分的原子性技术，即注重的是一种宏观策略的开发。所提出的策 略将独立于优化种类和优化算法。 定性分析与定量分析相结合的原则：鉴于优化下料问题的n p 复杂性，本 4 重庆大学硕士学位论文 1 绪论 研究重视定量分析方法，但不回避一些有价值但并未被证明的经验甚至是主观感 受，当然它们的有效性应当被实验证明。 整体最优原则：大规模下料问题涉及较多的资源，而本文提出方法多为综 合性的、策略性的方法，故而应当以整体最优为目标。 1 3 2 本文研究的目的 在整体上，本文所提出的方法在处理大规模下料问题时，应当具备节省下料时 间，维持和提高材料利用率的性能。在具体上，本文针对多原料下料问题、多零 件下料问题和多原料多零件下料问题等三类大规模下料问题，需要达到如下几点 具体目标： 对于多原料下料问题，考虑到对原料组合选择的局部最优性，研究部分方 法能够无需对所有的原料组合进行探索，而按一定的规则提高对目标原料组合的 探索精度。 对于多零件问题，基于“分而治之”的思想，研究可以高质量拆分大规模零 件的技术。通过拆分，达到分散解空间却不降低材料利用率的目的。 对于兼有多原料和多零件的下料问题，研究宏观策略可以使得在一定的资 源限制下实现多方技术协调工作，达到整体更优的下料效果。 1 3 3 研究内容和论文结构 在研究原则的指导下，根据研究目的，本文提出筛选法、交叉组合法和最速 下降法来对多原料下料问题进行原料组合的选择：提出基于下料特征的分组优化 方法来解决多零件下料问题；研究优化路径控制技术来使多方技术协调工作以解 决多原料和多零件的下料问题。本文各章节的内容如下： 第1 章：绪论。主要介绍本研究课题的研究背景和意义，综述优化下料的研 究现状，分析优化下料的共性，制定本文的主要工作等。 第2 章：多原料下料问题中的原料选择技术研究。在对多原料下料问题介绍 的基础上，提出筛选法、交叉组合法和最速下降法等三类原料选择技术，对它们 的基本思路、算法流程和运行效果等进行介绍和分析。 第3 章：多零件下料问题中的零件分组优化技术研究。在对多零件下料问题 介绍的基础上，提出一类基于下料特征的分组优化方法，对该类方法的结构、特 征、实现技术等予以介绍和研究。并着重介绍该类方法中的一种具体方法甚 于零件相似特征的分组优化方法。 第4 章：多原料多零件下料问题的优化路径控制。分析多原料多零件下料的 系统求解结构，探讨在一定的整体目标下，如何实现多方面技术的协调和优化路 径的控制。 第5 章：实验、结果分析及应用。集中地对部分技术进行实验验证，并说明 5 重庆大学硕士学位论文 1 绪论 这些技术的应用情况。 第6 章：结论。对全文的研究工作进行总结，并且对未来的工作提出展望。 1 4 本章小结 本章首先介绍了本研究课题的背景和意义，接着对优化下料技术的研究现状 进行了综述和分析，总结了优化下料的共性特点，并阐述了本论文研究工作的研 究原则、目的和主要内容。 6 重庆大学硕士学位论文 2 多原料下料问题中的原料选择技术研究 2 多原料下料问题中的原料选择技术研究 2 1 多原料下料问题概述 多原料下料问题是指含有较多原料种类的下料问题。相对于同一批下料零件， 如果提供较多的原料种类，零件的排列组合方式必然增加，获得更高的材料利用 率的可能性也就越大。这种适当增加原料以提高材料利用率的措施在实际生产加 工活动中也常常被使用。此外，还有另外一种导致出现多原料问题的情况，那就 是余料下料问题。余料是本次下料之前所留下的较小尺寸的料头，并且有数量限 制，对它们注重的是再次利用，能否更优利用则在其次。故而对一般的余料下料 不必要耗费过多的时间效率，可以采用相对简单的处理办法，如贪婪法。但这种 情况并不是此处要研究的情形，此处研究的是指原料数量没有限制，以获得更高 材料利用率为目标的多原料下料问题。因此，不能简单地使用对待余料的方法来 处理，而应当考虑更优普遍效果的方法。 增加原料种类，虽然提高了获得更高材料利用率的可能性，但同样也带来了不 利因素。最直接受影响的就是时间效率问题。原料种类数增加必然导致求解时间 的增加，因为在构造可行方案时，可供选择的范围随原料的增加而增多，当然， 这部分时间的增多可以近似认为是线性的。间接受影响的就是材料利用率。由于 没有任何一种算法能必然找到最优解，也就意味着没有任何一种算法可以肯定找 到最优的原料组合。与之对应的，在实际下料过程中，经常会遇到较多原料的求 解效果反倒不如较少原料的求解效果的情况。所以，限于现在方法上的不足，随 着原料种类的增加，材料利用率未必会理想地增加。如果采用一定的方法对原料 组合进行合理有效地选择，材料利用率会得到一定的提高。不过这部分工作又增 加了时间负担，且所需时间与所采用的方法有很大的关系。所以，在探索有价值 的原料选择方法时，必然要兼顾时间效率和材料利用率。 对于原料组合效果的预测，目前并没有相关的理论予以支持，也就是并不存在 简洁、高效的方法能够脱离优化算法而直接定位到目标原料组合。直接的思路就 是穷举所有的原料组合，并对它们进行分别优化，再比较组合的优化效果并选择 最优组合。但是由于每一个组合就代表了一次优化，所以穷举所有原料组合后择 优的思路往往也只能用于原料种类数相对较少的情况，即使原料只有5 种时，其 可能组合已有3 1 种之多，这样的效率代价在实际情况下是难以承受的。更为不利 的情况是，如果零件种类数同样较多，这种方法简直是无法实现对原料组合的选 择。在一些被广泛应用的优化下料软件中，为了防止出现上述明显的不足，但又 限于时间效率的约束，故而只好退求其次，如只考虑其中的单一材料、两两组合 7 重庆大学硕士学位论文 2 多原料下料问题中的原料选择技术研究 等少数原料组合情况。即便如此，这种不完全的穷举搜索由于搜索方向缺乏指导， 往往徒劳无功。因此，对于多原料下料问题，探究可以更快地定位到目标组合的 原料选择技术将对缓解优化下料的局部最优性具有一定的意义，同时也对普遍提 高材料利用率大有裨益。 2 2 选择方法的思想路线和前提假设 既然暂时无法对原料组合进行预测，又不能穷举所有的原料组合，所以当前构 造原料选择方法的思想路线就是通过设计一种原料选择的迭代结构，并制定一定 的原料选择规则，使得对于原料的选择范围有针对性的逐步缩小。在此路线的指 导下，本文提出三种原料选择方法：筛选法、交叉组合法和最速下降法，它们从 不同的侧面来缩小搜索范围。在介绍它们之前，先介绍它们共用的概念和前提假 设。 基组原料：设有肘种原料参与优化，采用某种优化算法进行一次优化运算 后，称出现在结果方案中所有的肘。( 肘。肘) 种原料构成的集合为基组原料。 非基组原料：设有膨种原料参与优化，采用某种优化算法进行一次优化运 算后，称未出现在结果方案中的所有的m 。( 肘，肘) 种原料构成的集合为非基组 原料。 对于一次优化而言，有m = m 8 + 肘，m 目n m = m 。 认为基组中的原料有强弱之分，弱势群体的存在制约着材料利用率的进一 步提高。判断原料强弱有不同的评价方法，如平价利用率、价值量等。 设定一百分数，7 ，用于界定强弱原料的数量。基组中的m 。= l m 。叩i 部分 认为是强势原料，将被保留下来；而被认为是弱势群体的 m 。= l m 。x r j = m 。一m 。部分将会被舍弃或者被更改。其中“ ”和“【j ”分别表 示向上取整和向下取整。这么假设的基本思想是肯定优化算法在一定程度上对原 料选择的正确性，同时兼顾其不足。7 7 的取值根据具体情况来设定，通过设定- 7 ， 可以控制原料的组合范围。在原料种数不是很大的情况下，可以设定玎= 5 0 。 2 3 筛选法 2 3 1 筛选法的基本思想 筛选法的基本思想是：认为基组原料之所以被选中是因为它们能够产生比较好 的切割方式，同时在基组中的弱势原料的存在造成了算法过早陷入局部最优解， 那么针对基组原料再次进行内部组合将有可能获得更好的原料组合。根据下料的 经验来看，当参与优化的原料较多时，基组原料往往小于总原料数，即肘。 1 时，之所以只需要列出 从c 帮。1 到c j 答的所有原料组合，那时因为从答。1 到c ：1 扩1 1 的所有组合情况已 经在上一次，即i = i 一1 时被计算过，并且它们的结果并不优于当前基组的优化效 果，故而可以省略。 2 4 交叉组合法 2 4 1 交叉组合法的基本思想 与筛选法在基组内探索更优组合的思路不同，交叉组合法认为由于优化下料的 局部最优性，使得部分有价值的原料被排斥到非基组中，那么通过对基组与非基 组中的成分进行适当交换，则有可能发现更优的原料组合。也就是希望将基组中 的弱势原料与在非基组的潜在强势原料进行交换，以达到提高材料利用率的目的。 由于该方法与遗传算法【2 h 中的交叉或交换的思想比较接近，故有“交叉组合法”的 命名。在该方法中，识别弱势原料的依据不同构成不同的交叉组合法，可以采用 平均材料利用率或价值量来进行判断，评价值低的原料被认为是弱势群体，是被 交换的对象。图2 2 显示了交叉组合的原理。交叉过程中，基组换出的原料种数和 换入的原料种数是相等的，因此这是一种等量交叉方法。 1 0 重庆大学硕士学位论文2 多原料下料问题中的原料选择技术研究 基组 交 非基组 强原料i 诊 吒。 原料2 l 俣留 o 原辩 原料 ， l 餮 弱原料m 图2 2 交叉组合原理 f i g2 2p r i n c i p l eo f e x c h e m g c - c o m b i n a t i o nm e t h o d 2 4 2 交叉组合法的工作流程 交叉组合法的工作流程可如此描述：首先对原始材料进行优化得到初始基组和 非基组。然后，根据设定的叩值，计算出能够保留的最少原料种类数肘。，将肘。 与非基组原料种数相比较，取小值埘疗 肘。，膨。， 作为最大可交叉数量，并定义交 叉厅种原料为刀次交叉；根据设定的原料强弱的判断标准对原料进行排序。接着， 分别列出1 次交叉到m i n m 。m 。： 次交叉的所有原料组合。再对各个原料组合进 行优化，将结果与基组原料的结果相比较，如果有更优的组合方案，那么将这个 组合方案所得到的基组和非基组原料分别作为新的基组和非基组原料，并重复上 面的步骤；如果依然是基组原料占优，那么则认为此基组原料就是目标组合。交 叉组合法的工作流程图如图2 3 所示。 2 4 3 交叉组合法的算法实现 类似于筛选法的算法实现步骤，交叉组合法的算法步骤如下： 设置迭代计数器i = 1 ，基组原料为肘g ，非基组原料为m 。o ，基组中能够保留 的最少原料数为m 蜜，第i 次优化结果为，嚣“，原料组合数组t m p m 】用于记录原料 的可能组合情况，结果数组t m p r e s 】用于记录与t m p m 】相对应的优化结果。 对原始原料优化，记录优化结果r e s ( ”、基组原料m g 和非基组原料m g 。 计算最大原料交叉数量胁h m 。，m 。 ，按照原料强弱标准设定交叉原料的 顺序，列出从1 次交叉到m i n m ，m 。) 次交叉的所有原料组合，记录于t m p m 】中。 对t m p m 】中的原料组合进行依次优化，记录它们的优化结果于t m p r e s 】中， 并找出其中的最优值。 将步骤得到的最优值与r e s “进行比较，如果前者更优，则以这个组合方 案所得到的基组和非基组原料分别作为新的基组和非基组原料，计数器f ；f + 1 ， 转步骤；如果还是后者占优，停止探索，并输出m = m g 。 重庆大学颈士学往论文2 多原料下料问题中的原料选择技术研究 图2 3 交叉组合法的工作流程 2 5 最速下降法 2 5 1 最速下降法的基本思想 虽然说筛选法和交叉组合法在一定的程度上缩小了原料组合的探索范围，但是 当原料数量实在比较多，且基组原料数也比较大的情况下，它们所需要进行的组 合试探依然不少。为了进一步使原料选择技术走向实用化，在交叉组合法的基础 上，引入一定规则，提出最速下降法。该方法可以认为是交叉组合法的变种，引 入的规则有两条，其一，增强基组中原料强弱的模糊性，即对于强弱相当的原料 具有等同的可交叉性。其二，将非基组作为一个整体进行交叉，而不管基组决定 换出几种原料。如此，在宏观上可以认为，新原料组合的获得是通过从原来的原 料中去掉一定数量的由基组确定的弱势原料。相对于交叉组合法，该方法是一种 不等量交叉方法。在基组中原料的强弱比较分明的情况下，最速下降法在该基组 1 2 重庆大学硕士学位论文 2 多原料下料问题中的原料选择技术研究 上的探索最多只需要执行膨。次，这样效果就比较理想了。该方法的实现流程与 交叉组合法基本一样，不同之处只须按照规则作相应改动，下面介绍其算法实现