二维不规则排样cad系统的设计

《二维不规则排样cad系统的设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上海交通大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：顾振华日期：2007年2月6日上海交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学

2、位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在年解密后适用本授权书。本学位论文属于不保密□√。（请在以上方框内打“√”）学位论文作者签名：顾振华指导教师签名：何援军日期：2007年2月6日日期：2007年2月6日上海交通大学硕士学位论文1.绪论1.1.课题的研究背景及意义排样问题(Nestingproblems)又称为下料问题(Cuttingstockproblems)或[1]填充问题(Packingproblems)，其目标是在材料切割过程中寻求一个较高的材料利用率。由于现代加工制造

3、业的发展，经济增长对资源的需求不断增加，提高原材料的利用率可有效节约资源和降低成本，是实现可持续发展的必由之路；同时，自动化排样技术的应用有利于提高生产效率、降低人力成本，可以显著提高企业的经济效益。因此，排样问题的研究具有重要的经济价值。排样问题可定义如下：定义1-1在给定的几何空间E(d)(d为空间维数)内，寻求n个空间子集{R1dR2d,R3d,⋯,Rnd}的优化布局，优化目标是使得排样后所有子集占用的空间最小，即总体空间利用率为最大。其约束条件为式1-1：RE∈()didst..RR∩=∅(1-1)idjdij,{∈1..nij},

4、≠即排样后各子集位于给定空间内，且各子集互不相交；同时还需满足一定的工艺要求(例如对旋转角度或其他空间变换有一定的限制)。排样问题广泛存在于国民经济的各个行业，包括机械制造、印刷包装、服装、皮革、玻璃、木材加工、建筑、微电子、航空航天等，与实践应用密切相关。排样问题主要涉及到信息和计算机软件科学、运筹学、数学、工程管理等学科。从20世纪70年代以来，世界上许多研究机构和研究人员都投入了对优化排样问题的研究，不同研究人员从不同的学科角度，结合不同的应用需求，在相关会议和期刊上发表了许多论文，提出了多种算法，并出现了相关的专著和软件产品。然而从目前的研究

5、进展来看，排样问题，尤其是不规则形状排样问题，尚处在基础性的理论研究方面，诸如几何计算、排样定位规则及排样顺序优化算法等一系列算法还需要进一步的探索；从总体发展现状来看，对排样问题的研究较为分散，尚未形成系统化的理论，缺乏成熟可用的排样应用系统架构。1上海交通大学硕士学位论文1.2.排样问题的分类[2]Coffman等将排样问题称为GeometricCombinatory问题，根据是否涉及到空间布局划分为狭义和广义排样问题，如图1-1所示：GeometricCombinatoryProblems狭义排样问题广义排样问题(空间问题)(非空间问题)切割下

6、料：物料装填：时间调度资金预算其他：纸张、版金车辆装载时间分配找零资源分配玻璃、木材集装箱装填内存分配塑料、皮革货盘等服装纺织图1-1排样问题的分类Fig.1-1TheclassificationofGeometricCombinatoryProblems在狭义下料问题中，根据空间划分，排样问题可分为一维排样(线材排样)问题；二维排样(平面排样)或下料问题；三维排样(三维装填)问题。对于研究与应[3]用最为广泛的二维排样问题，国内有学者专门对其分类进行了研究，按照被排样零件特点、排样区域、优化标准和工艺要求进一步进行了划分。根据狭义排样问题在空间特征

7、上的分类，以下分别对一维、二维、三维排样问题进行简单介绍。1.2.1.线形排样问题线性排样问题的定义为：给定一定数量和长度规格的管材，要求从管材中切割出一定数量和种类的毛坯(各类毛坯的长度不一，数量要求也不同)，目标函数为消耗的管材总长度为最少。一维排样问题的定义较为简单，但是能够反映出排样问题的共同特征，即：在给定空间内寻求一种优化组合方式，在满足空间和工艺等约束条件的情况下，使零件占用的空间为最小，亦即浪费的空间为最小。[4][5]由于线性排样问题只涉及到一个维度变量，一般采用整数规划模型算法，理论上可以求得最优解。然而在排样问题规模较大、零件毛

8、坯种类较多时，整数规划求解的计算量和计算时间相对于毛坯种数将呈指数级迅速上升，无法在合理2上海交通大学硕士学