（船舶与海洋结构物设计制造专业论文）船舶板材排样优化设计研究.pdf

哈尔滨工程大学硕士学位论文 摘要 下料排样是船舶制造中必要的一个工艺过程，通过下料前的排样可以显 著提高钢材的利用效率，从而节约造船成本。本文针对船舶下料过程的排样 问题归类、分析，以单种零件的排样、多种零件组合排样以及矩形件的排样 为研究对象，通过关系数据库建立一套套料信息库，实现对排样过程数据信 息的管理，进而提高材料利用率和劳动效率。 排样问题是一类复杂的优化问题，不仅需要考虑几何约束，还要考虑船 舶下料制造过程中的工艺约束。本文对单种零件排样和多种零件组合排样进 行了研究，根据船舶钣金生产实际，采用先对零件进行几何包络矩处理，然 后再对矩形进行优化排样，结合“基于板宽”的理论，尝试将遗传算法用于 矩形件排样设计。 基于a u t o c a d 为平台，构建了一套船舶排样优化系统，主要模块包括： 零件信息管理，板材信息管理，下料零件管理，零件信息预处理，单种零件 排样和多种组合排样，以及排样图形信息输出。 关键词：0 b j e c t a r x ：板材排样优化；基于板宽；矩形板 哈尔滨工程大学硕士学位论文 a b s t r a c t c u t t i n go fs h e e tm e t a lt op r o d u c ep a r t i san e c e s s a r yp r o c e s si n s h i p m a n u f a c t u r e ，a n di ti se v i d e n tt h a tn e s t i n gb e f o r et h e p r o c e s sm a x i m i z e sm a t e r i a l u t i l i z a t i o na n de c o n o m i z e sc o s t t h i sp a p e ra n a l y z e sa n dc l a s s i f i e s n e s t i n g p r o b l e mi ns h e e tm e t a lm a n u f a c t u r ep r o c e s s s i n g l ep a r tn e s t i n g ，d i f f e r e n t s h a p e d p a r t sc o m b i n a t o r i a ln e s t i n ga n dr e c t a n g l ep a r t sc o m b i n a t o r i a ln e s t i n ga r es t u d i e d i nd e t a i l t h em a n a g e m e n to fn e s t i n gi n f o r m a t i o ni sa c h i e v e da e r o s s i n gr e l a t i o n a l d a t a b a s eo fn e s t i n gi n f o r m a t i o n a c c o r d i n g l yi m p r o v em a t e r i a lu t i l i z a t i o na n d w o r ke f f i c i e n c y n e s t i n gp r o b l e mi sak i n do fo p t i m a lp r o b l e mw i t hg e o m e t r i cc o n s t r a i n t sa n d t e c h n o l o g i c a lc o n s t r a i n t si ns h e e tm a n u f a c t u r ea sw e l l s i n g l ep a r tn e s t i n ga n d d i f f e r e n t s h a p e dp a r t sc o m b i n a t o r i a ln e s t i n ga r es t u d i e db a s i n gm a n u f a c t u r e p r a c t i c a l i t yi nt h i sp a p e r p a r te n c l o s u r ea l g o r i t h mi sf i r s tu s e da n dt h e no p t i m i z e n e s t i n go f r e c t a n g l ep a r t s a c c o r d i n gt ot h e o r yo f b a s e do ns h e e tw i d t h ”，g e n e t i c a l g o r i t h mi st e n t a t i v e l yu s e df o rr e c t a n g l ep a r t sn e s t i n go p t i m i z a t i o n as u i to fo p t i m a ln e s t i n go fs h i ps h e e ti sf r a m e db a s e do na u t o c a d ， p r i m a r ym o d u l ei n c l u d i n g ：m a n a g e m e n to f p a r t si n f o r m a t i o n ，m a n a g e m e n to f s h e e t i n f o r m a t i o n ，m a n a g e m e n to fs t o c kp a r t s ，p r e t r e a t m e n to fp a r ti n f o r m a t i o n ，s i n g l e p a r tn e s t i n g ，d i f f e r e n t s h a p e dp a r t sc o m b i n a t o r i a ln e s t i n ga n do u t p u to fn e s t i n g g r a p h i c si n f o r m a t i o n k e yw o r d s ：o b j e c t a r x ；o p t i m a ln e s t i n go fs h e e t ；b a s e do ns h e e tw i d t h ； r e c t a n g l ep a r t s 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：圣! ! 壅 日期：j o 口6 年月2 7 日 哈尔滨- t 程大学硕士学位论文 1 1 排样系统概述 第1 章绪论 优化摊样系统就是要解决生产实践中的一维下料问题，二维排样问题， 三维装箱问题。这类问题我们统称为排样问题( p a c k i n gp r o b l e m ) 。由于这类问 题都是n p h a r d 问题，所以我们主要是用一些现代常用的优化计算方法，如 遗传算法，模拟退火，启发式，禁忌搜索等算法来求解实践中的一些具体问 题的近似最优解。从而能使实际生产者提高其生产效率和经济效益! 最大限 度地节约材料，提高材料利用率是生产中提高效益的一个重要手段。而由于 排样问题的广泛存在，船舶工业下料问题，钢板下料，飞机钣金下料及玻璃 切割，报刊排版，服装裁减等，都需要在可接受的时间和客观条件下得到最 优和近似理论最优的解，因此解决这类问题有着重要的理论意义和现实意义。 优化排样问题的理论研究涉及到线性规划( l p ) ，整数规划( i p ) ，动态规 划( d p ) ，计算机图形学( c g ) 及人工智能( a i ) 等多种学科。此类问题由于具有 广泛和真实的应用背景，所以许多国内外学者对此进行了长时间的研究和尝 试工作。已经尝试过的主要方法主要有启发式方法，模拟退火方法，遗传算 法，基于学习的方法等。 零件排样布局的优劣，直接与产品的成本及企业经济效益有关。该问题 日益引起应用部门和学术界的兴趣。目前国内外已有一些关于一维，二维和 三维排样问题的软件，它们多半是提供交互排料和自动排料两种功能，但是 从排样的效果上来看，自动排料并未形成相对于人工排样的非常明显优势， 这说明自动排样算法还有进一步研究的必要，实际生产中还非常需要更多更 好的排样软件。这也正是我们今后不断努力奋斗的方向。 排样问题在现实生活和生产中大量存在。我们主要研究以下一些排样问 题： 1 ，一维( 卜d ) ：这里我们主要考虑钢管，t 型材等下料问题 2 ，二维( 2 - d ) ： a ) 生产规模 哈尔滨工程大学硕士学位论文 大规模和小规模 b ) 零件形状 矩形件：一般切割，二级切割和三级切割 异型件：规则和不规则 c ) 生产要求 一刀切( g u i l l o t i n e ) 和非一刀切( n o n g u i l l o t i n e ) 3 ，三维( 3 一d ) ：目前主要还是装箱问题 从我们对排样问题的分类很明显可以看出来，二维排样问题是我们研究 的重点。其中矩形排样是我们研究的重中之重。我们研究这类问题最重要的 原因就是要最大限度的节约材料，提高材料利用率。 1 2 板材下料c a d c a m 系统的研究与应用概况 我国制造业普遍存在板材下料利用率不高的缺憾以及决定板材下料利用 率高低的因素，针对这些因素开发的板材下料c a d c a m 系统可以有效地帮助 企业在技术和手段上改人工排样为计算机自动优化排样，从而实现集中下料 的先进生产方式和提高板材下料的利用率及企业的经济效益。 在板材上套料零件不仅要考虑零件图形互不重叠、不但要排出板材的约 束，而且要从优化的角度出发，考虑它们的合理拼接，任意移动( 平移、旋转、 镜象) 以及凹边填充等。这些因素都是由于零件图形的不规则所致，并使问题 更加复杂化。目前国内外有少数学者在这方面做了不少尝试，并取得了很多 有益的成果。其中以浙江大学、西安交通大学、华中理工大学和美国的 a h l b a n o ，m a d a m o w i c z 的工作最有代表性，他们主要方法为：多边形边界移 动法和最小矩形包络法：自动碰撞理论求解边界位置等。例如国外文献“”采 用轮廓边的匹配方法，按照一组基于零件面积、轮廓周长和复杂性的性能参 数进行排序，选择两个具有最高指标的零件，按照逆时针方向匹配每一边后， 以形成的最小包络矩形确定排放位置。这个过程不断重复直至所有零件排放 完毕。由于存在许多可匹配的边需要进行大量的测试，因此这种算法计算量 大，速度慢。a a l b a n o 在文献“”中研究了匹配边的方法，他采用选取两个零 件具有最长重合边的位置，将一个零件固定，另一个零件围绕这固定零件的 2 哈尔滨工程大学硕士学位论文 边移动一圈，但这种方法适合零件于零件数量较少的情况下。在国内对排样 问题的研究始于8 0 年代，主要集中在高校和研究所。华中科技大学模具国家 重点实验室的曹炬采用将零件图形处理为多边形的方法进行自动排样的研究 ，在文献。1 采用碰撞算法直接对零件进行排样。近年来不少国内学者对异 形件的排样问题进行了研究，例如：文献。1 采用一定规则先处理为矩形，然后 按矩形件进行排样；文献“1 采用基于图形运算的移动算法、碰撞算法，基于 规则、样图的方法，神经网络方法求解；于洋等提出的基于遗传算法求解卫 星舱布局问题等“1 。不过这方面的成果主要集中在排样c a d 上，而板材套料 是一个很具体的生产过程，显然要在这个方面上有所进展，不仅需要在优化 理论与算法方面有所突破，而且需要在图形识别、图形处理、人工智能、计 算机辅助自动数控编程、数控加工仿真等方面有相应的开发和应用。在开发 中，排样c a d 与套料c a m 是密不可分互为补充的，二者共同组成板材套料 c a d c a m 系统。并且还要将系统纳入车间生产作业信息系统，才能真正发挥 它的作用。 由于排样问题应用领域广泛，众多学者在研究排样算法的同时也开发了 一些排样软件。目前国内较成熟的套料软件有以华中科技大学排样理论为基 础而开发的武汉世科有限责任公司推出的套料软件，它包括矩形件优化排样、 线型材优化排样、冲裁件优化排样、异型件优化套料排样等软件，其它还有 一些与之类似的软件，例如：重庆大学刘飞等人开发的型材、矩形件排样系统： 大连理工大学的滕弘飞及其课题组成员对航天器舱布局方案设计等等。但这 类软件仅仅针对整个套料生产作业中的一个环节排样，缺乏与企业其它部 门的信息交流。这种单纯的排样并不能显著提高材料的综合利用率。但这样 仍然不够，实际上，提高钢板材料利用率的工作是一个系统工程，涉及技术、 生产、物资各个部门，既有管理因素，又有技术因素，管理是重点，这里所 指的下料管理包括：生产计划管理、生产人员管理、材料管理、库存管理、生 产设备管理、技术文档管理等等，通过科学高效的下料管理能够及时掌握车 间的资源状况：制定合理准确的生产计划并实时掌握及调整生产计划的执行 过程。故真正适应市场需要的套料软件应该是将下料管理放在核心地位，必 须将优化排样c a d 系统和套料c a m 系统集成在下料管理系统下构建成车间生 产作业信息系统，才能进行统一资源配置、优化生产任务规划、优化排样设 堕玺鎏三堡盔兰堡主堂垡堡茎 计、高效套料等过程，真正实现显著提高材料综合利用率的目的。 1 3 排样系统的研究趋势 2 l 世纪的制造业将面临着m a s s c u s t o m i z a t i o n 的生产方式，要求企业 以批量生产的时间和成本去生产出具有个性化( 客户化) 的产品。优化排样系 统必须适应工厂应用环境及应用场合的灵活多变性，将排样问题与设计、工 艺相联系，面向制造：同时与生产管理系统密切联系。 ( 1 ) 把产品零件设计和排样联系起来。板类零件分为两类：二维平面零件 和具有立体形状的零件。立体板类零件一般通过平面展开，然后成型。因此 在设计时就应该把零件的立体信息和后续加工信息存入特定的数据库供零件 排样时使用，提高零件的生产效率和质量。 ( 2 ) 把排样和具体的制造工艺联系起来。要考虑不同的工艺制造问题，如 对于火焰切割问题，需要考虑切割变形问题、切割路径优化问题；对于需焊 接的零件，要考虑零件坡口的形状：对于冲压问题，需要考虑压力中心平衡、 桥宽问题。因此在排样时完成相关工艺咨询，进行多工艺方案的经济性分析。 要综合考虑设备情况、加工成本和交货期等因素，以期达到整体上的最优。 ( 3 ) 将排样优化系统作为整个企业信息化系统的一个有机组成部分，实现 整体最优。从系统的观点，将排样优化系统作为整个企业信息化系统的一个 有机组成部分，排样系统不单纯提供排样功能，而且对生产、管理提供决策 支持信息，实现整体上的最优。 1 4 船舶板材排样的特点 对于造船行业来说。其板材的套料有着自身的特点。一方面虽然它的排 样也要求在给定的平面区域内找出被排零件的最优布局，使得材料消耗最少， 并且零件之间不能互相重叠；另一方面船舶零件由于形状复杂，多为不规则 零件，制造特征和方法各异，船舶产品多为单件生产，当采用火焰切割时还 有变形问题等独有的特点，决定了其在设计算法时要综合考虑多种因素。能 否有效降低生产成本是一个企业能否在市场经济条件下正常运作的关键，由 于材料成本在工业生产的成本中占有很大比重，所以如果能够研究出一套比 4 哈尔滨工程大学硕士学位论文 较有效的排样方法，用来提高材料的利用率，显然是非常有意义的。 船体零件套料工作是船舶建造的重要工序，它对于缩短造船周期，提高 板材利用率有着重要作用。目前不少船厂虽已采用c a d c a m 技术进行船体零 件的套料工作，但由于所使用的方法( 即模拟手工套料的交互式方法) 与评价 准则不合理，故所收到的效果并不令人十分满意。 船体零件套料是一种2 - d 布局问题，其实质就是将若干个不同形状的零 件，按其互不重叠的布局要求，依次布置在一组矩形钢板上，并要求所使用 的板材数量最少，利用率最高。显然，从该问题的性质与求解目标的要求而 言，它是一种极为复杂的多目标、多约束非线性优化问题，而且难以数学解 析式加以描述。这也正是目前多采用交互式方法求解间题的原因。而交互式 方法不但效率低，而且没有建立数学模型与合理的方案评价准则，故难以得 到比较合理的布置方案。 1 5 船舶板材的排样问题的研究现状 船体生产设计工作的流程相当复杂，而且处理的信息非常多，需要多人 参与并协同工作。具体来说，在进行船体生产设计时，主要有以下几项工作 要完成： 材料汇总。这部分需要做的工作是，根据在a u t o c a d 中设计完成的图 纸，完成对图中的零件进行分类统计处理。通过汇总每张图中各类零件的信 息和整条船所用材料的总体信息，得到各张图的材料明细表以及整条船的材 料订货清单。 套料( 即船体零件的下料) 7 - 作。这部分工作一般分三个阶段来完成，其 中第一阶段为套料前的信息准备，主要是对前一科室提供的零件信息、施工 图册以及批量分段表等进行数据处理，并建立套料数据库来管理这些数据； 第二阶段进行自动套料( 这项工作进行时，需要进行材料检查、零件干涉状况 检查、切割过程模拟、划线顺序优化、零件的切割顺序及引火点位置的优化 等工作) ；第三阶段主要完成套料结果的记录，并统计输出各项数据。 具体归纳起来，目前我国各类船厂生产设计工作方式的不足，主要在以 下几个方面体现： 哈尔滨工程大学硕士学位论文 1 ，设计数据库管理分散，数据的正确性和安全性没有保障。 2 ，有些船厂设计平台比较落后，而且功能也不完善。 3 ，船体零件的套料大多停留在手工套料阶段，没有真正实现自动化、 智能化套料。 1 6 本文研究的方法和研究意义 本课题所研究的是板材排样系统是面向船舶制造，结合船舶制造中实际 生产加工需要，以面向c 觥a m 集成需求。包括单种零件的排样，矩形件 组合排样，以及多种零件的组合排样，建立一套合理的排样信息数据管理系 统。 本课题是基于a u t o c a d 图形平台下进行的排样系统研究。由于a u t o c a d 是目前最为通用的绘图软件，具有功能强，适应强的特点，是目前很多工厂 的科研院所选用的最为普及的c a d 系统。对图形的处理也是基于对数据交 换文件d x f ( d r a w i n ge x c h a n g ef o r m a t ) 文件处理基础上，而且d x f 文件 已成为事实上的标准，这里对d x f 文件的处理也就具有一定典型性。 本课题主要研究内容包含： ( 1 ) 排样信息的预处理 零件轮廓提取、等距放大等算法是排样取得零件几何信息必须的算法， 在前景处理完成后才能继续应用优化排样算法得到排样方案。包括对d x f 文件的访问以及封闭轮廓的组成。 ( 2 ) 单种零件排样算法 对单一零件的排样优化问题，主要是确定零件最佳方位角度和双排中相 邻零件间的最佳相对位移，以及在每个角度下计算排样步距和料宽。 ( 3 ) 组合排样算法 组合排样相应分为矩形件组合排样和曲线外形零件组合排样两类问题。 在实际生产中，每次下料首先要选择实际生产计划中一定材料和厚度要求的 零件在同一批内加工，这就是一个下料计划。组合排样需要根据下料计划进 行，实际上这就把组合排样问题划分为两个问题：满足给定零件的数量要求 和确定每个零件在板材上的位置和数量。在本研究中把前一个问题称之为排 6 哈尔滨工程大学硕士学位论文 样方案数量优化问题，第二个问题称之为排样优化问题。 ( 4 ) 排样信息库的建立 对于待排零件，随着排样的进行，待排零件的数量不断发生变化。为了 便于管理，系统建立了一个排样数据库，用于管理排样过程中待排零件的各 种信息，包括编号、数量、面积等等。在排样的过程中，可以查询或者更新 这些数据，以判断排样进行的状态。排样过程不仅需要待排零件的工程信息 和工艺信息，更需要钣金零件的几何信息，以实现对待排零件和板材信息有 效的管理。 7 堕签堡三堡奎堂堡主堂垡堡窭 第2 章排样的过程分析 零件的排料过程可以视为在毛料上零件排放状态的变化过程。常用的排 样方法有普通单排、普通双排、对头单排和对头双排四种，其中普通单排和 对类双排最具代表性。根据船舶零件特殊性，通常也将零件化为矩形件进行 排样。 在开始排样的过程中，首先给出板材排样问题的求解模型；然后对待排 样的图形进行预处理，这是整个排样过程的基础。 2 1 板材排样优化问题求解模型 2 1 1 板材排样优化问题的形式化描述 设有各种大小的同材质同厚度矩形零件集合 p ) i 1 ，n ，其面积集 合为 b 。) ：另有原材料板材集合f a j j 1 ，m ，其面积集合为 a j ) ；排样 工作就是选出适当的板材集合 a m 1 ，k ，其面积集合为 a ) ，将零件集 合中的所有零件适当地安排在此板材集合中的某个板材上，并确定零件在该 板材上的位置和方向。优化排样即是寻找合理的板材集合 a ，以及其上零 件的合理放置布局，使如下目标函数达到最大值： m a x 隆割 协t ， 设在板材a ：上放置的零件集合为 砭) ，其面积集合为f 培) ( j 】，k j 1 ，h ) ，则选出的板材集合，以及零件在板材上的位置与方向应该满足如下 约束条件： ( 1 ) 在板材a ：上的所有零件( 瑶) 互不重叠，即集合( 瑶 中零件图形交集 哈尔滨工程大学硕士学位论文 为空； ( 2 ) 在板材a 上的所有零件 砭) 满足式( 2 2 ) ，且均在板材图形内； h a ：b ； ( 2 - 2 ) i - t ( 3 ) 所有零件 p i ) i 1 ，n 均在板材集合 a ：) j 1 ，k 中的某块板材上 ( 4 ) 在板材a ：上零件的放置满足一定的工艺条件。 2 1 2 求解策略 鉴于套料优化问题的复杂性，难以建立一个简单的数学规划模型，使用 传统的、简单的优化计算方法，来求解此问题。为此，本文研究以下策略来 求解板材套料优化问题： ( 1 ) 分解策略就是将板材排样规划问题的主要优化计算拆分为套排规划 和优化排样两个相对独立但相互协同的优化计算步骤分别求解：第一步套排 规划：以提高板材利用率为主要目标，以零件面积为主要参数，不考虑零件 的具体形状，使用装箱问题模型，计算在最高原材料利用率下零件的最优组 合。确定选出的板材集合以及每块板材上应该排放的零件集合。第二步优化 排样：根据套排规划计算结果确定零件在板材上的最优布局。第三步对板材 中不能排下的零件统一处理：或寻找最合适的其它板材，或增加新板材。当 排不下的零件过多时，进行新的规划计算，或放弃该方案，从套排规划结果 中另外选择一个解。 对于零件数量庞大，存在形状非常复杂或面积接近板材的零件时，板材 利用率是优先考虑的问题。则使用分解策略可以保证最少的原材料消耗。分 解策略的关键技术难题包括： 建立合适的套排规划数学模型，使用适当的方法保证求解的效率与效 果。套排规划相当于装箱问题，即一个n p c 难题。合适的求解方法一直是 一个世界难题。套排规划数学模型及其求解方法应该在零件规模较大时仍能 高效地找到一批相当好的结果，供优化排样时选择。 9 哈尔滨工程大学硕士学位论文 在零件轮廓形状任意复杂时，快速判断套排规划结果的可行性。套排 规划只考虑了零件面积，并不一定能保证在板材中排下给定零件集合。应该 设计一种快速判断能否排下零件的图形算法，以帮助套排规划寻找最佳零件 组合。 给定任意形状的零件集合和板材，寻找零件在板材上符合一定条件的 最优布局。复杂图形的布局和排样算法也是世界难题。 当排样布局的工艺条件比较复杂，零件图形比较复杂，排样算法难以 得到较好的排样结果时，需要设计一个人工排样的图形界面。多数情况下自 动排样的结果应该经过人工调整，才能保证在各个方面尽可能满足要求。 ( 2 ) 矩形策略就是将所有零件的轮廓简化为矩形，使用矩形零件的套排 规划和优化排样算法求解板材排样优化问题。矩形零件的形状只有长宽两个 参数，便于建立数学模型。矩形零件的排样算法有较多成功的设计，且便于 将套排规划和优化排样两个步骤统一在一个数学模型中求解。通过矩形策略 就把板材排样优化问题转化为矩形件的优化排样问题了。矩形策略的关键技 术包括： 设计矩形零件优化排样的算法：既要求保证较好的排样结果，又要求较 高的计算速度，才便于将排样与规划一并求解。 零件的矩形近似算法：为了保证较高的板材利用率，任意形状的零件应 该用其最小包络矩形近似，并将几个零件组合成一个接近矩形的形状。零件 的矩形近似非常重要。如果最小包络矩形过大，则板材利用率降低；如果过 小，则零件不能在板材中排下。如果组合在一起形成矩形的零件越多，面积 越大，则排样规划的结果可能越差；组合在一起的零件太少，则最小包络矩 形与真实形状的差别可能越大，板材利用率会降低。 2 1 3 求解过程 基于以上求解策略，一套合理完善的优化排样系统，应当建立以下求解 过程，具体主要包括以下五个步骤： ( 1 ) 零件信息预处理：从生产作业管理系统中读取本次排样所需的零件 1 0 哈尔滨工程大学硕士学位论文 信息，按同材料、同厚度、完工期限相近等信息归类，建立基本零件信息集 合。用人工辅助或算法自动计算集合中零件的面积、最小包络矩形、零件组 合矩形等信息集合，产生待排样零件集合。 ( 2 ) 板材信息处理：读取材料库存中板材的信息：材质特征、板厚、尺 寸、面积以及是否为需要优先使用的余料，选择本次排样计算所需的板材集 合。无论新板材或余料都需要确认板材的有效面积不包括边缘。 ( 3 ) 优化计算：取待排样零件集合的有关信息与待选板材信息，生成各 种优化计算方法模块所需的初始输入信息，进行优化计算。汇总各种优化方 法得到的最好的一批结果形成优化排样的最终结果数据。这个步骤也整个优 化排样求解过程最为关键和复杂的过程。 ( 4 ) 排样图形生成：优化计算过程完成以后，从结果数据中取出若干较 好的结果，送到指定的c a d 系统或其它绘图工具软件中，自动生成排样图。 经过人工确认和修改调整，产生最终排样结果。 ( 5 ) 排样结果输出：输出排样图和原材料消耗统计信息；向生产作业管 理系统返回排样结果信息；根据作业调度指令为每块板材编制n c 代码。 2 2 排样图形的预处理 2 2 1 任意多边形凸、凹顶点的判定 进行优化排样的前提条件是必须完整地提取该不规则零件的内外轮廓特 征，在此基础上调整图形的位置和姿态以达到一个近似最优算法，以便能在 一个低阶多项式时间内得到“接近”最优的解。因为任何带曲线的图形都可 以通过直线逼近转化为多边形进行处理，所以为方便，下面把不规则零件视 为多边形来处理。 如果将一个多边形置于一直角坐标系中，可以证明，只有使多边形的两 凸顶点之间的边或连线平行于坐标轴时才能产生最佳的矩形包络，为此必须 先求出多边形的凸顶点( 或凹顶点) ，然后才能求出最优包络距。 哈尔滨工程大学硕士学位论文 对任一多边形的某一顶点e ，我们给出顶点坐标为p ( x ；，y ) ，其入 矢量定义为从e 。( x i _ 1 ，x 一。) je ，其出矢量为从e 哼e + 。( x 。，x + 。) 即 v 入2 ( x i x j 1 ) i + ( x y i 。) j ( 2 3 ) v i e = ( x 一x i ) i + ( y i + l y i ) j ( 2 4 ) 由此可知，如果e 。寸p ：斗e + 。成逆时针方向，则e 为凸点( 如图2 1 a 所示) ；反之，如果成顺时针方向，则只为凹点( 如图2 1 b 所示) 。 二+ j j j ： ， r 、鬲 、一 p i + l 图2 1 ab 为凸点图2 1 bp i 为凹点 优矢量叉积的公式，如果v 入x v 童为正，则只，e 只。为逆时针； 反之则为顺时针。 v - 入xv 出= ( x i x 。) i + ( y y ；，) j 】x ( x i + 1 - x i ) i + ( y ：+ 一y ；) j = ijk x i x i 1y i y i 1 0 x + l x iy 汁l y i 0 i x 一x 2 l x l + l - x i y 一y i - i k y i + l y i | 枞当巨基 y i - 叫y i - i 呲啪榔籼点。 2 2 2 图形的等距放大 在c a d 领域，图形等距放大一直以来都是一个很值得讨论和研究的问 题，在优化排样过程中，我们通常为了考虑工件间的搭边，一般将待排样工 件图外轮廓沿法线方向等距放大半个工件问搭边值或给定的值，如图2 2 所 一 h ， 、，| 、| ， 一 ，k ， ， 、。 ， 、 ， 一 一 jr _ _ ( p p 哈尔滨工程大学硕士学位论文 示： 2 图2 2 等距放大 在排样设计时，将以等距图代替原工件外轮廓图形，等距图之间如相切 即保证了工件问所必需的最小搭边值，常规的封闭环等距放大算法已较完善， 但对于带有内凹的图形，如果放大量大于一定值，等距图就会发生自交，导 致干涉错误。解决上述错误通常有两种途径： 第一， 是在进行等距放大之前，进行计算，判断在给定的放大距离 时是否会产生干涉现象，如果发生了干涉，则进行一定的处 理以简化原图，然后再进行等距放大。 第二， 则是先按照上面介绍的方法计算出等距放大后的图形，然后 再判断是否有干涉发生。如果发生了干涉，则删除某些交点、 线。 这两种方法各有利弊。第种方法面临的困难是很难找到一个判定在给 定放大距离时凹形是否发生干涉的判据。下面我们采用第二种方法来处理等 距放大问题。 哈尔滨工程大学硕士学位论文 3 3 ( a )( b ) 图2 3 等距放大干涉处理 如图2 3 所示，( a ) 为带有内凹的原图形，( b ) 为原图经过等距放大后 得到的图形。容易看出，等距放大后产生了自交现象。问题的原因产生于原 来不相交的线段在经过等距放大后发生了相交。问题的解决在于找出多余的 交点，合理删除多余交点。具体步骤如下： 第一，按逆时针方向给图形上的各个顶点( 圆弧仅计首尾两点) 顺序编 号，并将其存放到双向循环链表s o u r c e 之中，然后计算得出等 距放大后各顶点对应的新顶点，也将它们存放在另一双向循环链 表r e s u l t 中，如图，此二链表的结点均为1 、2 、3 、4 、5 、6 、 7 、8 。 第二，下面将寻找等距放大图中多余的交点，按照链表r e s u l t 中节点 的顺序遍历各曲线段( 或直线段，以下同) ，以判断其是否与不相 邻的其它曲线段相交，如果产生了交点，则记录该交点，并存放 到一个新的单向链表p o i n t s 之中，之后将p o i n t s 中的各个节点 插入到r e s u l t 链表中，插入时每一交点都会插入两次。具体规 则为：该交点是由哪两条曲线段相交产生的，就将其分别插入到 每一条曲线段所对应的两个顶点之间。如图( b ) 中的只点是由曲 线段1 、8 和直线段6 、7 相交产生，则p l 应分别插在顶点1 、8 之间和6 、7 之间。点插入之后，再按照新的r e s u l t 链表继续遍 1 4 哈尔滨工程大学硕士学位论文 历下去( 不必重头遍历) ，以使后继的所有多余交点都能够准确地 插入到r e s u l t 中。此时p 点系由曲线段p 1 、8 和直线段p 1 、7 相交产生，则p 2 应分别插在顶点e 、8 之问和e 、7 之间( 插入 时需确保没有重复插入同一点) 。完成之后， r e s u l t ：1 、2 、3 、4 、5 、6 、e 、p 2 、7 、8 、p 2 、p l p o i n t s ：e 、p 2 第三，接下来要做的就是删除某些多余点。沿p o i n t s 链表中点的记录 顺序，遍历r e s u l t 链表，进行拆链工作由于p o i n t s 链表中的 每一个记录都对应着r e s u l t 链表中的两个记录，因而可以将 r e s u l t 链表按照p o i n t s 链表中的每个记录分解成两个双向循环 链表，记为r e s u l t l ，和r e s u l t 2 ，具体拆分规则为：在r e s u l t 中找到与p o i n t s 链表中相应的点后，双向搜索，直至在每个方 向上都再次遇到该点为止。按照p o i n t s 中的点只，可以将r e s u l t 拆分为： r e s u l t l ：p l 、l 、2 、3 、4 、5 、6 r e s u l t 2 ：p 2 、p l 、7 、8 、p 2 然后对r e s u l t l 和r e s u l t 2 进行同样处理，r e s u l t 2 又可按p 分 拆为： r e s u l t 3 ：p 2 、p i r e s u l t 4 ：p 2 、7 、8 按照如上方法，直到p o i n t s 中的所有记录都处理完毕为止，便可以得到 若干个各自独立的双向循环链表，也就是将一个有干涉的封闭图形拆分成了 若干个相互独立的封闭图形。之后，再从各个相互独立的封闭图形中选出最 大的封闭图形就是所要的等距放大图。在此即为r e s u l t ，所以最终结果为：p 、 l 、2 、3 、4 、5 、6 所组成的封闭图形为等距放大图形”1 。 2 2 3 图形的包络矩和最小包络矩 所谓图形的包络矩，使之完全包括了图形上的所有点，各边均与图形相 接触的矩形。凸多边形最简单的一个包络矩求法就是求出其横、纵坐标最大 哈尔滨工程大学硕士学位论文 与最小值共四个点，然后将其相连；对于凹多边形的包络矩就是不断将其凹 点相邻的两顶点相连形成其凸壳，然后依据凸多边形求包络矩的方法而得到 的。 图2 4 凹多边形的包络矩图2 5 凸多边形的包络矩 所谓最小包络矩就是在多边形所有的包络矩中面积最小的包络矩形。下 面介绍主要步骤： 1 ) 求出多边形所有凸点，依次连接得到新的凸多边形。 2 ) 求出新凸多边形每条边与坐标轴所成的角。 3 ) 以凸多边形每条边为基准，对应角为旋转角对其进行旋转，得到新的 凸多边形。 4 ) 求出新凸多边形的包络矩，并求出包络矩形的面积。 5 ) 求出所有包络矩形面积的最小者，此最小面积所对应的包络矩形便为 原多边形所对应的最小包络矩。 如图2 6 所示。图中零件从任意方向开始，向任意方向转动9 0 。的过程 中找到的最小外接矩形即为其最小包络矩形。只要采样角度a o 大小合适， 计算效率可以接受。计算结果需要记录包络矩形长宽和零件方向p 。 1 6 哈尔滨工程大学硕士学位论文 图2 6多边形的最小包络矩 2 3 同类零件普通单排计算 普通单排是将工件一个切一个的排列在一条直线上，料宽h 与步距s 仅 是图形与条料夹角目的单值函数。如图2 7 所示。 工件等距放大图p ( 1 2 3 4 ) 为绕点3 旋转口角后的位置，将p 的拷贝 p ( 1 2 3 4 ) 沿水平方向从p 向右平移并与p 相切，就形成了一个单排。此时， 为了计算步距s ( 口) ，从p 的各顶点向对边作水平线并相交，多边形在各顶点 处宽彬= q + 6 f ，由于p 与p 全等且对应边平行，则必有口，= n ；，由几何图形 特点很容易计算在各顶点处，顶点4 处的宽度最大，并且就是步距s r 口) ，即： s ( 口) = - - 一i t i a x 形( f = l ，2 ，3 ，弗) ( 2 - 5 ) 堕签鎏三矍丕兰堕主堂堡堕兰 y 1 j ! 么 2 恒j 攀 b 2 h ( d i 形1 p t 3 卜 y s ( 曲 图2 7 普通单排多边形顶点算法 多边形相切可能是点与点相切、点与边相切或者边与边相切，但共同边 界部分至少已含其中一个图形的顶点，因此以上算法具有普遍性，由此可以 得出结论：普通单排时，步距即为图形的最大顶点宽度9 1 。 因此，在普通单排时，优化排样就有了简化算法，即图形p 在角度范 围：0 - 1 8 0 。内每次以角度增量a 0 进行旋转，得到一个排样方案，并计算此时 的s 和h ，使得& 最小者即为最佳排样方案。 材料利用率计算的数学模型为： r l h = m a x ( y ) - m i n ( y , ) 一+ 2 a b s = m a x 彬】( 2 6 ) j 【叩2 其中z 为各顶点处的y 坐标值，为工件问的搭边值，6 为条料边缘搭 边值。 综上所述，普通单排的多边形顶点算法不需要考虑两个图形的相交状态， 也不需要判断零件图形轮廓是属于凹或凸的形状，而只是关心零件图形顶点 的个数和其状态，然后利用图形的转动就可以得到最佳的排样方案。图2 8 为普通单排的计算流程图。 1 8 哈尔滨工程大学硕士学位论文 (排样开始) 1 i 零件输入 。l。 l 零件图形处理( 离散 j 化，等距放大) + 0 图2 8 普通单排的计算流程图 2 4 同类零件的对头双排计算 在对头双排中，并不是将“等距图形”一个切一个地排在一条直线上， 而是先将图形平移或旋转1 8 0 。加平移后相切排布，因而不同于普通单排，每 两个图形才构成一个排样单元，单元面积仍可记为融肮。1 对头双排算法的 详细说明如下： 1 假定在某角度口时，原等距放大图形的位置如图2 9 中a 所示， 将图形a 绕原点旋转1 8 0 。可得a 1 ，再将a 。沿x 轴向右平移2 x 。， 沿y 轴向上平移y 眦+ k 。+ a l l ，得到a “图。 2 为了借鉴多变形顶点算法，将a 图形与a ”图形各按y o 、y 0 。、 y ”一、y ”。四点分别拆成左右两部分，并重新合成一个虚拟多 边形13 ”4 + l ”3 4 1 与一个虚拟外多边形13 ”2 ”1 ”3 2 1 。求得虚拟外 哈尔滨工程大学硕士学位论文 多边形的最大顶点距离和虚拟内多边的最小顶点距离，将它们相 减可得步距。 y 图2 9 对头双排的类多边形顶点算法 3 考虑到虚拟内多边形有时会出现交叉现象，如果利用上节中介绍 的普通单排多边形顶点算法求虚拟内多边形的最小顶点距离，将 会求得d ，或者d ，并非为所要的w 或w ；。参照普通单排多边形 顶点思想，可以将图形a 右半部分各顶点( 即l ，2 ，3 ，4 点) 作水平线，求得它们与图形a ”左半部分各边的交点，求出距离最 小值w 1 ，同样，由图形a ”左半部分各顶点( 即1 ”、3 “、4 ”点) 作 水平线，求得它们与图形a 右半部分各边的交点，找出距离的最 小值w ，比较w 与w ，可确定小者即为虚拟内多边形的最小顶 点距离。 4 用同样方法，可求得虚拟外多边形的最大顶点距离。 5 虚拟外多边形最大顶点距离与虚拟内多边形最小顶点距离之差为 步距。即： s = m a ) 【 彬外 - m i n 内 ( 2 7 ) 2 0 哈尔滨工程大学硕士学位论文 料宽由下式确定： h = m a x y i - m i n e 一+ 2 6 + ( 2 8 ) 式中z 为各顶点处的y 坐标值，为工件问的搭边值，a b 为条边 缘搭边值，l l 为两排图形间的错移量。 6 a 在0 - 1 8 0 。内每转动一个适当的方位角增量a o ，同时调熬l l 的 值，重复以上步骤可得到一个新的排样方案，如此循环直到求得 使排样单元耗料叙最小的方案，即是最终的排样结果。图2 1 0 为对头双排计算流程图。 2 1 哈尔滨工程大学硕士学位论文 r 蓬景髻嚣偿壤髂戮嚣井 将得到图形上移a h l l 塑竺皇翌空竺! ! 竺j l 藉粼帮掌 鼠料宽和 ，h r ：赢i 、n 。 、芝兰，一7 0y e s 惺冕警李童藿爨；羊雾梨鲁 i ( e ) m a l 人、 、7 。 y e s 羹森劣辫摄。最 竺堂兰堂算墨j f 7捧志柬。j 1 、 7 图2 1 0对头双排计算流程图 2 5 排样图形过程分析比较 0 通常在对图形的预处理过程中，通常过程如下图2 i i 所示 哈尔滨工程大学硕士学位论文 l | 零仆输入i i 图形信息预处理 i 翻形等跑放人 i 求出最小l i 包络矩i 工 对矩形中i ：摔样 j 零仆输入 l l 幽形信息预处理 率 i 图形等距放人i l 对j 4 i 形仆摊群i ( a )( b ) 图2 1 1排样图形信息预处理过程 由可知，( a ) 图是先对图形进行等距放大然后，然后再求出待排图形的 最小包络矩：( b ) 图则是先求出图形的最小包络矩，然后再对包络矩形进行 等距放大。在优化排样过程中，我们通常为了考虑工件间的搭边，即加工时 的方便，一般将待排样工件图外轮廓沿法线方向等距放大半个工件间搭边值 或给定的值。前者的优点是，更加节约板材用料，使板材的排样更加合理， 但它的缺点也是显而易见，即对多边形的等距放大过程容易产生交叉干涉现 象，删去多余点、线的过程也较为麻烦。后者与前者相比较，可能会在材料 利用率上较前者差，但由于是对包络矩形后的等距放大，不会出现交叉干涉 现象，一定程度上降低编程难度。 考虑到船体零件的特殊性，船用外板、实肋板、肘板等典型结构的形状 都是较为规则，因此可以先求最小包络矩，再进行等距放大后对板材实行排 样。 2 6 切缝边缘计算 在图2 1 2 中，设切缝的宽度为d ，实线表示的是各待排件的轮廓线，虚 线表示的是切割时应走的路线。很显然，我们