（机械制造及其自动化专业论文）支持多任务集成下料的优化下料技术研究及应用.pdf

中文摘要 摘要 实施绿色制造与低碳制造是制造业减少资源消耗强度的重要途径，减少物料 消耗和能源消耗是企业实施绿色制造的具体手段。优化下料技术是实现减少物料 消耗的一项具体实用技术，作为控制原材料利用率的重点环节，通过采用合理的 优化下料技术，对减少有限资源的浪费和碳排放起着积极而关键的作用。传统的 优化下料注重于排料的数学意义上的最优，但难于解决实际工程应用中大规模多 任务集成下料、特殊数据结构适应性、下料过程自动化、系统集成等一系列复杂 应用需求问题。论文针对目前企业普遍采用的多工程、多任务集成下料方式，围 绕支持多任务集成下料的优化下料技术及应用进行了深入研究。 首先，在分析多任务集成下料问题特点的基础上，提炼总结了支持多任务集 成下料的优化下料需求，建立了多任务集成下料的优化决策过程模型；针对多任 务集成下料优化决策过程中所涉及的重要支持技术，建立了支持多任务集成下料 的优化下料技术体系，并以关键技术攻关作为研究重点给出了论文的解决思路。 然后，针对技术体系中的主要关键技术展开了研究，包括多任务大规模零件 复杂轮廓信息的自动提取技术、多任务大规模零件的分组优化技术及基于网络的 零件分组并行优化下料技术。 针对多任务集成下料中大规模零件轮廓信息提取过程复杂、提取工作量大等 问题，提出了一种零件轮廓分层路由提取的m s t 生长算法，包括零件轮廓路由拓 扑结构的构造和基于有权无向图m s t 的轮廓劈裂提取。其中，零件轮廓路由拓扑 结构的构造包括基于拓扑投影的图纸平面化、节点路由状态定义与特征节点提取 和轮廓线重组；基于有权无向图m s t 的轮廓劈裂提取包括无向图m s t 求解和轮 廓线布尔劈裂。同时，为了实现下料生产对产品设计变更的快速响应，避免传统 上更改传递的冗余过程，提出了基于产品模型重建的设计变更快速响应方法。 针对优化算法在处理多任务集成下料问题时易陷入时间效率和材料利用率矛 盾的问题，提出了基于下料特征的多任务大规模零件分组优化策略，将零件的相 似性特征和下料配合特征作为分组约束，并利用样本零件的导向作用加速零件分 组过程，研究了具体的零件分组优化方法。一方面，为了克服传统无监督聚类算 法中聚类中心需事前确定、聚类结果不稳定等缺点，提出了一种k m e a n s 与h c m 算法相结合的大规模零件分组优化方法；另一方面，利用图论工具对零件的下料 特征关联进行分析，提出了一种基于有权无向图m s t 的大规模零件自适应分组优 化方法，并通过应用实例验证了两种方法的可行性和有效性。 针对目前不同优化方法及其优化软件对不同下料数据优化效果具有不确定性 重庆大学博士学位论文 的问题，为了避免零件分组形成的下料子任务优化效果不理想而影响最终下料方 案的形成，提出了一种基于网络的零件分组并行优化下料方法，通过集成多种计 算资源、多种下料方法，利用开放的网络环境进行零件分组的并行优化求解，重 点建立了基于网络的零件分组并行优化下料模型，并给出了零件分组并行优化下 料的物理拓扑结构。 最后，以a u t o c a d 作为系统的图形支持平台，建立了支持多任务集成下料的 优化下料系统的结构体系和功能体系，以国家8 6 3 c i m s 目标产品“建筑金属结构 计算机辅助设计与生产管理集成系统”中的条材板材优化下料子系统为基础，基于 上述研究结论开发了支持多任务集成下料的优化下料系统。 论文的研究内容是国家自然科学基金项目的重要组成部分，其研究结论和开 发的产品是2 0 1 1 年度高等学校科学研究优秀成果奖科学技术进步二等奖获奖项目 “支持复杂应用需求的优化下料关键技术及应用”的重要组成内容，软件系统已经在 上百家企业中得到推广应用；在减少物料资源消耗、提高企业的生产制造水平方 面，取得了较好的应用效果。 关键词：多任务集成下料，零件轮廓提取，零件分组优化，并行优化，下料系统 i i 英文摘要 a b s t r a c t i m p l e m e n t a t i o no fg r e e nm a n u f a c t u r i n ga n dl o w - c a r b o nm a n u f a c t u r i n g i st h e i m p o r t a n tw a y t or e d u c em a n u f a c t u r i n gr e s o u r c ec o n s u m p t i o n , a n dr e d u c i n gm a t e r i a l c o n s u m p t i o na n de n e r g yc o n s u m p t i o n a r e t h e s p e c i f i c m e a n sf o re n t e r p r i s e st o i m p l e m e n tg r e e nm a n u f a c t u r i n g c u t t i n gs t o c kt e c h n o l o g yi sap r a c t i c a lt e c h n o l o g yt o r e d u c em a t e r i a lc o n s u m p t i o n ，w h i c hm a i n l yc o n t r o l st h em a t e r i a lu t i l i z a t i o nr a t i o t h e r e f o r e ，b yu s i n gr a t i o n a lc u t t i n gs t o c kt e c h n o l o g y , t h ew a s t eo fl i m i t e dr e s o u r c e sa n d c a r b o ne m i s s i o n sw i l lb eg r e a t l yr e d u c e d t h et r a d i t i o n a lc u t t i n gs t o c kt e c h n o l o g y f o c u s e so nt h eo p t i m a lm a t e r i a lu t i l i z a t i o nr a t i oo fp u r em a t h e m a t i c s ，b u ti ti sd i f f i c u l tt o s o l v eas e r i e so fc o m p l e xa p p l i c a t i o nr e q u i r e m e n t si np r a c t i c a le n g i n e e r i n ga p p l i c a t i o n ， s u c ha l si n t e g r a t e dc u t t i n gs t o c k ，a d a p t a b i l i t yt os p e c i a ld a t as t r u c t u r e ，c u t t i n gp r o c e s s a u t o m a t i o n ，s y s t e mi n t e g r a t i o n ，a n ds oo n a c c o r d i n gt ot h ei n t e g r a t e dc u t t i n gs t o c k m o d ec o m m o n l yu s e db ye n t e r p r i s e s ，c u t t i n gs t o c kt e c h n o l o g i e sf o ri n t e g r a t e dc u t t i n g s t o c ka n di t sa p p l i c a t i o na r es t u d i e di nt h i st h e s i s f i r s t l y , b a s e do nt h ea n a l y s i so ft h ei n t e g r a t e dc u t t i n gm o c kp r o b l e m ( i c s p ) s c h a r a c t e r i s t i c s ，c u t t i n gs t o c kr e q u i r e m e n t sf o ri c s p a r es u m m a r i z e d t h e n , o p t i m i z a t i o n d e c i s i o nm o d e lf o ri c s pi se s t a b l i s h e d a c c o r d i n gt ot h ei m p o r t a n ts u p p o r t i n g t e c h n o l o g i e si n v o l v e di nt h eo p t i m i z a t i o nd e c i s i o np r o c e s s ，t e c h n o l o g ys y s t e m f o ri c s p i s c o n s t r u c t e d s o l v i n gt h o u g h tf o ri c s pi sp u tf o r w a r d 谢t 1 1k e yt e c h n o l o g i e s a s r e s e a r c he m p h a s i s s e c o n d l y , t h ek e yt e c h n o l o g i e si nt h et e c h n o l o g ys y s t e ma r es t u d i e di nd e t a i l ， i n c l u d i n ga u t o m a t i ce x t r a c t i o nt e c h n o l o g y o fl a r g e s c a l e p a r t s c o m p l e xo u t l i n e ， g r o u p i n go p t i m i z a t i o nt e c h n o l o g y o fl a r g e s c a l ep a r t sa n dp a r a l l e lo p t i m i z a t i o n t e c h n o l o g yo fp a r t sg r o u p sb a s e do nn e t w o r k o np a r t so u t l i n ee x t r a c t i o n ，i no r d e rt or e s o l v et h ec o m p l i c a t e de x t r a c t i o np r o c e s s a n dh e a v yw o r k l o a dp r o b l e m s ，m s tg r o w i n ga l g o r i t h m sf o rp a r t so u t l i n eh i e r a r c h i c a l r o u t i n ge x t r a c t i o na r ep r o p o s e d ，w h i c hi n c l u d et h e c o n s t r u c t i o no fo u t l i n er o u t i n g t o p o l o g ya r c h i t e c t u r ea n do u t l i n ed i s a s s e m b l i n ge x t r a c t i o nb a s e do nm s t o fw e i g h t e d u n d i r e c t e dv i e w c o n s t r u c t i o no fo u t l i n er o u t i n gt o p o l o g y a r c h i t e c t u r ei n v o l v e s d r a w i n g sc o m p l a n a t i o nb a s e do nt o p o l o g i c a lp r o j e c t i o n ，t h e d e f i n i t i o no fn o t er o u t i n g s t a t u s ，t h e e x t r a c t i o no ff e a t u r en o t e sa n do u t l i n er e s t r u c t u r i n g a n do u t l i n e d i s a s s e m b l i n ge x t r a c t i o ni n v o l v e st h es o l u t i o no fu n d i r e c t e dv i e w sm s t a n do u t l i n e i i i 重庆大学博士学位论文 b o o l e a nd i s a s s e m b l i n g m e a n w h i l e , i no r d e rt or e a l i z eq u i c kr e s p o n s et od e s i g nc h a n g e i nc u t t i n gs t o c ka n dt oa v o i dr e d u n d a n tp r o c e s so ft r a d i t i o n a lc h a n g et r a n s f e r , q u i c k r e s p o n s em e t h o df o rd e s i g nc h a n g eb a s e do np r o d u c tm o d e lr e c o n s t r u c t i o n i s p u t f o r w a r d o ng r o u p i n go p t i m i z a t i o no fl a r g e s c a l ep a r t s ，a i m e da tt h ec o n t r a d i c t i o no ft i m e e f f i c i e n c ya n dm a t e r i a lu t i l i z a t i o nr a t i oi ni c s p , g r o u p i n go p t i m i z a t i o ns t r a t e g yo f l a r g e - s c a l ep a r t sb a s e do nc u t t i n gs t o c kc h a r a c t e r i s t i c si sp r o p o s e d w i t ht h es t r a t e g y , c o n c r e t ep a r t sg r o u p i n gm e t h o d sa r ef u r t h e rs t u d i e dw i t hp a r t s s i m i l a r i t yc h a r a c t e r i s t i c s a n dp a r t s c o m b i n a t i o nc h a r a c t e r i s t i c sa s g r o u p i n gc o n s t r a i n t s ，m e a n w h i l e ，p a r t s s a m p l e sa r eu t i l i z e dt oa c c e l e r a t eg r o u p i n gp r o c e s s o nt h eo n eh a n d ，a c c o r d i n gt ot h e s h o r t c o m i n g so fu n s u p e r v i s e dc l u s t e r i n ga l g o r i t h m st h a tc l u s t e r i n gc e n t e r ss h o u l db e d e t e r m i n e db e f o r e h a n da n du n s t a b l ec l u s t e r i n gr e s u l t sl i k e l yo c c u r , ap a r t sg r o u p i n g o p t i m i z a t i o nm e t h o db a s e do nk - m e a n sa n dh c m i sp u tf o r w a r d o nt h eo t h e rh a n d ，b y a n a l y z i n gt h ea s s o c i a t i o no fp a r t s c u t t i n gs t o c kc h a r a c t e r i s t i c sw i t hg r a p ht h e o r y , ap a r t s 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 d o nm s to fw e i g h t e du n d i r e c t e dv i e wi s e s t a b l i s h e d a tl a s t ，t h ea p p l i c a t i o ne x a m p l e sv a l i d a t et h ef e a s i b i l i t ya n de f f e c t i v e n e s so f t h ep r o p o s e dm e t h o d s o np a r a l l e lo p t i m i z a t i o no fp a r t sg r o u p s ，i no r d e rt or e s o l v eu n s t a b l eo p t i m i z a t i o n r e s u l t sp r o b l e m sw h e nd i f f e r e n to p t i m i z a t i o nm e t h o d sa n dc o r r e s p o n d i n go p t i m i z a t i o n s y s t e m sp r o c e s sd i f f e r e n td a t a , a n dt oa v o i dn e g a t i v ei n f l u e n c eo nf i n a lc u t t i n gs o l u t i o n c a u s e db yu n s a t i s f a c t o r y o p t i m i z a t i o n r e s u l t so fc u t t i n gs t o c ks u b t a s k s ，ap a r a l l e l o p t i m i z a t i o nm e t h o df o rp a r t sg r o u p sb a s e do nn e t w o r ki sg i v e n a n dt oc o m p l e t et h i s m e t h o d ，t h ep a r a l l e lo p t i m i z a t i o nm o d e lf o rp a r t sg r o u p sb a s e do nn e t w o r ka n dp h y s i c a l t o p o l o g i c a ls t r u c t u r ef o rp a r a l l e lo p t i m i z a t i o na r ec o n s t r u c t e d b yi n t e g r a t i n gv a r i o u s c o m p u t i n gr e s o u r c e sa n dc u t t i n gs t o c km e t h o d s ，t h ep a r a l l e lo p t i m i z a t i o nf o rp a r t s g r o u p sb a s e do no p e nn e t w o r ke n v i r o n m e n ti sr e a l i z e d f i n a l l y , b ys e l e c t i n g a u t o c a da s t h e s y s t e m sg r a p h i cs u p p o r tp l a t f o r m ， a r c h i t e c t u r ea n df u n c t i o ns t r u c t u r eo ft h es y s t e ms u p p o r t i n gi n t e g r a t e dc u t t i n gs t o c ka r e c o n s t r u c t e d b a s e do nc u t t i n gs t o c ks u b s y s t e mo fb a ra n d p l a t ew h i c hb e l o n g st o 8 6 3 c i m ss o f t w a r ep r o d u c tc a l l e dc a da n dp r o d u c t i o nm a n a g e m e n ti n t e g r a t e ds y s t e m f o ra r c h i t e c t u r em e t a ls t r u c t u r e ，t h ec u t t i n gs t o c ks y s t e mu s i n gt h ea b o v er e s e a r c h r e s u l t si sd e v e l o p e d t h i st h e s i s sr e s e a r c hc o n t e n t sa r et h ei m p o r t a n tp a r to ft h ep r o j e c ts u p p o r t e db y t h en a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o n ，a n dt h er e s e a r c hr e s u l t sa n d d e v e l o p e ds y s t e m i v 英文摘要 a r ea l s ot h ei m p o r t a n tp a r to ft h ew i n n i n gp r o je c tc a l l e dc u t t i n gs t o c kk e y t e c h n o l o g i e s s u p p o r t i n gc o m p l e xa p p l i c a t i o nr e q u i r e m e n t sa n di t sa p p l i c a t i o n s t h i sp r o j e c th a sw o n t h es e c o n da w a r do ft h es c i e n t i f i ca n dt e c h n o l o g i c a lp r o g r e s so fc h i n a sm i n i s t r yo f e d u c a t i o n t h es y s t e mh a sb e e na p p l i e dt oh u n d r e d so fe n t e r p r i s e s ，a n d g o o d a p p l i c a t i o n e f f e c ti so b t a i n e df o r r e d u c i n gm a t e r i a lc o n s u m p t i o na n di m p r o v i n g e n t e r p r i s e s m a n u f a c t u r i n gl e v e l k e y w o r d s ：i n t e g r a t e dc u t t i n gs t o c k ，p a r t s o u t l i n e e x t r a c t i o n ，p a r t sg r o u p i n g o p t i m i z a t i o n ，p a r a l l e lo p t i m i z a t i o n ，c u t t i n gs t u c ks y s t e m v 重庆大学博士学位论文 v i l 绪论 l 绪论 1 1 优化下料问题概述 1 1 1 优化下料问题所属研究领域 “减少资源消耗、优化利用资源”是经济可持续发展战略的重要内容，建设“资 源节约型、环境友好型”社会是加快转变经济发展方式的重要着力点。根据国家统 计局统计数据显示，截止至u 2 0 1 0 年1 1 月份，中国的年钢产量已经突破7 亿吨，平板 玻璃达5 7 7 亿重量箱，铝材产量近2 0 0 0 万吨。上述数据充分表明，我国目前的资源 消耗量巨大。然而，我国目前的资源利用率偏低，以钢材为例：由于缺乏钢材套 料技术和切割焊接经验，我国企业在钢材切割焊接过程中比美国、日本等发达国 家的企业多浪费1 0 的钢材。我国造船业目前钢材利用率为8 7 ，而日本韩国钢材 利用率已达至u 9 2 9 5 ，差距十分明显，造成了巨大的浪费，改善和提高资源的 利用水平，对我们这样一个资源消耗大国，具有重大的经济意义和社会意义。 实施绿色制造与低碳制造是制造业减少资源消耗强度的重要途径，减少物料 消耗和能源消耗是企业实施绿色制造的具体手段。如图1 1 所示，优化下料技术是 实现减少物料消耗的一项具体实用技术，优化下料是指在一定的生产条件下，将 一批尺寸有别的零件互不重叠地、最优地排布到具有一定规格尺寸的原材料之中， 在满足切割工艺等约束条件的前提下，使得零件切割下来后所剩的废料尽可能的 少。优化下料技术应用范围非常广泛，在机械、家具、钢铁、船舶、车辆、建筑、 造纸、玻璃、皮革等制造业中普遍存在着下料问题，作为控制原材料利用率的重 点环节，通过采用合理的优化下料技术，对减少有限资源的浪费和碳排放起着积 极而关键的作用。 绿色制造 低碳制造 优化下料技术 上实用技术 减少物料消耗 减少能源消耗 ( 生产制造过程) 图1 1 优化下料技术所属研究领域 f i g 1 1t h er e s e a r c hf i e l do fc u t t i n gs t o c kt e c h n o l o g y 重庆大学博士学位论文 1 1 2 优化下料问题描述一 优化下料问题，国外称之为“c u t t i n g s t o c kp r o b l e m ( c s p ) ”。该问题在不同的 刊物上有一些不同的提法，如“t r i ml o s sp r o b l e m ”，“b i np i c k i n gp r o b l e m ”， “a s s o r t m e n tp r o b l e m ”，“l a yo u tp r o b l e m ”等【l 】。对优化下料问题的大规模研究始于 2 0 世纪7 0 年代【2 1 ，该问题的产生主要是现代加工制造业的发展和市场经济竞争所 产生的推动结果。优化下料作为控制原材料利用率的重点环节，其目标是寻找一 种材料利用率尽可能高的下料方案进行材料切割。通过采用合理的优化下料技术 制定科学合理的下料方案，对节省原材料起着积极而关键的作用，已经成为企业 节约成本和提升竞争力的重要手段；同时自动化下料技术的应用也有利于提高切 割生产效率和降低人力成本。优化下料问题可定义如下： 定义1 - 1 在给定的玎维几何空间g ( 刀) 内，寻找一种最优的布局方案将尽可能多的待排样 空间子集 r 。，r 2 ，r 。) 填充到g ( ，? ) 内，优化目标是使得排样后子集所占用的空间最大，即 几何空间g ( n ) 的利用率最大需要满足的约束条件为被排样的空间子集r ，必须位于g 0 ) 内，即足g ( 刀) ( f = 1 , 2 ，m ) ，且任意两个子集互不重叠，即r ，r 、r j = 咖( f ，j = 1 , 2 ，聊) ， 且f j ，同时需满足一定的下料工艺要求。 上世纪7 0 年代以前，由于当时计算工具的限制，优化下料问题并未引起人们 的足够重视，优化下料技术一直处于理论研究阶段，实际下料生产仍主要采用人 工排样方式。随着计算机软硬件技术以及诸如线性规划、运筹学理论、智能决策 等现代优化技术的发展，为优化下料问题的研究成果的付诸生产实际创造了条件， 世界上许多研究机构和研究人员都投入到对优化下料问题的研究中，不同的研究 人员从不同的学科角度、运用不同的优化方法，提出了多种排样算法，发表了许 多相关论文，有些还开发了相应的软件产品。 优化下料问题本身是具有最高计算复杂度的非确定性( n o n d e t e r m i n i s t i c p o l y n o m i a l ，n p ) 完全问题，并且广泛存在于制造业的各个领域，和生产实践密切 相关。通过采用好的下料方案可以为企业节约巨额资金，因此对优化下料技术的 研究具有较高的理论价值和经济效益，这也是优化下料研究一直都很活跃的关键。 传统的优化下料研究偏重于优化下料算法的创新和改进，注重于排料的数学意义 上的最优，产生了许多高效的排样算法，但随着生产技术的不断更新以及制造模 式的急剧变化，这些排样算法已无法满足越来越复杂的应用需求。如：随着计算 机处理技术和系统集成技术的发展，多任务集成下料等新的下料模式不断涌现。 相对于传统的单一任务下料，多任务集成下料使得下料问题的规模呈“爆炸式”增 长，诸多算法在处理多任务集成下料问题时易陷入时间效率和材料利用率矛盾的 2 l 绪论 问题，而一味通过算法改进来解决此问题的想法被认为是不现实的。另外，大规 模零件下料信息的自动获取也成为很好解决多任务集成下料问题的重要支持技 术。又如：随着优化下料技术应用的深入，优化下料技术的应用环境、下料数据 结构以及实际应用需求的千差万别，使得单一排样算法对不同下料任务优化结果 的稳定性难于保证，成为优化下料研究有待解决的关键问题之一。此外，优化下 料问题不是一个纯粹的数学问题，还需要解决实际工程应用中数据集成、可制造 性、原材料工艺状况约束、交货期要求、下料过程自动化、余料再利用等一系列 复杂应用需求问题，成为优化下料技术实用化的重要研究方向。 1 1 3 优化下料问题的主要应用领域 优化下料问题广泛存在于国民经济的多个行业中，如机械、家具、钢铁、船 舶、车辆、建筑、造纸、玻璃、皮革等。优化下料的核心是在满足工艺条件的基 础上，尽可能地提高原材料利用率，以达到减少材料浪费和节省成本的目的。表 1 1 所示为优化下料问题的主要应用领域【3 训。 表1 1 优化下料问题的主要应用领域 旦垒! 曼! ：! ! 蛙翌查坠箜p ! i 璺型i q 堕鱼璺! 坐q 里坚i 望g ! ! q 丛2 翌鱼! 宝堕 行业名称主要应用问题 机械制造业 家具制造业 建筑业 造纸业 皮革制品业 服装制造业 印刷包装业 微电子 航空航天 钢板、卷材分割，工业用各种钣金件、型材、管材、棒料分割，汽车、 船舶、压力容器等的钢板下料 木制家具的胶合板、木条的分割，金属家具的型材、板材的分割，玻 璃板、石膏板的分割 钢筋、门窗幕墙铝合金型材、钢结构型材分割，建筑用玻璃、金属板、 保温板、混凝土模板裁制 大尺寸纸张原片及卷纸的分割 大尺寸皮革原片上不同形状毛坯的套裁 制衣、制鞋中布匹、皮革等原材料上不同形状毛坯的套裁 包装材料分割，报纸书刊的版面布局 集成电路的布局、电路板的切割 航天器舱室静态布局与动平衡布局 1 1 4 优化下料问题的分类及定义 对优化下料问题的科学分类和准确定义是全面了解和解决优化下料问题的基 础。根据不同的分类标准，优化下料问题有多种分类方法。如图1 2 所示，文献【5 】 根据是否涉及空间布局问题将优化下料问题划分为狭义优化下料问题和广义优化 重庆大学博士学位论文 下料问题，狭义优化下料问题又分为材料分割和器物填充2 类，材料分割类下料 问题在实际生产中应用较多，如型材、玻璃、皮革分割等，凡是需要从原材料上 切割下零件的下料都属于该类问题；器物填充主要包括车辆装载、容器填充等空 间利用问题。广义优化下料问题按照不同的尺度属性( 金融尺度、时间尺度、重 量尺度、其他尺度) 可划分成4 类，主要包括资金预算、找零、任务调度、队列 平衡、背包问题、内存分配及数据存储等。根据所处的不同空间维度，狭义优化 下料问题又可划分为一维( 条材) 、二维( 板材) 及三维( 装箱) 优化下料问题。 对于研究广泛的二维优化下料问题，文献 6 】按照下料零件特点、下料区域、优化 标准和工艺要求对其分类进行了系统研究，根据零件形状可分为矩形下料、规则 多边形( 圆形、三角形等) 下料、不规则多边形下料；根据零件排列方式可分为 方向固定与可旋转下料；根据切割工艺可分为一刀切下料( 剪床下料、玻璃切割) 及正交下料( 线切割、火焰切割、气割) 。 材料分割器物填充金融尺度时间尺度 重量尺度其他尺度 图1 2 优化下料问题的分类 f i g 1 2t h ec l a s s i f i c a t i o no fc u t t i n gs t o c kp r o b l e m 以下分别对一维、二维及三维优化下料问题进行描述和定义： 一维优化下料问题 一维优化下料问题，又称为条材下料问题，即认为零件与原材料等宽，排样 时只需要在长度方向进行考虑。该问题可描述为：设有k 种原材料，第k 种原材料 的数量为。，原材料长度分别为厶，l ：，l r ，m 种待下料零件的长度分别为 0 ，：，z 。，各零件的需求量分别为b 16 ：，b 。排样目标是在完成所有零件下料 的基础上，使得消耗的原材料长度最少。建立其优化数学模型如式( 1 1 ) 所示， 为不失一般性，假设k 种原材料中有r 种原材料无数量限制，则0 n k 0 0 ， k = 1 , 2 ，k 一，；n k = 0 0 ，k = k 一，| + 1 ，k 一，+ 2 ，k 。 4 1 绪论 ki l k 口x 夕玩 ，i = 1 ，2 ，聊 。2 1 ，“ ( 1 1 ) i 赋 x 夕以 k = l x o ，且为整数 ，k = 1 , 2 ，k 一， 其中： z 目标函数( 长度最小) ； 厶第k 种原材料的长度； k 原材料的种类； x 在第k 种原材料上的第j 种切割方式的使用次数，即用第j 种切割方 式切割第k 种原材料的数量； 仇第k 种原材料上可行切割方式总数； 包第i 种待下零件的需求量； 够第k 种原材料对应的第j 种切割方式下第i 种零件的数量： m 第k 种原材料的数量： m 零件种类。 式( 1 1 ) 描述的数学模型是典型的整数线性规划模型，目标函数z 记录下料 过程中原材料的消耗，约束条件则规定了待下料零件在原材料上的合理排布。根 据现有整数线性规划模型的求解算法【7 8 】，以上不等式方程组理论上可以求得最优 解，但随着下料零件种类的增加，算法求解的计算量将呈指数级增长【9 1o 】。因此除 零件规模较小的实例外，一般无法在合理的时间内找到最优解。实际应用中常去 掉对变量的整数约束，将其转化为线性规划问题用背包算法进行求解。目前则主 要采用各种启发式排样算法或智能排样算法。 上述数学模型考虑了原材料规格多样、部分原材料有数量限制的情况，对该 模型进行适当调整后就能将其转化为特定的一维优化下料问题。当r = k 时，模型 则适合于多种原材料且原材料没有数量限制的一维优化下料问题：当k = 1 时，该 模型适合于单一原材料的一维优化下料问题，如：某门窗生产企业拟采用某种切 割设备对一批铝合金型材进行下料，表1 2 是待下料零件规格与数量，表1 3 是按 原材料长度为5 0 0 0h i m 时求解上述模型得到的切割方案，其材料综合利用率为 9 7 9 3 。 ，r l ， x 一 r 埘 = znm 重庆大学博士学位论文 表1 2 待下料零件规格和数量 序号零件规格m m 需求数量件 表1 3 优化下料结果方案 序号材料长度下料规格及数量余量根数 6 1 绪论 二维优化下料问题 二维优化下料问题，又称为板材下料问题，即认为零件与原材料的长、宽均 不相等，按照零件形状的不同，二维优化下料问题可分为矩形零件下料、规则形 状零件( 圆形、三角形) 下料及不规则形状零件下料，其排样时至少需要在2 个 尺寸方向进行考虑。以矩形零件排样为例，该问题可描述为：设有k 种原材料， 7 重庆大学博士学位论文 第k 种原材料的数量为。，原材料长、宽分别为p ( l ，) ，p ( l 2 ，) ，p ( l k ，) ， m 种待下料零件的长、宽分别为p ( f l ，w i ) ，p ( z ：，w ：) ，p ( ，。，w 。) ，各零件的需求量 分别为b ，b ：，b 。排样目标是在完成所有零件下料的基础上，使得消耗的原材料 面积最小，且满足条件：1 ) 零件必须包含在原材料内部，即对于任意的零件 p q ，w ，) ，在其套裁的原材料p ( l ，形，) 上，满足尸( ，w ，) 互p ( l ，形f ) ( f = 1 , 2 ，m ，= 1 , 2 ，k ) ；2 ) 任意两个零件互不重叠，即e ( t ，w ，) r 、尸( ，w ，) = 妒 ( f ，= l ，2 ，m ) ，且f ，。将数学模型式( 1 1 ) 中的原材料长度替换为原材料面 积即可建立二维优化下料问题的数学模型，某矩形零件优化排样图如图1 3 所示。 3 r3 rl r 3 r3 r i r 3 r3 r 图1 3 矩形零件优化排样图 f i g 1 3t h eb l a n kl a y o u tg r a p h i c so fr e c t a n g u l a rp a r t s 相对于一维优化下料问题，二维优化下料问题的约束条件更少，排样中零件 可以布置在二维板材内的任意位置，不规则零件还可以在3 6 0 。的范围内任意旋转， 其可行切割方式的组合数量更加巨大，不同切割方式中零件的套裁方式也更为复 杂，仍是一个求解相当困难的n p 完全问题。此外，为满足零件图形包含在板材图 形区域内及零件图形问互不重叠的条件，排样过程中需要对零件图形及板材图形 进行大量复杂的几何图形运算，使得二维优化下料问题的求解难度大大增加，对 其科学求解方法的突破将具有重要的意义，因此二维优化下料问题，特别是不规 则零件的下料问题，已成为优化下料研究的热点。 三维优化下料问题 三维优化下料问题，又称为装箱问题，其主要解决的是空间体积的高效利用 问题，即在一个给定的三维空间内，装填若干尺寸不同的三维零件，在将所有零 件装完的基础上，使得零件所占用的空间体积总量最小。如图1 4 所示为典型的三 维优化下料问题集装箱装填问题。由于三维优化下料问题应用相对较少，且 复杂度高，本文将不纳入研究范畴。 1 绪论 回回 够 匕令ll 亡 图1 4 集装箱装填问题 f i g 1 4c o n t a i n e rp a c k i n gp r o b l e m 每类优化下料问题的应用场合各不相同，但通过上述对每类优化下料问题的 描述和定义，可以反映出优化下料问题的共同特征：1 ) 包含两组基本数据，即零 件规格和原材料规格；2 ) 以满足工艺、空间等约束条件为基础，寻求一种合理的 排样布局方案，将所有的零件进行下料，并使原材料的利用率尽可能高。 1 2 优化下料问题的国内外研究现状与发展趋势 1 2 1 优化下料问题的理论研究现状 对先进优化下料技术的研究早已在很多国家受到高度重视，并且已经形成了 许多有价值的研究成果。最早关于优化下料的研究是k a n t o r o v i c h 【1 l 】于1 9 3 9 年发表 的关于一维优化下料的文章。五十年代中期，p a u l l i l 2 】、e i s e m a n n t l 3 】、h e r r m a n n 和 d a i l 4 j 率先提出用线性规划( l i n e a rp r o g r a m m i n g ) 的方法解决印刷和造纸工业的 矩形件排样问题，但其效果不理想。g a r e y 和j o h n s o n 1 5 】证明用数学规划 ( m a t h e m a t i c a lp r o g r a m m i n gt e c h n i q u e s ) 的方法解决二维下料问题是优化问题中 具有最高计算复杂度的n p 完全问题。6 0 年代初，g i l m o r e 和g o m o r y 1 6 - 1 9 】发表了四 篇著名的优化下料论文，使用列生成技术解决了一维下料问题，并对二维下料问 题进行了开创性地探讨。但由于当时计算工具的限制，优化下料问题并未引起人 们的足够重视，理论研究处于初级阶段。7 0 年代，随着高速计算机的出现和诸如 线性规划、运筹学理论等现