（控制科学与工程专业论文）智能优化排样技术研究.pdf

浙江人学博士学位论文 摘要 计算机辅助优化排样问题就是将一系列形状各异的零件排放在给定的 材料上，找出零件的最优排布，使得给定材料的利用率最高，以达到节约材 料，提高效益的目的。从数学计算复杂性理论看，优化排样问题属于具有最 高计算复杂性的n p 完全问题，至今还无法找到解决该问题的有效多项式时 间算法。传统的排样工作都是人工依靠经验进行的，时问氏并且效果不理想。 由于生产实际的需要，人们迫切需要利用现代科技来解决这一问题。智能优 化算法作为现代信息技术，已被广泛应用于许多领域。本文以智能优化算法 为基础，提出了几种用于解决优化排样问题的新方法，实验结果证明本文提 出的方法是有效的。本文的主要工作和创新点如下： ( 1 1 针对矩形件排样问题，本文在建立其数学模型的基础上，将小生境 遗传算法应用于计算机辅助排样领域，提出了一种改进的解码算法高度调 整法，将高度调整法和小生境遗传算法相结合，用于求解矩形件排样问题。 该方法首先将矩形件的排样问题转化为便于优化求解的排列问题，然后应用 小生境遗传算法的全局优化概率搜索能力进行优化求解，优化计算过程中应 用高度调整法将排样序列转化为排样图。用该算法对文献中的两个算例进行 了求解，取得了很好的排样结果。 ( 2 ) 提出一种应用粒子群算法优化求解矩形件排样问题的方法。该方法 对矩形件的排样位置直接进行编码，以零件左下角的位置坐标和零件的长和 宽来确定零件的排样位置，然后用粒子群优化算法对整个解空间进行高效搜 索，在进化计算过程中应用了自适应调整规则，最终可获得材料利用率很高 的排样结果。排样实例表明，该优化排样算法是有效的，具有广泛的适应性。 ( 3 ) 将模拟退火算法和粒予群算法相结合，提出了一种基于模拟退火的 粒子群算法。并对其巾的变异算法进行了改进，提高了算法的收敛速度和精 度；对包络矩形求取算法进行了改进，减少了计算量，提高了算法的运算速 摘要 度。应用该算法求解二维不规则零件排样问题，首先利用改进的包络矩形算 法求取不规则零件的包络矩形，将二维不规则零件的排样问题转化为矩形件 的排样问题，然后应用混合算法进行优化求解，在求解过程中应用自适应调 整规则对零件的排样位置进行微调。排样结果表明该算法是有效的。 ( 4 ) 在综合利用计算几何、计算机图形学、组合优化的知识的基础上， 提出了基于临界多边形和水平线扫描算法的二维不规则零件排样算法。针对 排样零件的轮廓形状，逐步分析了两个凸多边形、一个凸多边形和一个凹多 边形以及两个凹多边形的临界多边形求取方法；对多边形合成算法、多边形 面积求取算法和水平线扫描算法进行了介绍，并对其中的关键算法进行了改 进，把它们和临界多边形算法相结合以解决不规则零件排样问题。 ( 5 1 进行了计算机辅助优化排样系统的设计。分析了排样系统的需求情 况，规划了系统的基本功能，讨论了系统中各模块的划分和设计。 关键词：优化排样；小生境遗传算法；高度调整法；粒子群算法；模拟退火 临界多边形；水平线扫描算法 浙江大学博士学位论文 a b s t r a c t t h ea i mo ft h ec o m p u t e ra i d e do p t i m a ll a y o u to ft h e p a r t sw i t hd i f t b r e n t s h a p e si s t of i n dt h ea r r a n g e m e n to fp a r t sa n dp r o d u c i n gt h el e a s tw a s t e t h e p r o b l e mo fo p t i m a ll a y o u tb e l o n g st o t h en p c o m p l e t e p r o b l e mw i t ht i p t o p c a l c u l a t ec o m p l e x i t y , a n dc a n n o tf i n dt h ee f f e c t i v ep o l y n o m i a la l g o r i t h mu pt ot b e p r e s e n t c o n v e n t i o n a ll a y o u tw o r k sa l la d o p tm a n u a lo p e r a t i o nt h a th a v em a n y s h o r t c o m i n g ss u c ha sl o wy i e l d ，i n e f f i c i e n ta n dl o n gt i m ec o n s u m i n g p e o p l ec r yf o r as o l u t i o nb yt h em o d e ms c i e n c ea n dt e c h n o l o g yb e c a u s eo ft h en e e do fp r o d u c t i o n i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m sh a v eb e e nu s e de x t e n s i v e l yi nm a n yd o m a i n s i n t h i sp a p e r , t h ea p p l i c a t i o no fi n t e l l i g e n to p t i m i z a t i o na l g o r i t h m si no p t i m a ll a y o u t w a sm o r ei n v e s t i g a t e d s e v e r a ln e wm e t h o d sw e r ep r o p o s e df o rt h ep r o b l e mo f o p t i m a ll a y o u t t h em a i nw o r k sa n di n n o v a t i o np o i n t sa r el i s t e da sf o l l o w s ： ( 1 ) i no r d e rt os o l v et h ep r o b l e mo fr e c t a n g u l a rp a r t so p t i m a ll a y o u tw i t h d y n a m i cc o n s t r a i n t s ，b a s e do nt h em a t h e m a t i c a lm o d e l ，an o v e lr e c t a n g u l a ro p t i m a l l a y o u tm e t h o di sp r o p o s e db a s e do nn o v e ld e c o d i n ga l g o r i t h m h e i 【g h ta d j u s t m e n t a l g o r i t h m ( h a a ) a n dn i c h eg e n e t i ca l g o r i t h m ( n g a ) t h ep r o b l e mo fr e c t a n g u l a r o p t i m a ll a y o u tc a nb e t r a n s l a t e di n t o o p t i m i z a t i o np r o b l e m i nt h ef i e l do f p e r m u t a t i o np r o b l e m ，a n dt h e nt h en g ai su s e d t os e a r c ht h es o l u t i o ns p a c e e f f i c i e n t l yi no r d e rt of i n dt h eo p t i m a ls o l u t i o no f t h el a y o u t h a ai su s e dt od e c o d e p e r m u m t i o no fr e c t a n g l e st op a c k i n gp a r e md u r i n gt h ep r o c e d u r eo fo p t i m i z a t i o n t h ef e a s i b i l i t yo f t h ep r o p o s e dm e t h o di sd e m o n s t r a t e db yt w on u m e r i c a le x a m p l e s ( 2 ) an o v e lr e c t a n g u l a ro p t i m a ll a y o u tm e t h o du s i n gp a r t i c l es w a r m o p t i m i z a t i o n ( p s o ) i sp r o p o s e d t h em e t h o dc o d i n gd i r e c t l yw i t ht h ep o s i t i o n so f t h er e c t a n g l e s ，d e t e r m i n i n gt h ep a c k i n gp o s i t i o no fp a r t sb yu s i n gt h el e f t l o w e r c o r n e a lp o s i t i o nc o o r d i n a t e ，w i d t ha n dl e n g t ho ft h ep a r t s ，a n dt h e nt h ep s ow i t h t h es e l f - a d a p t i v em o d u l m er e g u l a t i o ni su s e dt os e a r c ht h es o l u t i o ns p a c ee f f i c i e n t l y a b s t r a c t i no r d e rt of i n dt h eo p t i m a ls o l u t i o no ft h el a y o u t t h ea v a i l a b i l i t yo ft h e p r o p o s e d m e t h o di sd e m o n s t r a t e db yt h el a y o u te x a m p l e ( 3 ) an o v e lp a r t i c l es 、v a r mo p t i m i z a t i o na l g o r i t h mb a s e do nt h es i m u l a t e d a n n e a l i n ga l g o r i t h m ( p s o s a ) i sp r e s e n t e d t h ec r o s s o v e ro p e r a t i o na n dc a u c h y m u t a t i o no p e r a t i o nw e r eu s e dt oe n h a n c et h ec o n v e r g e n c ep e r f o r m a n c ea n ds p e e do f t h ea l g o r i t h m t h ep r o p o s e da l g o r i t h mw a su s e dt os o l v et h ep a c k i n gp r o b l e mo f t w o d i m e n s i o n a li r r e g u l a rp a r t s f i r s t l y , t h ep r o p o s e dm e t h o dc o n v e r t st h ep a c k i n g p r o b l e mo ft w o d i m e n s i o n a li r r e g u l a rp a r t si n t or e c t a n g u l a rp a r t sp a c k i n gp r o b l e m b yc a l c u l a t i n gt h es u r r o u n d i n gr e c t a n g l eo fi r r e g u l a rp a r t s s e c o n d l y , t h ep r o p o s e d a l g o r i t h mw a su s e dt os e a r c hf o rt h eo p t i m a ls o l u t i o no ft h el a y o u t t h es t r a t e g yo f s e l f - a d a p t i v em o d u l a t i o ni su s e dt oa d j u s tt h el a y o u tp o s i t i o no fe a c hr e c t a n g u l a r p a r td u r i n gt h ep r o c e d u r eo fo p t i m i z a t i o n s o l u t i o n so ft w on u m e r i c a le x a m p l e s s h o wt h ee f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h m ( 4 ) an o v e lt w o d i m e n s i o n a li r r e g u l a rp a r t sp a c k i n gm e t h o du s i n gn of i t p o l y g o nf n f p ) a n dh o r i z o n t a ll i n es c a na l g o r i t h mi sp r e s e n t e d a i m i n ga tt h e c o n t o u ro ft h ep a c k i n gp a r t s ，t h em e t h o d st og a i nt h en f pa r ed i s c u s s e ds t e pb ys t e p ， f r o mt w oc o n v e xp o l y g o n s o n ec o n v e xp o l y g o na n do n ec o n c a v ep o l y g o nt ot w o c o n c a v ep o l y g o n s a n dt h e nt h ep o l y g o nc o m p o s ea l g o r i t h m ，p o l y g o na r e a a l g o r i t h ma n dh o r i z o n t a ll i n es c a na l g o r i t h mw e r ec o m b i n e dw i t l lt h en f p t os o l v e t h ep r o b l e mo f t w o d i m e n s i o n a li r r e g u l a rp a r t sp a c k i n g ( 5 ) t h ed e s i g no fc o m p u t e ra i d e do p t i m a ll a y o u ts y s t e mi sp r o p o s e d t h e d e m a n d ，t h eb a s i cf u n c t i o na n dt h em o d u l eo f t h el a y o u ts y s t e ma r ed i s c u s s e d k e y w o r d s ：o p t i m a ll a y o u t ；n i c h eg e n e t i ca l g o r i t h m ；h e i g h t a d j u s t m e n ta l g o r i t h m ； p a r t i c l es w a r mo p t i m i z a t i o n ；s i m u l a t e da n n e a l i n g ；n of i tp o l y g o n ；h o r i z o n t a ll i n e s c a na l g o r i t t u n 浙江大学博士学位论文 第1 章绪论 摘要：总结了计算机辅助优化排样问题的主要内容、分类和优化排样评价标准， 分析了本论文的研究背景和意义，目前国内、外在计算机辅助优化排样方面的 研究现状及发展趋势等。 1 1 计算机辅助优化排样问题概述 1 1 1 优化排样问题的基本概念 首先从一+ 个简单的一维排样问题引j 叶j 优化排样问题的基本概念。下面这个 问题中：从长管中切割出一定长度的散热单元短管”1 ，如图1 - 1 所示，原料长管 原料长曹( 长9 8 ) 9 9 所需要的小_ f 芒寸管( 长5 到4 6 ) 口 口 口 口 56 二二二二二二二二二 二二二二二= 二二二 二二二二二二二二二二 d 6 切割过程将小尺寸管组台成可切善l 胀度并从原料长 ! 里! 三三三三三三三? t ，- 、1 二二2 二5 二二2 二5 二二二二= 4 1 4 二二二 由 图l l& 管切割问题 第1 章绪论 及需要的小单元散热管构成了切割问题的基本数据。看待切割问题有两个角度， 是可以看成是用原料长管来生产小单元散热管，使得原料的浪费最少；另一 个也可以看作是生产这些小单元散热管，最少需要使用多少数量的原料长管。 长管切割属于简单的一维排样，但也具备了排样问题的基本要素。一般而 言，排样问题具有两个共同特征： ( a ) 有两组基本数据，数据元素定义了空间中确定形体的几何表达：大尺 寸。几何原材料对象和小尺寸几何零件列表。 ( b ) 排样过程实现小尺寸对象的几何组合在大尺寸对象上排放的布局方 案。残余的小块，例如，布局方案中无法排放小尺寸对象的小块区域，通常称 之为“切割损耗”( t r i ml o s s ) 。 图1 2 通过典型的二维矩形排样图直观地说明排样问题的基本构成。 给定图形定义的大尺寸几何原材科对象 凰匿圈 圈匿盈一 捧样方案图示 豳函 图1 - 2 排样问题的基本构成 计算机辅助优化排样就是寻求某种优化的布局方式，使平面区域的材料面 积利用率较高。许多工业问题如卷材、玻璃、印刷业等的切割，服装、皮革等 翻翻圈团 浙江大学博士学位论文 的剪裁，货物装箱等均属此类排样问题，是典型的组合优化问题，具有很高的 计算复杂性。因此对规模较大的排样问题，不但手工排样不可能做到真i f 的优 化，即使采用计算机辅助排样也必须开发高效的算法才能实现利用率相对较高 的优化排祥和切割。 1 - 1 2 优化排样问题主要应用领域 在国民经济许多行业中，都会遇到材料分割问题。计算机辅助优化排样的 作用，就是生成高利用率的材料分割排样方案，网此，凡是需要进行材料分割 的行业，都可以应用计算机辅助优化排样，达到提高生产率、节约材料、降低 成本的目的。 表1 1 所示为材料分割问题较多的乱二业，这些行业构成了计算机辅助优化 排样的主要应用领域2 1 1 3 1 。 表1 1计算机辅助优化排样的主要应崩领域 行业名称材料分割问题 服装制造业 皮革制品业 术材加工业 家具制造业 纸制品业 体育用品帝造业 塑料制品业 金属制胁l e 普通机械制造业 # 、i k 设备制造业 交通运输设备制造业 服装生产过程中的布匹等材料的分割 将人张皮革分割成各种形状的毛坯 圆木、力木或胶合板的分割 木制家具的胶合板分割；金属家具的型材、管材和板材分割 将成卷的纸分割成小块 制造体育器材的型材、管材和板材等金属材料的分割 塑料板材、符材和棒材的分割 模具、金属包装品、金属fj 窗等金属制品制造过程中，对型 材、棒材、卷木j 、板材等进行分割。 制造过程中型材、管材的锯切，中厚钢板的气割，金属薄板 的剪切等 备类专用设备制造过程中型材、管利、棒材的锯切，金属薄 板的剪切等 铁路运输设备、汽1 二、电车、船舶、航空航天器等制造行业 的金属利料分割问题 第1 章绪论 电气机械制造业电机制造业的硅钢片f 料，各种金属材料的分割 1 1 3 优化排样问题的类型 对排样问题的科学分类和标识是全面了解和解决排样问题的基础。根掘不 同的分类标准，排样问题可以分为很多类：按形状分为矩形、凸多边形、规则 多边形、任意多边形等：按单元排列方式分固定方向、可旋转等；按照排样要 求分为在定宽无限长板材上求最，j 、排样高度、在无限多定宽定高板材上求最少 板材个数以及在不规则材料e 求最大材料利用率等；还有其他多种分类方式， 形成各式各样的排样问题。可以说，排样问题在生活中随处可见，应用广泛。 文献 1 对排样问题进行了概括，按照空问尺度分为狭义切割排样问题和抽象切 割排样问题，如图卜3 所示。 二至亟口 、 索、 图卜3 排样问题概括 其中狭义切割排样问题可按零件和材料的形状分为以下几种类型0 3 1 ： 1 一维排样问题 维排样问题，又称为线材排样问题，是指在排样时只需要考虑一个方向 的尺寸。例如，将较长的型材、管材等，分割成各种较短的毛坯。典型的应用 4 圈 浙江大学博+ 学位论文 领域包括门窗、金属制品、机械设备、专用设备、交通运输设备、电气机械等 制造行业，这些行业所属企业在制造过程巾，需要将线材切割成较短的毛坯， 用于生产产品。 2 _ 二维排样问题 二维排样问题，又称为板材排样问题，是指将板材分割成各种形状的毛坯。 这些毛坯可以是矩形、梯形、三角形等规则形状，也可以是不规则形状。典型 的应用领域包括木材制品业、家具假造业、金属制品业、普通机械制造业、交 通运输设备制造业、电气机械制造业等行业。 另外一种比较特殊的二维排样问题，卷材排样问题，又称为一一维半排样问 题，是指被分割的材料宽度较小，长度很大，排样时可以将长度看作无限长。 布匹、纸张、塑料、金属薄板等，都可以用卷材的形式供应。典型的应用领域 包括服装、纸制品、塑料制品、电机等制造行业。当金属薄板的厚度在o 5 m m 以下时，经常以卷材的形式供应。在分割过程中，通常先沿着卷材的长度方向、 将其分割成很长的条带，然后再将条带分割成较小的毛坯。 3 j 维排样问题 在三维排样问题中，材料和毛坯都必须按照立体形状处理。典型的应用领 域包括木材加工业，在那里需要将圆木分割成尺寸较小的方木。圆木的长度、 弯度等都可能不i 司，但方木的尺寸要求是规则的。因此需要确定分割方案，使 圆木分割后所产生的方水价值尽可能大。 1 1 4 优化排样方案质量的评价 1 下料利用率 材料切割是根据排样方案进行的，切割后产生的毛坯供制造产品使用。因 此经常使用下料利用率，衡量排样方案的质量。 对于线材排样问题，下料利用率按卜- 式计算： 下料利用率= ( 毛坯的总长度所耗线材的总长度) x1 0 0 浙江大学博+ 学位论立 领域包括f j 窗、金属制品、机械设备、专_ | = j 设备、交通运输设备、电气机械等 制造行业，这些行业所属企业在制造过程巾，需要将线材切割成较短的毛坯， 用于生产产品。 2 二维排样问题 二维排样问题，又称为板材排样问题，是指将板村分割成各种形状的毛坯。 这些毛坯可以是矩形、梯形、三角形等规则形状，也可以是不规则形状。典型 的应用领域包括木材制品业、家具假造业、金属制品业、普通机械制造业、交 通运输设备制造业、电气机械制造业等行业。 另外一种比较特殊的二维排样蒯题，卷材排样闯题，又称为一维半排样问 题，是指被分割的材料宽度较小，长度很大，排样时町以将长度看作无限长。 布匹、纸张、塑料、金属薄板等，都可以用卷材的彤式供应。典型的应用领域 包括服装、纸制品、塑料制品、电机等制造行业。当金属薄扳的厚度在0 5 m 以下时，经常以卷材的形式供应。在分割过程中，通常先沿着卷材的长度方同、 将其分割成很长的条带，然后再将条带分割成较小的毛坯。 3 二三维排样问题 在i 维排样问题中，材料和毛坏都必须按照立体形状处理。典型的应用领 域包括木材加1 ：业，在那里需要将网小分割成尺寸较小的方木。圆术的长度、 弯度等鄯可能不j 司，但力木的尺寸要求是规则的。因此需要确定分割方案。使 圆木分割后所产生的方木价值尽可能大。 1 1 4 优化排样方案质量的评价 1 下料利用率 材料切割是根据排样方案进行的，切割后产牛的毛坯供制造产品使用。因 此经常使用下料利用率，衡量排样方案的质量。， 对于线村排样问题，下料利用率按r 式计算： 下制利用率= ( 毛坯的总长度所耗线材的总长度) 1 0 0 f 料利用率= ( 毛坯的总长度所耗线材的总长度) 1 0 0 第1 章绪论 对于卷材或板材排样问题，下料利用率按下式计算： 下料利用率= ( 毛坯的总面积所耗板材的总面积) 1 0 0 如果被切害u 材料的质地均匀，可统一按下式计算： 下料利用率= ( 毛坯的总重量所耗材料的总重量) 1 0 0 2 最优排样方案 所谓“最优排样方案”，是指下料利用率最高的排样方案：所谓“近优排 样方案”是指排样方案的下料利用率接近最高。般来说，最优排样方案是很 难得到的平时所说的优化方案都是指近优排样方案。 总之，优化排样方案质量与多方面因素相关，但人们最关心的还是下料利 用率。它主要受两个方面因素影响：零件本身的结构和形状，如零件本身不 规则程度高、存在内孔等，将不可避免地产生一部分废料：工艺因素，包括 加工方式和排样方案等，必然会形成不能再加工的搭边、小块边角料和细窄长 条等废料。当然以上仅仅是从理论上区分废料，实际生产中往往混合在一起， 很难具体区分的。工艺因素引起的材料损耗是可以通过改进工艺而不断降低的。 排样问题研究的就是如何通过优化排样策略，一方面尽量避免工艺性废料，另 方匝通过运用合理的优化排样策略来降低零件本身形状不规则性所带来的影 响，提高材料利用率。 1 2 计算机辅助优化排样问题研究背景和意义 计算机辅助优化排样问题就是将一系列形状各异的零件排放在给定的材 料f 二，找出零件的最优排布，使得给定材料的利用率最高，以达到节约材料， 提高效益的日的。排样问题广泛应用在机械制造、轻工、服装和印刷业排版等 r 业中。由于材料费用在产品成本中占很大比例，比如在冲压零件的生产成本 中，丰要包括材料费、加工费和模具费，其中，材料费用通常占总成本的6 0 以l 【4 】；还有一些行业，材料非常昂贵，如汽车制造业，所采用的是比较昂贵 的薄钢板。因此材料的节约对于降低整个行业的制造成本有重要的影确，特别 6 浙江大学博士学位论文 是在大批量生产中，即使将材料利用率提高1 ，也可以带来显著的经济效益。 但是，在很多企业，仍然是在没有排样图的情况下进行人工排样，排样技 术人员仅仅凭借自己的经验自由地在材料上排样，一般排出来的并不是最优的 方案，并且材料浪费很多；有些企业，即使有排样图，但是一方面排样图是人 工绘制，费时费力，效率低下，另一方面也不能做到最优化排样，材料利用率 仍然不高。 计算机和计算机辅助技术的应用和发展，大大提高了一l ：作效率和质量，使 得许多人工难以完成的工作成为可能一e 世纪四十年代以来，人们便尝试着提 出各种理论，设计不同的计算方法来解决计算机辅助优化排样问题。优化排样 问题实际上是一个十分困难的问题，从数学计算复杂性理论看，它属于具有最 高计算复杂性的类问题n p ( 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 ，即非确 定型的多项式算法) 完全问题，也就是说在一般情况下，即使是使用很快的计 算机，在人们可以接受的时问内也不太u f 能求出这类问题的最优解。另一方面， f 】于实际生产的需要，人们又迫切需要利用现代科技刈这一问题给出一个能满 足生产需要的求解方法。这些方法应该是能以较高的计算速度求出一个近似的 解。所谓近似的解是指虽然不是最优解，但接近最优解，并且要比人f 排样的 效果好，能达到或超过人们所期望的材料利用率。 开发、应用计算机辅助优化排样系统的意义pj ，可以归纳为：通过节约材 料、减少排样工作虽和化简切割工艺，最终达到降低产品成本的目的。 1 节约材料，提高经济效益 人工排样受人的工作态度、能力等主观因素所限制，很难给出材料利用率 最高或者接近最高的排样方案。应用计算机辅助优化排样，u r 以充分发挥计算 机强人的计算能力，经过大量排样方案的比较，选出材料利用率最高或者接近 最高的排样方案，以达到节约材料的目的。 2 减少排样下作量，加快排样速度 人r 排样时，为了得到一个较好的排样方案，往往需要长时间的反复r 作。 第1 章绪论 而计算机辅助排样，则可以在非常短的时间内完成排样，并且得到高质量的排 样方案。 3 化简切割工艺，减少切割工作量 排样时经常遇到这样的情况，存在许多材料利用率接近的排样方案，称其 中材料利用率最高的排样方案为最优排样方案。应用计算机辅助排样，可以在 大量的达到最优，或接近最优的排样方案中，选择切割工艺尽可能简单的排样 方案，减少切割工作量。 1 3 计算机辅助优化排样问题国内外研究现状与趋势 1 3 1 优化排样问题的研究现状 国外有关下料排样问题的研究起步比较早。最早关于排样的文章是前苏联 人k a n t o v o r i c h 在1 9 3 9 年发表的【5 1 ，讨论一维下料问题。五十年代中期，p a _ u u 【6 1 、 e i s e m a n n t j 、h e r r m a n n 和v a j d a 8 1 率先提出用线性规划( l i n e a rp r o g r a m m i n g ) 方 法解决印刷和造纸2 1 2 、1 k 的矩形件排样问题，但材料利用率不高。g a r e y 和 j o h n s o n 9 i 证明用数学规划( 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 j o l 1 1 脾】【13 发表了四篇著名的文章， 提出了一维下科方案和二维排样问题。7 0 年代至今，许多学者对排样问题进行 了大量的研究，取得了一定的成果。但排样问题为n p 完全问题，复杂难解； 同时由丁排样时存在各种限制条件，因此至今也没用通用的标准方法来进行求 解。由于排样问题的复杂性和广泛性，在1 9 8 8 年的p a r i s e u r o t i m s 国际会 议上，专门成立了下料问题兴趣小组e s i c u p l l 4 1 ( e u r os p e c i a li n t e r e s tg r o u po n c u t t i n ga n dp a c k i n gp r o b l e m ) 。 l 自于研究矩形件排样既可以直接解决矩形件排样问题，也可以作为解决二 维不规则零件排样问题的基础( 以包络矩形法将不戏则零件排样问题转换为矩 浙江大学博士学位论文 形件排样问题) ，所以一直是众多学者研究的热点，有大量的研究成果出现 | 1 5 】【1 7 1 【1 8 i 。 启发式算法在排样问题求解中占据了重要的地位。y 抽a s s e 【1 9 】提出依次序的 启发式排样算法，算法的主要思想是根据排样零件的物理属性( 长、宽、面积) 等给出一定的优先级规则，零件按照这种优先级规则排序，从板材的左下角开 始按次序排放每一个零件。d a g l i 和t a t o g l u 2 0 1 提出使用启发式算法，但该启发 式算法的启发规则难以确定，排样结果不稳定。a m a r a | 【孔j 提出一种交互式排样 方法，计算结果比较稳定，但排样效果一般化。p r a s a d 和s o m a s u n d a r a m l 2 2 吸 收两种理论的优缺点，针对三种不同的问题提 “了不同的算法。文献1 2 3 j 提出了 一种混合启发式优化算法，在建立新的数学模型的基础上，采用一个三步算法 进行求解，首先利用贪婪算法获得一个较好的初始解，然后利用禁忌搜索进行 初步优化，最后利用。个改进的穷举方法( e x a c ti m p l i c i te n u m e r a t i o nm e t h o d ) 进行优化。文献1 2 叼利用启发式算法和最小下界条件来解决装箱问题。 d y c k h o 一1 1 对排样问题进行了综述，依据空问维数、排样任务种类、排样材 料分类和排样零件分类等四个特点，建立了排样问题的拓扑( t y p o l o g y ) 模型。 7 0 、8 0 年代，随着智能优化算法如神经网络、遗传算法、禁忌搜索、模拟 退火等的不断出现，给解决排样问题提供了新的思路。9 0 年代后，智能优化算 法不断发展，日益成熟，它们在t s p 、装箱问题、任务调度等组合优化问题得 到了成功的应用，体现了智能优化算法的优越性。这些算法与排样算法相结合 解决排样问题j 下日益成为热门。 e h o p p e r 和b ，t u r t o n i ”】对遗传算法在排样问题中的应用进行了综述，按 照空间维数和排样图形的几何形状对排样问题进行了分类。对遗传算法中的排 样叫题编码方法、遗传算子和解码算法进行了讨论；s e g e n r i e c h 和b r a g a l 2 6 提出 用遗传算法解决零件多件多排问题；文献2 7 】提出一种新型的结合遗传算法和模 糊挎制的排样算法，利用模糊控制规则来降低遗传算法的适应度函数值( 该算 法中，适应度函数值越小越好) ，呵以获得较好的排样效果：文献1 2 引提出神经网 第1 章绪论 络算法，较好地结合了算法和人的智能因素，排样结果较好；文献【2 明应用模拟 退火算法解决圆形排样问题；文献【3 0 】应用蚁群算法来求解具有动态条件约束的 排样问题：d a g l i 3 h 采用神经网络、数学规划和基因算法来求解定宽无限长板 材的矩形件排样问题；文献【3 2 】综合利用启发式算法和遗传算法求解排样问题； 文献【3 3 l 提出一种“树形搜索”算法来解决切割下料问题；文献【3 4 给出了s a 、 g a 、n e 、r a 与不同排样算法结合，对不同问题实例的综合性能评价的结果， 有两点主要结论：复合算法的结果优于单纯排放算法的结果，并且排放算法 效果越好，则复合算法在同等条件下的效果也越好。任何算法都有效果不佳 的算法实例，即使对矩形件排样目前都没有完全有效的排样算法。 在对矩形件进行研究的同时，人们也对二维不规则零件的排样问题进行着 研究。相对来说，不规则零件的排样问题难度要大很多。对不规则零件排样的 方法可以分为三大类：第一类是以矩形件排样为基础的排样算法。对于不规则 零件，首先利用包络矩形技术转化为矩形零件，然后利用矩形件排样算法进行 求解；第= 类是以图形运算和计算几何为摹础的方法。把排样的材料和零件都 作为图形来处理，利用图形学和计算几何的知识来进行排样零件的定位和判交 处理；第三类是采用智能优化算法。这类方法一般都是和第、二类方法相结 合使用的。 文献最早提出了两步法的排样思路；文献【3 6 】采用两步法进行排样，首先 利用包络矩形法，然后利用模拟退火算法进行求解：文献1 37 】利用遗传算法进行 求解；文献3 8 l 提出将遗传算法和启发式算法相结合来求解二维不规则零件排样 问题，对遗传算法的编码方法进行了改进，从图形学的角度出发，使算法尽可 能忽略材料和零件几何形状的复杂性的影响；文献【3 9 】讨论了不规则材料上的圆 骷排样问题；文献采用临界多边形( n f p ) 求解不规则零件排样问题。 我国的计算机辅助排样研究工作开展的比较晚，始于8 0 年代，开始时， 一般都集中在矩形件排样的研究上，出现了许多研究成果【4 1 1 1 4 2 1 1 4 3 】【州【4 5 1 。主要集 中在清华大学、浙江大学、上海交通大学、华巾科技大学和四川大学等高等院 浙江大学博士学位论文 校和研究所。至今已经获得了很大的发展，但是总体上，国内就排样问题研究 和国外相比，无论是深度和广度方面，仍然有很大的差距。 进入9 0 年代之后，矩形件排样技术有了进一步的发展。曹炬【4 6 j 提出了一个 利用背包问题解法的矩形件排样的近似优化算法；崔耀东【47 提出了组块策略， 将制造同一种产品所需各种不规则形状零件套排成大小各异的矩形组块，每一 组块包括多个零件：下料时在整张板上按矩形组块切割，同一张板上可以排列 多个矩形组块；文献1 4 8 j 构造了一个近似算法，该算法的主要思想是在排样过程 中根据一种局部最优原则不断地动态产生一些较小的矩形，然后对这些小矩形 区域排样，l 司时也消去一些已排过的矩形区域，直至所有的矩形件被排完；文 献【4 9 提出用遗传算法求解矩形件排样问题；文献提出一种带预选搜索步深的 二维- - ) j 切矩形优化排料算法：李建勇提出分别用混沌人工神经元网络【5 l 】和 c h n n 人工神经元网络1 5 2 】进行排料优化计算；文献吲提出一种基于c a s e 推理 的优化排料算法，主要思想是对每块板材的布局都进行c a s e 推理，选取最佳 布局，若没有相应的c a s e ，则调用启发算法搜索。 9 0 年代以后，开始逐步涉及不规则零件排样研究。岳为| 5 4 j 提出将不规则零 件转换为规则零件，并进行自动组合填充，然后根据局部寻优的原则进行排样 的算法，提高了材料利用率；文献【55 】提出一种针对不规则形状冲压零件排样的 智能化算法，该算法利用了一种新的自动碰撞技术以寻求尽可能多的可行排样， 并自动计算碰撞零件和固定( 被撞) 零件之蝴的动态距离；文献| 56 j 提出基于改进 免疫遗传算法的不规则图形排样算法；刘心雄1 57 j 提出一种基于人工智能的自动 排料算法，该算法运用问题归约理论，将自动排料的过程简化为基本块的生成 与搜索，运用规则判断与启发式搜索的方法，生成基本块，对系统中大片、小 片( 衣片) 进行自动判断分组，从而加快了运算速度；文献【58 】提出一种基于四 叉树结构的排样算法，它也采用了两步法，预先利用组合规则和邻接规则生成 矩形块。 应用图形学和计算几何理沧，能使计算机在排样时自动控制整个图形作整 第1 章绪论 体平移、旋转而不局限于某一线段，排样具有一定的智能性。文献5 9 1 给出了解 决自动排料的求解思路，并对自动排料的主要算法移动算法，进行了研究 和改进：文献【6 0 j 给出了一种对象的几何表达方式，可以忽略高度不规则形状带 来的复杂性影响，然后利用遗传模拟退火算法进行优化排样；文献【6 1 1 提出一个 任意简单多边形的旋转靠接算法，该算法通过快速提取多边形的关于点的单调 线族的方法，将多边形的旋转靠接问题转换为多边形的部分线族的选择靠接问 题；文献【6 2 l 中讨论了计算机自动优化排样过程中图形求交和定位的关键技术， n f p 问题的算法实现。 1 3 2 优化排样问题的发展趋势 2 l 世纪的制造业将面临着m a s s c u s t o m z a t i o n 的生产方式，要求企业以批量 牛产的时间和成本生产出具有个性化( 客户化) 的产品，使得制造企业的生产 方式由面向产品的生产逐步转向面对顾客的生产1 6 3 1 。 ( 1 ) 考虑面向制造的问题 面向制造是面向并行工程的种设计方法，即产品设计与工艺设计并行进 行的一种设计方法。面向制造全面评价产品设计与工艺设计，并提供改进的反 馈信息，及时改进设计，以保证产品设计，工艺设计和制造一次成功，以达到 降低产品成本，提高产品质量，缩短产品开发周期的目的。具体到排样问题， 要考虑的包括： 把产品零件设讣和排样联系起来。板类零件分为两类：二维平面零件 和具有立体形状的零件。立体板类零件一般通过平面展开，切割下料，然后成 型。因此，在设计时就应该把零件的立体信息和后续加工信息存入特定的数据 库供零件排样时使用，以提高零件的生产效率和质量。 把排样和具体的工艺制造联系起来。要考虑不同的工艺制造问题，如 对丁火焰切割问题，要考虑切割变形问题、切割路径优化问题；对于冲压问题， 要考虑压力中心问题、零件的排列间隙问题。因此在排样时要完成相关工艺咨 浙江大学博士学位论文 询，进行多工艺方案的经济性分析。要综合考虑设备情况，加工成本和交货期 等因素，以达到整体上的最优。其中加工成本和交货期是最重要的。 ( 2 ) 解决计算的智能化问题 2 1 世纪是以知识经济和信息社会为特征的新时代，智能制造的研究应运而 生。智能制造技术和智能制造系统是在传统制造技术的基础上，利用计算机技 术、自动控制技术、传感器技术、信息处理技术、光机电一体化技术与人工智 能技术等发展起来的新型制造技术。其具体表现为：智能设计、智能加k 智 能控制、智能工艺决策、智能调度和管理等。 上世纪9 0 年代以来，各种智能优化算法如神经网络、遗传算法、禁忌搜索、 模拟退火算法等得到了很大的发展，日益走向成熟。由于排样问题的特殊性， 计算量非常大，在有限的时间内难以遍历整个问题的解空问，冈此非常适合利 用智能优化算法进行求解。但如何综合多种算法以及哪些算法在哪一阶段综合， 是排样问题研究的一个重要方向畔 。事实上自从9 0 年代以来，许多学