（机械制造及其自动化专业论文）支持复杂应用状态的一维优化下料系统研究及其应用.pdf

重庆大学硕士学位论文 中文摘要 摘要 实施绿色制造与低碳制造是制造业减少资源消耗强度的重要途径，减少物料 消耗和能源消耗是企业实施绿色制造的具体手段。优化下料技术是实现减少物料 消耗的一项具体实用技术，作为控制原材料利用率的重点环节，通过采用合理的 优化下料技术，对减少有限资源的浪费和减少碳排放起着积极而关键的作用。传 统的优化下料注重于排料的数学意义上的最优，缺乏对优化下料复杂应用状态及 其处理方法的系统性研究，难以适应企业实际下料问题应用状态的变化性和应用 状态模式的多样性，制约了优化下料技术应用的整体效果。本文围绕目前优化下 料存在的问题，对支持复杂应用状态的一维优化下料系统及其实用技术进行了深 入研究。 首先，分析了国内外一维优化下料技术的研究现状，针对现有研究的不足和 企业急需解决的优化下料问题，建立了一维优化下料复杂应用状态结构模型以及 一维优化下料复杂应用状态关联与影响评价模型；对复杂应用状态下一维优化下 料系统处理方法进行了研究，建立了支持复杂应用状态下一维优化下料问题的优 化决策过程模型。 接着，在分析复杂应用状态一维优化下料问题特点的基础上，提炼总结了系 统的应用需求，建立了支持复杂应用状态下一维优化下料系统的结构体系和功能 体系。 然后，针对大规模下料方式给优化下料问题带来的原材料利用率和时间求解 效率的矛盾问题进行了深入研究，提出了一种原材料不确定状态下的一维优化下 料方法。该方法首先根据订购件和标准件的下料特性，建立原材料订购件与标准 件混合下料的优化数学模型；然后提出并实现了一种基于零件下料配合特征的有 限递进复合求解方法，并通过应用实例证明了该方法的可行性和有效性。 最后，以国家8 6 3 c i m s 目标产品“建筑金属结构计算机辅助设计与生产管理 集成系统”中的一维优化下料子系统为基础，基于上述研究结论开发了支持复杂 应用状态的一维优化下料系统。 论文的研究内容是国家自然科学基金项目的重要组成部分，其研究结论和开 发的产品是2 0 1 1 年度高等学校科学研究优秀成果奖科学技术进步二等奖获奖项目 “支持复杂应用需求的优化下料关键技术及应用”的重要组成内容，软件系统已经 在上百家企业中得到推广应用；在减少物料资源消耗、提高企业的生产制造水平 方面，取得了较好的应用效果。 重庆大学硕士学位论文 中文摘要 关键词：一维优化下料，复杂应用状态，不确定状态，n p 完全问题 i i a bs 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 ga r e t h e i m p o r t a n tw a y st 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 n a n de n e r g yc o n s u m p t i o na r et h es p e c i f i cm e a n sf o re n t e r p r i s e s t 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 r i n gs t o c kt e c h n o l o g yi s ap 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 ，t h r o u g hu 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 d r e s o u r c e sa n dc 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 r i n gs t o c k t e c h n o l o g yf 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 ，l a c ko f s y s t e m a t i cs t u d yo nt h ec o m p l e xu s i n gs t a t ea n da p p r o a c ho fc u r i n gs t o c kp r o b l e m ， w h i c hi sd i f f i c u l tt oa d a p tt h ev a r i a b i l i t ya n dd i v e r s i t yo fu s i n gs t a t eo fc u t t i n gs t o c ki n t h ee n t e r p r i s e ，l i m i t i n gt h eo v e r a l le f f e c to ft h ec u r i n gs t o c kt e c h n o l o g y t h i sp a p e r f o c u s e so nt h ec u r r e n tp r o b l e m so fc u r i n gs t o c k ，o n e - d i m e n s i o n a lc u t t i n gs t o c ks y s t e m a n da p p l i c a t i o nt e c h n o l o g yf o rs u p p o r t i n gc o m p l e xu s i n gs t a t ea r es t u d i e di nt h i st h e s i s f i r s t l y ，r e s e a r c hs t a t u so fo n e d i m e n s i o n a lc u t t i n gs t o c kp r o b l e mo ft h ed o m e s t i c a n df o r e i g ni sa n a l y z e d ，t h es t r u c t u r a lm o d e l ，a s s o c i a t i o na n di m p a c ta s s e s s m e n to f m o d e lo fc o m p l e xu s i n gs t a t eo fo n e d i m e n s i o n a lc u r i n gs t o c kp r o b l e ma r ec o n s t r u c t e d a c c o r d i n gt oi n s u f f i c i e n c yo ft h er e s e a r c ha n dp r o b l e m sf o re n t e r p r i s et or e s o l v e t h e s y s t e ma p p r o a c ho fc o m p l e xu s i n gs t a t eo fo n e - d i m e n s i o n a lc u i n gs t o c kp r o b l e mi s s t u d i e d ，t h ed e c i s i o nm o d e lo fo n e d i m e n s i o n a lc u r i n gs t o c kp r o b l e mf o rs u p p o r t i n g c o m p l e xu s i n gs t a t ei sc o n s t r u c t e d s e c o n d l y ，b a s e do nt h ea n a l y s i s o fc h a r a c t e r i s t i c so fc o m p l e xu s i n gs t a t eo f o n e d i m e n s i o n a lc u r i n gs t o c kp r o b l e m ，a p p l i c a t i o nr e q u i r e m e n t so ft h es y s t e ma r e s u m m a r i z e d ，o r g a n i z a t i o ns t r u c t u r ea n df u n c t i o ns t r u c t u r eo fo n e - d i m e n s i o n a lc u r i n g s t o c kp r o b l e ms y s t e ms u p p o r t i n gc o m p l e xu s i n gs t a t ea r ec o n s t r u c t e d t h e n ，t h ec o n t r a d i c t i o n so ft i m ee 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 oo fc u t t i n g s t o c kp r o b l e mw h i c hl a r g e - s c a l ec u r i n gs t o c kw a yb r i n g s a r e d e e p l ys t u d i e d ，a o n e d i m e n s i o n a lc u r i n g s t o c km e t h o du n d e rt h es t a t eo fm a t e r i a li n d e t e r m i n a c yi s p r o p o s e d a c c o r d i n gt oc u r i n g - s t o c kc h a r a c t e r i s t i c so fo r d e rp a r t sa n ds t a n d a r dp a r t s ，a m a t h e m a t i c a lm o d e lo fc u r i n g - s t o c kp r o b l e mf o ro r d e rp a r t sa n ds t a n d a r dp a r t s c o m b i n a t i o ni se s t a b l i s h e d t h e n ，al i m i t e dp r o g r e s s i o nc o m p o u n dm e t h o db a s e do n c u r i n g s t o c kc h a r a c t e r i s t i c s o fp a r t si sp r o p o s e d ，a n di sa l s or e a l i z e d f i n a l l y ，t h e i i i e x p e r i m e n t a lr e s u l t sv a l i d a t et h ef e a s i b i l i t ya n d e f f e c t i v e n e s so ft h ep r o p o s e dm e t h o d f i n a l l v 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 rw h i c hb e l o n g st o8 6 3 c i m s s 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 d s y s t e m t o r a r c _ i l i t e c t u r em e t a ls t r u c t u r e ，ao n e d i m e n s i o n a lc u t t i n gs t o c ks y s t e ms u p p o r t i n g m a t e r i a l i n d e t e r m i n a c ys t a t eb yu s i n g t h ea b o v er e s e a r c hr 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 砌c 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 撕o n a ln a t i 】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 dd e v e l o p e ds y s t e m 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 j e 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 d i t sa p p l i c a t i o n s t h i sp r o j e c th a l sw o n t l l 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 d t oh u n d r e d so fe n t e r p r i s e s ， a n dg 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 rr e d u c i n g m a t e r i a lc o n s u m p t i o na n dl m p r o v m 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 ：o n e d i m e n s i o n a lc u t t i n gs t o c k ，c o m p l e xu s i n gs t a t e ，m a t e r i a li n d e t e r m i n a c y s t a t e ，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 i v 重庆大学硕士学位论文1 绪论 1 绪论 1 1 优化下料问题概述 1 1 1 优化下料问题所属研究领域 “减少资源消耗、优化利用资源”是经济可持续发展战略的重要内容，建设“资 源节约型、环境友好型”社会是加快转变经济发展方式的重要着力点。根据国家 统计局统计数据显示，截止到2 0 1 0 年1 1 月份，中国的年钢产量已经突破7 亿吨， 平板玻璃产量达5 7 7 亿重量箱，铝材产量近2 0 0 0 万吨。上述数据充分表明，我国 目前的资源消耗量巨大。然而，我国目前的资源利用率偏低，以钢材为例：由于 缺乏钢材套料技术和切割焊接经验，我国企业在钢材切割焊接过程中比美国、日 本等发达国家的企业多浪费1 0 的钢材。 日本韩国钢材利用率已达到9 2 9 5 ， 我国造船业目前钢材利用率为8 7 ，而 差距十分明显，造成了巨大的浪费，改 善和提高资源的利用水平，对我们这样一个资源消耗大国，具有重大的经济意义 和社会意义。 实施绿色制造与低碳制造是制造业减少资源消耗强度的重要途径，减少物料 消耗和能源消耗是企业实施绿色制造的具体手段。如图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 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 在给定的n 维几何空间g ( n ) 内，寻找一种最优的布局方案将尽可能多的待排样 空间子集 r 。，r 2 ，r 。) 填充到g ( n ) 内，优化目标是使得排样后子集所占用的空间最大，即 几何空间g ( n ) 的利用率最大。需要满足的应用条件为被排样的空间子集尺，必须位于g ( n ) 内，即r ，g ( ，z ) ( f = 1 , 2 ，z ) ，且任意两个子集互不重叠，r if 3r j = 痧( f ，j = 1 9 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 重庆大学硕士学位论文1 绪论 1 1 3 优化下料问题的主要应用领域 优化下料问题广泛存在于国民经济的多个行业中，如机械、家具、钢铁、船 舶、车辆、建筑、造纸、玻璃、皮革等。优化排样的核心是在满足工艺条件的基 础上，尽可能地提高原材料利用率，以达到减少材料浪费和节省成本的目的。表 1 1 所示为优化下料问题的主要应用领域3 4 1 。 表1 1 优化下料问题的主要应用领域 t a b 1 1t h em a i na p p l i c a t i o nf i e l do fc u t t i n gs t o c kp r o b l e m 行业名称主要应用问题 机械制造业 家具制造业 建筑业 造纸业 皮革制品业 服装制造业 印刷包装业 微电子 航空航天 钢板、卷材分割，工业用各种钣金件、型材、管材、棒料分割，汽车、 船舶、压力容器等的钢板下料 木制家具的胶合板、木条的分割，金属家具的型材、板材的分割，玻 璃板、石膏板的分割 钢筋、门窗幕墙铝合金型材、钢结构型材分割，建筑用玻璃、金属板、 保温板、混凝土模板裁制 大尺寸纸张原片及卷纸的分割 大尺寸皮革原片上不同形状毛坯的套裁 制衣、制鞋中布匹、皮革等原材料上不同形状毛坯的套裁 包装材料分割，报纸书刊的版面布局 集成电路的布局、电路板的切割 航天器舱室静态布局与动平衡布局 1 1 4 优化下料问题的分类及定义 对优化下料问题的科学分类和准确定义是全面了解和解决优化下料问题的基 础。根据不同的分类标准，优化下料问题有多种分类方法。如图1 2 所示，文献 5 根据是否涉及空间布局问题将优化下料问题划分为狭义优化下料问题和广义优化 下料问题，狭义优化下料问题又分为材料分割和器物填充2 类，材料分割类下料 问题在实际生产中应用较多，如型材、玻璃、皮革分割等，凡是需要从原材料上 切割下零件的下料都属于该类问题；器物填充主要包括车辆装载、容器填充等空 间利用问题。广义优化下料问题按照不同的尺度属性( 金融尺度、时间尺度、重 量尺度、其他尺度) 可划分成4 类，主要包括资金预算、找零、任务调度、队列 平衡、背包问题、内存分配及数据存储等。根据所处的不同空间维度，狭义优化 下料问题又可划分为一维( 条材) 、二维( 板材) 及三维( 装箱) 优化下料问题。 对于研究广泛的二维优化下料问题，文献 6 按照下料零件特点、下料区域、优化 重庆大学硕士学位论文1 绪论 标准和工艺要求对其分类进行了系统研究，根据零件形状可分为矩形下料、规则 多边形( 圆形、三角形等) 下料、不规则多边形下料；根据零件排列方式可分为 方向固定与可旋转下料；根据切割工艺可分为一刀切下料( 剪床下料、玻璃切割) 及正交下料( 线切割、火焰切割、气割) 。 材料分割器物填充 金融尺度时间尺度重量尺度其他尺度 图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 k ，m 种待下料零件的长度分别为 ，z ：，。，各零件的状态量分别为b ，6 ：，b m 。排样目标是在完成所有零件下料 的基础上，使得消耗的原材料长度最少。建立其优化数学模型如式( 1 1 ) 所示， 为不失一般性，假设k 种原材料中有，种原材料无数量限制，则0 n 。 0 0 ， k = 1 , 2 ，k r ：n t = 0 0 ，k = k r + 1 ，k r + 2 ，k 。 k n k 口x 夕玩 ，i = 1 ，2 ，m k = l = l 1 妣 工罗n 。 k = l x o ，且为整数 4 ，k = 1 , 2 ，k 一， 乙 似、 x 一 k 料 i f zmm 重庆大学硕士学位论文1 绪论 其中： z 目标函数( 长度最小) ； 。第k 种原材料的长度； k 原材料的种类； x 在第k 种原材料上的第，种切割方式的使用次数，即用第，种切割方 式切割第k 种原材料的数量； n 。第k 种原材料上可行切割方式总数； b i 第f 种待下零件的状态量； 口第k 种原材料对应的第，种切割方式下第f 种零件的数量； 。第k 种原材料的数量； m 零件种类。 式( 1 1 ) 描述的数学模型是典型的整数线性规划模型，目标函数z 记录下料 过程中原材料的消耗，应用条件则规定了待下料零件在原材料上的合理排布。根 据现有整数线性规划模型的求解算法【7 。8 】，以上不等式方程组理论上可以求得最优 解，但随着下料零件种类的增加，算法求解的计算量将呈指数级增长【9 。10 1 。因此除 零件规模较小的实例外，一般无法在合理的时间内找到最优解。实际应用中常去 掉对变量的整数约束，将其转化为线性规划问题用背包算法进行求解。目前则主 要采用各种启发式排样算法或智能排样算法。 上述数学模型考虑了多种不同规格原材料、部分原材料有数量限制的情况， 对该模型进行适当调整后就能将其转化为特定的一维优化下料问题。当，= k 时， 模型则适合于多种原材料且原材料没有数量限制的一维优化下料问题；当k = 1 时，该模型适合于单一原材料的一维优化下料问题。 二维优化下料问题 二维优化下料问题，又称为板材下料问题，即认为零件与原材料的长、宽均 不相等，按照零件形状的不同，二维优化下料问题可分为矩形零件下料、规则形 状零件( 圆形、三角形) 下料及不规则形状零件下料，其排样时至少需要在2 个 尺寸方向进行考虑。以矩形零件排样为例，该问题可描述为：设有k 种原材料， 第k 种原材料的数量为。，原材料长、宽分别为p ( l 。，) ，p ( l ：，吸) ，p ( l k ，) ， m 种待下料零件的长、宽分别为p ( i 。，w 1 ) ，p ( i ：，w 2 ) ，p ( i 。，w m ) ，各零件的状态量 分别为b ，b ：，b 。排样目标是在完成所有零件下料的基础上，使得消耗的原材料 面积最小，且满足条件：( 1 ) 零件必须包含在原材料内部，即对于任意的零件 p ( i ，) ，在其套裁的原材料p ( l j , ，) 上，满足p ( z ，w f ) p ( l ，) ( f _ 1 , 2 ，m ，j = 1 , 2 ，k ) ；( 2 ) 任意两个零件互不重叠，即p ( i ，w i ) n p ( 1 ，w j ) = 重庆大学硕士学位论文1 绪论 ( f ，j = 1 , 2 ，m ) ，且i j 。将数学模型式( 1 1 ) 中的原材料长度替换为原材料面积 即可建立二维优化下料问题的数学模型，某矩形零件优化排样结果如图1 3 所示。 3 r 3 r u 己 3 r3 r j r 3 r3 r 3 r 3 r2 r 3 r 3 r 2 r 3 r3 r 图1 3 矩形零件优化排样图 f i g 1 3t h e b 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 所示为典型的三 维优化下料问题集装箱装填问题。 匕令i匕令 ，+ 图1 4 集装箱装填问题 f 远1 4c o n t a i n e rp a c k i n gp r o b l e m 每类优化下料问题的应用场合各不相同，但通过上述对每类优化下料问题的 6 够 重庆大学硕士学位论文 1 绪论 描述和定义，可以反映出优化下料问题的共同特征：1 ) 包含两组基本数据，即零 件规格和原材料规格；2 ) 以满足工艺、空间等应用条件为基础，寻求一种合理的 排样布局方案，将所有的零件进行下料，并使原材料的利用率尽可能高。 1 2 优化下料问题的国内外研究现状与发展趋势 1 2 1 优化下料问题的研究现状 上世纪6 0 年代初，g i l m o r e 和g o m o r y 两位学者相继发表了数篇文章【1 1 。1 4 】，着重 论述了一维下料问题的方案，并且提出了二维下料优化问题。此后，优化下料问 题引起了人们的研究兴趣。近四、五十年来各行各业的专家学者针对这一问题的 发表了大量研究著作，提出了各种各样的针对下料问题的数学算法。起初是以启 发式算法和智能算法为主。启发式算法是一个基于直观或经验构造的算法，在可 接受的计算时间、占用空间等条件下求出优化问题的可行解，该可行解与最优解 的偏离程度不一定事先可知【l5 1 。启发式算法通过寻找最优解的近似解，使得在可 接受的开销下得到问题的一个满意解，基于不同的规则构造出不同的启发式排样 算法【1 6 之3 1 。 文献 1 6 将来自有经验的排样师的启发式规则以及冲孔、剪床下料等的限制条 件存储在知识库中，通过知识的重用指导模型生成排样图案组合。 文献 1 7 1 针对一维下料的整数双线性规划问题，提出一种基于整数规划问题的 局部搜索启发式算法，提高了列生成算法的质量。 文献 1 8 根据某大型钢结构生产企业提出的型材下料时既要切割又要焊接的 生产工艺问题，构造出一种可焊接的一维排样问题的启发式算法。该算法以矩阵 来表述问题的数学模型，通过直接在矩阵上进行操作来求解问题的可行解以及优 化该可行解。 随着现代优化理论研究的不断深入，尤其是智能优化算法的出现，为解决优 化下料问题提供了新的思想【2 4 弓5 1 ，智能算法也被称为现代启发式算法。智能算法 主要包括遗传算法( g e n e t i c a l g o r i t h m ，g a ) 、模拟退火算法( s i m u l a t e d a n n e a l i n g ， s a ) 、禁忌搜索算法( t a b us e a r c h ，t s ) 、人工神经网络( n e u r a ln e t w o r k s ，n n ) 等，这些算法相互的混合以及与普通排样算法的结合正成为优化下料算法研究的 执占 、j 、u 文献 2 4 对遗传算法在优化下料问题中的应用进行了总结，对遗传算法中的编 码、遗传算子和解码方法进行了论述。 文献 2 5 提出了结合遗传算法和模糊控制的新的排样算法，降低了遗传算法的 适应度函数值，获得了较好的排样效果。 文献 2 6 针对不规则件排样问题，提出一种应用粒子群算法优化求解的方法。 重庆大学硕士学位论文 1 绪论 首先以零件的入排交换序列和角度变异序列作为粒子运动速度构造粒子群算法， 然后运用剩余矩形动态匹配算法实现解码和局部寻优，并结合不规则件的正交靠 接算法实现自动排样。 文献 2 7 1 针对一维优化下料问题，将基于群体的编码方法与遗传算法相结合， 设计了一种适用于一维优化下料问题的编码方法，修改了经典遗传算子的操作方 法，提出了降序最佳置换方法。引入最佳配合、优先配合降序局部搜索算法，建 立了求解一维优化下料问题的复合遗传算法。 上述国内外专家学者对优化下料问题的研究偏重于优化下料算法，其算法方 面的研究已经相当深入。线性规划方法、动态规划方法、禁忌搜索算法、模拟退 火算法、遗传算法、蚁群算法等都被用于求解优化下料问题，但优化下料问题不 是一个纯粹的数学问题，仅从算法的角度对优化下料问题研究是片面的，其实际 应用场合很有限。 针对一些具体的下料问题，国内外专家学者对一种或几种应用状态下的优化 下料问题进行过一些研究，文献 3 6 提供了一种简化下料方式的算法，并将下料方 案的可操作性作为应用状态之一，提高了下料的可操作性。文献 3 7 认为下料是一 个持久的过程，优化目标不能局限于某次订单的状态，而应该是以在满足交货期 应用前提下的下料余料最少为目的。文献 3 8 将优化下料问题和批量计划问题 ( l o t s i z i n gp r o b l e m ) 相结合，建立了切割余量应用、库存应用、安装费用应用下 的数学模型，并通过网络最短路径算法求解，获得了比单独解决各个应用问题更 优的效果。文献 3 9 提出了一种考虑加工时间、刀具磨损、机器限制、交货期限制 等应用条件，以按时交货和余料最少为优化目标的1 5 维的多原材多目标优化下料 数学模型，并采用不完全枚举法求解，认为能够获得材料利用率高且便于加工的 下料方案。文献【4 0 】针对多原材料多零件的大规模优化下料问题进行研究，提出采 用分组优化的策略，以下料零件特征为依据对零件进行分组，将大规模问题转化 为小规模问题，降低了问题求解难度；文献 4 1 4 2 1 认为通过网络整合各种优化技 术和系统能够获得更佳的实际应用效果，并分别提出一种基于i n t e m e t 的二维优化 下料解决方法和基于w e bs e r v i c e 的网络化优化下料方法。 这些研究都是针对某个具体下料问题进行的，考虑了优化下料的一种或者几 种应用状态，但缺乏对优化下料复杂应用状态问题的系统性研究和考虑，有些情 况下会影响到优化下料整体效果，实际下料过程某个应用状态一旦发生变化，研 究结论就很难应用。 在优化下料应用系统方面，国内外的众多科研机构和公司开发出了许多实用 的优化下料系统，并在生产中得到了广泛应用。国外下料软件发展较早，其功能 强大，适用范围较广，如m t cs o t t w a r e 的p r o n e s t 、美国s i g m a t e k 公司的 重庆大学硕士学位论文1 绪论 s i g m a n e s t 及英国r a d a n 公司的n e s t i n g n e s t i n g 等。国内如清华大学、华中科 技大学、重庆大学等高校也一直从事优化下料技术的理论研究与系统开发，如重 庆大学与其他单位早期联合开发的“建筑金属结构企业计算机辅助设计和生产管 理集成系统( b k c a d p m ) ”具有条材板材自动排样功能；国内多家公司也开发出 了针对不同行业的下料软件，如北京金土木软件技术有限公司的平法钢筋下料软 件，北京斯达峰控制技术有限公司的s t a r c a m 绘图套料软件及创盈、蓝科、长 风门窗下料系统等。 这些系统能够解决大部分企业的优化下料问题，为企业降低资源消耗、提升 生产效率做出了贡献，从课题组长期从事优化下料研究和应用的实践经验发现， 因没能及时根据企业的应用状态变化进行功能扩充，导致部分优化下料系统与企 业生产实际不符，从而影响了应用效果。 1 2 1 现有一维优化下料技术不足之处 综上所述，国内外对优化下料技术的研究大都局限在算法改进和创新方面， 由于优化下料问题的n p 复杂性，至今未找到能在多项式时间内解决优化下料问题 的算法；少数研究把优化下料技术和其它技术相结合，探索新的优化下料处理方 法，取得了一定成果，但综合应用效果仍然不理想；基于上述研究的优化下料系 统在诸多领域解决了下料企业的优化下料问题，但随着新的下料状态的出现，这 些系统则显出不足之处。现有一维优化下料技术研究及应用不足之处主要表现在： 1 ) 就算法的角度对优化下料问题研究比较多，而缺乏从大系统的角度综合考 虑下料问题所有可能涉及的应用状态及其对优化下料的影响，制约着优化下料的 整体效果。 2 ) 对某种或某几种应用状态下具体的优化下料问题研究比较多，但缺乏对实 际优化下料问题从应用状态抽象、应用状态模式定义、建立或选择数学模型到模 型求解的一般机理的研究，现有研究显得很零散，研究结论只能针对特定的优化 下料问题，难以移植和推广。 3 ) 优化下料企业的实际生产情况在变，而大多数优化下料系统不能及时更新， 导致现有系统与实际应用脱节。 1 3 课题来源和本文研究的目的意义 1 3 1 课题来源 本论文的工作主要是基于作者参与的以下研究项目进行的： 国家自然科学基金面上项目“优化下料的复杂约束状态问题及其系统处理 方法研究”( 5 0 9 7 5 2 9 9 ) ，2 0 1 0 年1 月2 0 1 2 年1 2 月。 9 重庆大学硕士学位论文 1 绪论 1 3 2 本文研究的目的意义 针对实际优化下料过程中存在的复杂应用状态问题，传统的优化下料方法仅 从算法的角度来对优化下料问题进行研究是片面的，其实际应用场合很有限。随 着优化下料企业的发展，企业对优化下料问题提出了更多的下料需求，需要探求 符合企业实际需求的优化下料方法，因此，本文围绕支持复杂应用状态的一维优 化下料问题以及相关实用技术展开研究。首先通过对一维优化下料过程复杂应用 状态进行分析，建立了一维优化下料复杂应用状态结构模型以及一维优化下料复 杂应用状态关联与影响评价模型；对复杂应用状态下一维优化下料系统处理方法 进行研究，建立了支持复杂应用状态下一维优化下料问题的优化决策过程模型， 为解决任意应用状态下的一维优化下料问题提供了基础，然后针对大规模下料方 式给优化下料问题带来的原材料利用率和时间求解效率的矛盾问题进行了深入研 究，提出了原材料不确定状态下的一维优化下料实用技术，开发了相应的软件产 品，并在有关企业中得到推广应用，从而有效降低应用企业的物料资源消耗，减 少生产制造成本，提高企业的综合竞争力。 1 4 本文的主要研究内容 论文首先分析了国内外一维优化下料技术的研究现状，针对现有研究的不足 和企业急需解决的优化下料问题，建立了一维优化下料复杂应用状态结构模型以 及一维优化下料复杂应用状态关联与影响评价模型；对复杂应用状态下一维优化 下料系统处理方法进行研究，建立了支持复杂应用状态下一维优化下料问题的优 化决策过程模型。 接着，在分析复杂应用状态一维优化下料系统特点的基础上，提炼总结了系 统的应用需求，建立了支持复杂应用状态下一维优化下料系统的结构体系和功能 体系。 然后，针对大规模下料方式给优化下料问题带来的原材料利用率和时间求解 效率的矛盾问题进行了深入研究，提出了一种原材料不确定状态下的一维优化下 料方法。该方法首先根据订购件和标准件的下料特性，建立原材料订购件与标准 件混合下料的优化数学模型；然后提出并实现了一种基于零件下料配合特征的有 限递进复合求解方法，并通过应用实例证明了该方法的可行性和有效性。 最后，以国家8 6 3 c i m s 目标产品“建筑金属结构计算机辅助设计与生产管理集 成系统”中的一维优化下料子系统为基础，基于上述研究结论开发了支持复杂应用 状态的一维优化下料系统。 1 0 重庆大学硕士学位论文1 绪论 1 5 本章小结 本章首先对优化下料问题的主要应用领域及其分类与定义进行了论述。然后 对与本文研究工作相关领域的国内外研究现状进行了分析，并总结了现有优化下 料理论研究、下料软件存在的问题及发展趋势。最后指明了本文研究工作的来源， 阐述了本文研究的目的意义和主要内容。 重庆大学硕士学位论文 2 一维优化下料系统复杂应用状态研究 2 一维优化下料系统复杂应用状态研究 2 1 引言 实际的优化下料过程是包括很多阶段的，如原材料采购阶段、下料任务生成 阶段、优化排样阶段、下料切割阶段等，而每个阶段涉及到很多应用状态，彼此 之间有着关联、涉及环节多、组合情况多、对优化下料问题的影响性质也不一样。 现有研究都是针对特定应用状态组合下具体优化下料问题及其算法的解决，而在 企业实际下料问题处理中，应用状态本身可能是变化的，应用状态模式( 应用状 态的组合关系) 可能是多样的，应用状态模式的多样性和应用状态本身的变化性 导致既有优化下料处理方法可能不适合或者为了适应某个已有的优化下料处理方 法而减少对应用状态的考虑( 如：不考虑市场原材料供应的规格种类数) ，这都将 影响优化下料技术应用的整体效果。为此，本章将建立了一维优化下料复杂应用 状态结构模