排板王算法的分析与研究(荐)

《排板王算法的分析与研究(荐)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、排板王算法的分析与研究黄健英（计算机科学与技术师范专业）指导老师唐晓辛高级工程师摘要：矩形件排样优化问题是一个多目标优化问题，一方面耍考虑到材料的利用率，另一方而要考虑到生产时的下料效率，而冃述耍满足“一刀切”的工艺要求。矩形件排样优化问题实际上是一个十分困难的问题，从数学计算复杂性理论看，它属于具有最高计算复杂性的类问题——NP完全问题。从另一方面看,矩形件排样优化问题也属于人工智能领域方面研究的课题之一。通过对排料需求的分析和对当前流行算法的了解上，我们采用十字线法为主，基于分合的排料算法为辅完成了电脑自动排料系统一《排板王》，可同时兼顾材料利用率和切割时

2、的生产效率，为企业的生产降低了成本，提高了产品的竞争力！关键词：十字线法排料排样排板启发函数AnalyseAndResearchOfLayoutAlgorithmJianYingHuangDirectedbySeniorEngineerXiaoXinTangAbstract:Rectangula/rlayoutproblemisaproblemwhichhavesometargcts.Onesideitnustconsidertheutilizationratioofthematerial,anothersideitconsiderstheefficiency

3、oflayingoffwhenisproducting,furthermore,itshouldsatisfythecraftworkrequirementofcuttingfromthethresholdtotheendwithoneknife.InfactretangularlayoutproblemisaverydifficuItproblem,Fromthemathmeticalcomputationcomplexitythcory,itbelongstothescriesproblemwhichhavethemostcomputioncomplexi

4、ty一NPcompleteproblem.Fromtheotherside,retangularlayoutproblemisoneofthetaskofartificialintelligenceresearch.Afterinvestigatingandextractingsomeexperimentoflayoutsoftwareinthemarkethekingoflayoutsoftwaremostlyusesthecrossalgorithmtocompletetheprocessoflayout.Itcangiveattentiontotwoor

5、morethingsofmaterialutilizationratioandproductiveefficiency.Keywords:CrossAlgorithmLayoutLightFunction矩形件排样优化是指在给定长和宽一定数量的板材上，尽可能多地排放所需要的矩形件，使得所需要得板材尽可能少，以达到节省材料的目的。矩形件优化问题实际上是一个非常困难的问题，从数学计算复杂性理论看，它屈于具冇最高计算复杂性的一类问题——NP完全问题。也就是说在一般情况下，即使使用当今最快的计算机，在人们可接受的时间内也不可能求出这类问题的最优解。另一方面由于生产实际

6、的需要，人们又迫切需要利用现代科技对这一问题给出一些能满足生产需要的求解方法。这些方面应该是能以较高的计算速度给生产者一个好的解。所谓的解是指虽然不是最优的解，但是接近最优解，并且应比人工排样的效率高，能达到或超过人们所期望的材料利用率。国内外冇不少学者在这方面已做了很多工作，构造了一些近似算法。近似算法是指这些算法的计算结果接近或达到最优解，同吋计算速度非常快。矩形件的排样在各个生产企业内都经常遇到，因此在排样算法的构造方面必须考虑到这些企业的卜•料工艺。我们通过白己的测试后，采用十字线法完成了电脑自动排料系统一《排板王》，可同时兼顾材料利用率和切割时的生产

7、效率，为企业的生产降低了成本，提高了产品的竞争力！第一章矩形件排样优化的十字线法1.1十字线法描述排板王所用到的算法主要十字线法。算法简述如下：设待排板材的长宽分别是L、W,板材的数量足以排卜•所有要排的s种矩形件，第讶中矩形件的个数是m长度是I,宽度是叫，于是所有要排的矩形件的个数是n二£ni,设总共用了N张i=l板材，目标是矩形零件在板材上互不重叠的询提下尽可能地提高板材的利用率工（“W加）于二max，也就是在满足要求的前提下使用尽可能少的板材。排板王基NLW本思想是将一张板材通过划十字线的方法分为4块，选出4种零件依次排入4块矩形中，考虑材料利用率的同时

8、也考虑生产时的卜'料效率。排在板材上的