矩形件优化排样算法的研究与实现

《矩形件优化排样算法的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Y14047,so分类号：UDC：TP391．7密级：学校代号：10150学号：20052085峡建交通义挚硕士学位论文矩形件优化排样算法的研究与实现ResearchonRectangularOptimalLayoutAlgorithmandSystemImplementation学生姓名：导师及职称：学科门类：专业名称：赵晓东米小珍(教授)工学车辆工程研究方向：车辆协同设计与集成管理申请学位级别：论文答辩日期：学位授予单位：2008年1月4日大连交通大学摘要矩形件优化排样问题是指在矩形的板材上，要

2、排放多种不同尺寸的矩形件，如何使这些矩形件既不互相重叠，又不超出板材边界的条件下，使得材料的利用率达到最高。它广泛应用于玻璃、钢板、木材和皮革等。从数学计算复杂性理论看，优化排样问题属于具有较高计算复杂性的NP完全问题，至今还无法找到解决该问题的有效多项式时间算法【¨。好的排样结果可以提高生产效率，提高材料的利用率，降低生产成本，提高企业的竞争力。对矩形件优化排样问题的研究具有深远的理论意义和实际意义。本文在分析矩形件优化排样问题特点的基础上，建立了该问题的数学模型，描述了一些常见的优化算法和排样算

3、法。在一定的约束条件下，应用遗传算法方法对矩形件排样问题进行优化求解，对算例的求解结果进行比较与分析。首先介绍了矩形件优化排样问题的数学模型和矩形件排样问题的排样算法，如剩余矩形匹配法、BL算法、下台阶算法、基于最低水平线的搜索算法。比较了这些算法的优缺点。其次介绍了在大规模生产中矩形件的下料工艺，如“一刀切”；为了提高生产效率，相同的零件尽可能排放在一起；在加工时，要有安全距离的保障等。再次介绍了遗传算法的基本原理，采用遗传算法对矩形件排样问题进行求解。在求解过程中，给出了遗传算法的编码与解码方法

4、、适应度函数的定义方法、遗传算子的设计方法以及关键参数。通过对具体的算例进行求解，对求解的结果进行分析比较。最后，基于以上理论，用VB．NET开发了矩形件优化排样系统。其中包括用户登录模块，零件与板材管理模块，利用优化算法进行排样的模块等。本文将遗传算法与基于最低水平线的搜索算法相结合应用到矩形件排样优化中，产生的排样结果满足“一刀切”和相同的矩形件尽量排放在一起等工艺要求，并且使板材的利用率在9496左右，可以应用到企业的实际生产中。关键词：矩形件优化排样；排样系统；遗传算法；遗传算子；搿一刀切"

5、；大连交通大学工学硕十学位论文AbstractTheproblemofrectangularlayoutistoputvariousdifferentsizesrectangularobjectsintostocksheets，howtomaketheratioofmaterialhighlyundertheconditionofnointerferenceandnotbeyondtheboundaryLH．Itisextensivelyappliedintotheglass，steelplate，

6、timber，leatheretc．Frommathematicscalculationcomplexitytheory，theproblemwhosecomputationisthemostcomplexintheorybelongstotheNPcompleteproblem．Thesolutionofthevalidpolynomialtimecalculatewaycan’tfindoutbynow．AgoodpackingschemeCannotonlysaverawmaterialand

7、reduceproductioncost，butalsobringeconomicbenefitforandenhancethecompetitivenessofenterprises．Therefore，researchontheproblemofoptimallayoutforrectangularpartisveryimportantintheoryandapplications．Inthispaper,thefeaturesofproblemarestudiedanditsmathemati

8、csmodelisestablished．Somekindofoptimalalgorithmsandcommonlayoutalgorithmsfortheoptimallayoutofrectangularpartareintroduced．Undercertainconstraints，geneticalgorithmisappliedintotheoptimallayoutofrectangularpart．Theresultsofinstancesareco