“一刀切”约束下矩形件优化排样算法比较与整合的研究

《“一刀切”约束下矩形件优化排样算法比较与整合的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ThesisSubmittedtoHebeiUniversityofTechnologyforTheMasterDegreeofManagementScienceandEngineeringRESEARCHONCOMPARISONANDINTEGRATIONOFRECTANGULAROPTIMALLAYOUTALGORITHMSUNDERCONSTRAINTOFGUILLOTINEByLiuQianSupervisor:Prof.KongZaojieDecember2012河北工业大学硕士学位论文“一刀切”约束下的矩形件

2、优化排样算法比较与整合研究摘要矩形件排样问题是一类在计算理论上非常复杂，但在实际生产中应用广泛的问题，它普遍存在于工业生产的许多领域，且占有重要的地位。一个好的排样方案可以有效提高原材料利用率，降低生产成本，直接给企业带来经济效益。因下料工艺及板材情况的不同，矩形件排样问题又需要分为几类问题来解决，其中一类就是在优化下料时必须满足直线切割的“一刀切”排样问题，它普遍存在于玻璃切割、报刊排版、家具生产等行业中，本论文就是针对这类问题进行的研究。为了能够找到更好的排样方案，查阅了大量国内外相关文献资料，对优化排样的相关算法进行了

3、深入的研究。本文首先给出论文研究的背景及意义，总结并分析了矩形件优化排样问题的国内外研究现状，然后对矩形件优化排样问题的相关理论进行概述，建立了所要研究问题的数学模型，介绍了几种常见的启发式排样算法，并对各算法的优缺点进行比较分析，基于分析结果，提出一种改进的最低轮廓线搜索算法，并将其作为遗传算法的解码方法进行应用。随后介绍了遗传算法和蚁群算法的基本理论，基于所研究问题的特点，将两种基本算法进行了设计与改进，给出两种算法求解矩形件排样问题的具体步骤，之后通过一个具体算例对两种算法的性能进行测试与比较分析。接下来，基于两种算法

4、的对比结果及对两种算法整合的可行性及基本原理的分析与介绍，确定采用遗传算法和蚁群算法整合形成的混合算法来求解矩形件排样问题，着重研究了两种算法最佳融合时机的确定方法，通过分析现有混合策略的不足，提出一种改进的混合策略，给出了混合算法求解矩形件排样问题的具体步骤，并通过现有混合算法和改进后的混合算法分别对算例进行求解，综合比较了遗传算法、蚁群算法、现有混合算法和改进混合算法的算法性能，计算结果表明，改进后的混合算法在优化性能和时间性能上都优于单纯的遗传算法和蚁群算法，同时也优于现有混合算法，其在解决“一刀切”排样问题时更为有效

5、。最后对本文进行总结与展望。关键词：“一刀切”，矩形件优化排样，遗传算法，蚁群算法，算法融合i“一刀切”约束下的矩形件优化排样算法比较与整合研究RESEARCHONCOMPARISONANDINTEGRATIONOFRECTANGULAROPTIMALLAYOUTALGORITHMSUNDERCONSTRAINTOFGUILLOTINEABSTRACTTheproblemofrectangularlayoutisverycomplicatedincomputingtheory,butithasgottheextensivea

6、pplicationintheactualmanufacture.Itprevalentinmanyareasofindustrialproduction,andoccupiesanimportantposition.Agoodpackingschemecanimprovetheutilizationofrawmaterialseffectively,reducetheproductioncostandbringeconomicbenefitsforenterprises.Becauseofthedifferentofcut

7、tingcraftandplatesituation,theproblemofrectangularlayoutneedtobedividedintoafewproblemstosolve.Oneclassiscuttingstockmustmeettheconstraintofguillotine,itprevalentinmachiningofglass,newspapertypesettingandfurnituremanufacturing.Theresearchinthispaperisforthiskindofp

8、roblem.Inordertofindabetterrectangularlayoutprogram,consultendalargenumberofdomesticandforeignliterature,in-depthstudyontherectangularoptimallayo