排板王算法的分析与研究

AnalyseAndResearchOfLayoutAlgorithm排板王算法的分析与研究黄健英(计算机科学与技术师范专业)指导老师唐晓辛高级工程师摘要：矩形件排样优化问题是一个多目标优化问题，一方面要考虑到材料的利用率，另一方面要考虑到生产时的下料效率，而且还要满足“一刀切”的工艺要求。矩形件排样优化问题实际上是一个十分困难的问题，从数学计算复杂性理论看，它属于具有最高计算复杂性的一类问题——NP完全问题。从另一方面看，矩形件排样优化问题也属于人工智能领域方面研究的课题之一。通过对排料需求的分析和对当前流行算法的了解上，我们采用十字线法为主，基于分合的排料算法为辅完成了电脑自动排料系统--《排板王》，可同时兼顾材料利用率和切割时的生产效率，为企业的生产降低了成本，提高了产品的竞争力！关键词：十字线法排料排样排板启发函数AnalyseAndResearchOfLayoutAlgorithmJianYingHuangDirectedbySeniorEngineerXiaoXinTangAbstract:Rectangularlayoutproblemisaproblemwhichhavesometargets.Onesideitnustconsidertheutilizationratioofthematerial,anothersideitconsiderstheefficiencyoflayingoffwhenisproducting,furthermore,itshouldsatisfythecraftworkrequirementofcuttingfromthethresholdtotheendwithoneknife.Infactretangularlayoutproblemisaverydifficultproblem,Fromthemathmeticalcomputationcomplexitytheory,itbelongstotheseriesproblemwhichhavethemostcomputioncomplexity—NPcompleteproblem.Fromtheotherside,retangularlayoutproblemisoneofthetaskofartificialintelligenceresearch.Afterinvestigatingandextractingsomeexperimentoflayoutsoftwareinthemarket,thekingoflayoutsoftwaremostlyusesthecrossalgorithmtocompletetheprocessoflayout.Itcangiveattentiontotwoormorethingsofmaterialutilizationratioandproductiveefficiency.Keywords:CrossAlgorithmLayoutLightFunction第一章矩形件排样优化的十字算法引言矩形件排样优化是指在给定长和宽一定数量的板材上，尽可能多地排放所需要的矩形件，使得所需要得板材尽可能少，以达到节省材料的目的。矩形件优化问题实际上是一个非常困难的问题，从数学计算复杂性理论看，它属于具有最高计算复杂性的一类问题——NP完全问题。也就是说在一般情况下，即使使用当今最快的计算机，在人们可接受的时间内也不可能求出这类问题的最优解。另一方面由于生产实际的需要，人们又迫切需要利用现代科技对这一问题给出一些能满足生产需要的求解方法。这些方面应该是能以较高的计算速度给生产者一个好的解。所谓的解是指虽然不是最优的解，但是接近最优解，并且应比人工排样的效率高，能达到或超过人们所期望的材料利用率。国内外有不少学者在这方面已做了很多工作，构造了一些近似算法。近似算法是指这些算法的计算结果接近或达到最优解，同时计算速度非常快。矩形件的排样在各个生产企业内都经常遇到，因此在排样算法的构造方面必须考虑到这些企业的下料工艺。我们通过自己的测试后，采用十字线法完成了电脑自动排料系统--《排板王》，可同时兼顾材料利用率和切割时的生产效率，为企业的生产降低了成本，提高了产品的竞争力！第一章矩形件排样优化的十字线法1.1十字线法描述排板王所用到的算法主要十字线法。算法简述如下：设待排板材的长宽分别是L、W，板材的数量足以排下所有要排的s种矩形件，第i种矩形件的个数是ni，长度是li，宽度是wi，于是所有要排的矩形件的个数是n=ii=1ni,设总共用了N张板材，目标是矩形零件在板材上互不重叠的前提下尽可能地提高板材的利用率1()maxiiliwinifNLW,也就是在满足要求的前提下使用尽可能少的板材。排板王基本思想是将一张板材通过划十字线的方法分为4块，选出4种零件依次排入4块矩形中，考虑材料利用率的同时也考虑生产时的下料效率。排在板材上的第一种零件有s种选择，假设第一次排在板材上的零件处于板材的左下角，选择连续横排的情况考虑（纵排的情况类似）。假设选择了第i种零件，则一排最多可以[L/li]个零件，最多可以排[W/wi]行，在排样中每行排了m个零件，共排了n行,所以1≤m≤min([L/li],ni),1≤n≤min([W/wi],ni)。这样通过划十字线，第一块板材就分成了4部分A、B、C、D，如图2所示。第一章矩形件排样优化的十字算法图1板材分成4部分矩形A的长是x，宽是y,并且x=mli,y=nwi；矩形B的长是x，宽是w-y；矩形C的长是L-x,宽是W-y；矩形D的长是L-x,宽是y。设板材左下角坐标是（0，0），P的坐标是（x,y），我们的目标就是在如图所示的点P（x,y）的变化过程中，寻找合适的x,y使得在区域A，B，C，D排下足够多的零件后，浪费的材料最少。假设选择第i种零件排在矩形A中，选择第j种零件排在矩形B中，选择第k种零件排在矩形C中，选择第t种零件排在矩形D中。这样，区域A可以利用的面积是min(xy,liwini)，区域B可以利用的面积是min（[L-x/lj][W-y/wj],nj）ljwj，区域C可以利用的面积是min（[L-x/lk][W-y/wk],nk）lkwk，区域D可以利用的面积是min（[L-x/lt][W-y/wt],nt）ltwt。于是，接下来的目标就是选择适当的i,j,k,t使下式最小：Ming=LW-min(xy,liwini)-（[L-x/lj][W-y/wj],nj）ljwj-（[L-x/lk][W-y/wk],nk）lkwk-（[L-x/lt][W-y/wt],nt）ltwtx=mliy=nwi1≤m≤min([L/li],ni)1≤n≤min([W/wi],ni)1≤ij,k,t≤s这是一个离散的优化问题，从而也使问题简单化了。我们可以先随机选择一个i(1≤i≤k),再选择m、n,m、n满足以下条件：1≤m≤min([L/li],ni)，1≤n≤min([W/wi],ni)，再找到合适的零件种类j,k,t使得以上的目标函数取最小值。一张板排完以后，更新零件的数目，用同样的办法排第二张板。值得注意的是排到最后，每种零件的数目不是很多，所有剩余的零件的面积可能小于一张板的面积，这样再用以上的方法排样，板材的利用率不会太高，所以排最后一张板的时候，可以考虑用另外的一种方法：在用以上的方法排样后，减少板材的长度，将一块板材分为几部分，对每一小部分用以上介绍的搜索算法进行排样，这样可以提高板材的利用率。算法步骤如下：步骤1：对整张板材采用搜索算法，寻找零件的最优组合；步骤2：如果步骤1产生的零件组合的利用率大于某个给定的值则接受该种零件组合，否则转步骤3；步骤3：将整张板材分成几小部分，对每一小部分调用步骤1的搜索算法进行寻优。第一章矩形件排样优化的十字算法1.2十字线法存在问题在上面描述十字线法的过程中，基本思想是将一张板材通过划十字线的方法分为4块，选出4种零件依次排入4块矩形中。首先我们选择经过排序后，优先级别比较高的第i种零件，并把它排在板材的左下角，把它排成类矩形A；然后根据矩形A的上边长与右边宽分别平衡于x轴与y轴做十字分割，选择第j种零件排在矩形B中，选择第k种零件排在矩形C中，选择第t种零件排在矩形D中。与此相同，我们分别在矩形B、矩形C、矩形D中分别把第j种、第k种、第t种零件都排成类矩形。而在这四个矩形中，利用率都没有达到100%，换另外一句话来说，就是在这个四个矩形中，还存在着或多或少的还没有充分利用到的地方。如图2图2阴影i、阴影j、阴影k、阴影t分别是第i种、第j种、第k种、第t种零件所占的面积。可以看出在分别排了这几种零件后，在板材上还空出了相当大的一部分空间，这就是还没有充分利用到的地方。那么，如何才能更好的利用这块板材呢？如图3所示，沿着阴影j上边的长，平衡于x轴，沿着阴影k右边的宽，平衡于y轴，以虚线对板材进行二次切割。图3这个切割的主要标准是，比较阴影j与阴影k的宽，然后选取宽度长的阴影，沿着它上边的长，平衡于x轴切割，比较阴影k与阴影t的长，选取长度相对比较长的阴影，沿着它右边的宽，平衡于y轴切割。屏弃掉板材二次切割后的左下边部分，继续调用十字线法进行排样。在二次切割以后，板材的利用率就会比第一次切割提升了很多。但是从图3来看，这个十字线法还是存在着很大的不足。在这个已经屏弃掉板材二次切割后的左下边部分，可以看得出还是存在着很大的一部分板材还没有利用上，这个就是十字线法到目前为止的不足之处。第二章基于动态分割与合上的排样算法第二章基于动态分割与合上的排样算法2.1改进十字线法如何合理地在原矩形板材上切割给定规格的矩形零件，以提高原板材的利用率是一个有重大经济意义的课题。目前的切割算法有多类，如早期的线性规划算法和动态规划算法，它们存在的主要问题是计算时间和空间呈指数增长，并且假定供排料的矩形件总数是无限的,那么实际上算法是不可用的。启发式算法是对动态规划算法的改进，其效率完全依赖于启发函数的定义，难以调和计算时间与材料利用率之间的矛盾。具有类比学习的排料算法虽然引入了重要的类比学习思想，可逐渐减少系统的排料时间。一个具有类比学习机制的二维图形优化排料系统首先将不规则图形的排料问题转化为矩形件的排料问题，然后利用启发式搜索方法,求得较优解。但系统没有自动从排料经验中学习的能力，系统学习是通过人机交互式完成的，模式排料的利用率极大地依赖于专家的能力，但是对规模较大的排料，专家排样本身都不可能做到真正的优化。特别是这些算法都只实行二维切割而没有进行必要的余料合并，因此会产生很多分散的不能排样的余料碎片，不但大大降低了材料的利用率，而且极大地影响了切割速度。这里提出了一种基于动态分割与合一的优化排样算法，优化排样的目的是根据给定待排零件对板材进行最优切割使得板材的利用率尽可能的高。2.2排样模型假定每次排料总是将零件排在板材(L,W)的左上角，并且将板材和零件都置于一个坐标平面，则此矩形零件(li,wi)在板材上的位置可由其左上角坐标(xi,yi)和排料方式m完全确定。排样过程就是根据寻优规则，确定每个零件在板材的左上角坐标(xi,yi)、排料方式mi:竖排或横排以及切割方式ci:竖切或横切。因此排料模式S有4种不同的组合，再加上不排所选择的零件，共5类模式，如图4。不同模式决定了板材余料的坐标和后继的排料效率。但无论哪种模式，切割后的余料只有两种。因此排样过程就是与或树的搜索过程。此与或树或结点是确定排样模式，如图4的N结点。与结点是某排样模式的余料分割,如图4的M结点。而排样结果则是一棵典型的二叉树,如N-M-(K,L)。图4第二章基于动态分割与合上的排样算法与或树搜索过程具有很高的复杂度，属NP完全问题，因此零件及排样模式的选择必须采用启发算法。算法1零件选择算法传统算法均采用零件的面积为排样的启发信息，即越大越优先，这比较符合直觉，但实际应用中还存在着一些重要件要优先切割，而且面积越大不一定材料利用率就越高。