不规则零件的玻璃排样问题启发式算法研究.pdf

《不规则零件的玻璃排样问题启发式算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、AHeuristicAlgorithmResearchforIrregularGuillotineGlassPackingProblemDissertationSubmittedtoNanjingUniversityofFinanceandEconomicsFortheAcademicDegreeofMasterofEngineeringBYLuShuangSupervisedby(Associate)ProfessorHanWeiSchoolofInformationandEngineeringNanjingUniversityofFinanceandEconomics

2、November2011学位论文独创性声明本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明并表示了谢意。作者签名：——日期：学位论文使用授权声明本人完全了解南京财经大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部分内容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此规定。作者签名：——导师签名：——日期：捅要二维不规则零件排样问题

3、在玻璃加工、金属切割、服装等行业都有着广泛的应用，排样的目的是将一系列形状各异的零件排放在给定的材料上，找出零件的最优布局，让材料的利用率最大化，达到节省原料、提高企业经济效益的目的。排样问题属于典型的组合优化问题，在理论上，它属于NP完全问题，求解过程非常困难。本文以建筑设计的不断发展为背景，以玻璃排样问题为研究对象，提出了一种启发式排样算法。鉴于玻璃这种物质的特殊属性，在切割过程中必须满足贯通性约束条件，即guillotine约束，所以相对于布料、皮料等材料的切割，玻璃的切割过程更加的复杂。本文首次结合了贯通性约束和不规则排样两个方面的问题，提出了一种贯通性约束下的不

4、规则零件排样算法。显然，这一问题有着广泛的应用背景及理论意义。本文首先以玻璃排样问题为研究对象，提出了一种以贴边度为启发式信息的不规则零件匹配算法，并应用该启发式匹配方法构造了n阶匹配矩阵，将划分问题转换成在可行划分方案中寻找浪费率之和最小的方案，然后通过改进的匈牙利方法和KuhnMunkras算法进行最优划分。其次，在排样零件的填充问题上，通过介绍BL排样的相关知识，并对它的优缺点进行分析，针对其缺点提出了矩形复合的概念。指出在矩形复合过程中，需要递归地进行矩形排样，并以两个矩形匹配的利用率为启发式信息，分阶构造森林，只接受那些利用率大于给定阂值的匹配方案。最后，通过中

5、英两个玻璃加工企业的订单数据，进行了实验验证，证明本文提出的算法是有效的，原材料的利用率得到了提升。关键词：不规则排样；贯通约束；矩形复合ABSTRACT2Dirregularpackingproblemiswidelyusedinglass，steel，textileandotherindustries．Theaimofpackingproblemistofindthearrangementofpartsandproducingtheleastwaste．Packingproblembelongstotypicalcombinatorialoptimizationpro

6、blem．ItisaclassoftheNP—hardproblems．It’Sverydifficulttofindtheoptimalsolutionforsuchaproblem．Inrecentyears，architecturaldesignindustryhasdevelopedrapidly．Glasscuttingindustryfacesseverechallengesbecauseofreceivingmanyordersforirregularshapeditems．Duetothespecialpropertiesofglass，theguillo

7、tineconstrainsmustbesatisfiedinthecuttingprocess．Comparedwithleatherorfabric，glasscuttingprocessismorecomplex．Thispaperisthefirstworkcombinesdifficultiesfromirregularityandguillotineconstrains．Thepaperaimsatproposingaheuristicalgorithmto2Dirregularguillotinebinpacki