资源描述：
《填充启发式算法的二维矩形排样问题0》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、协议#算法及仿真2011年第24卷第1期ElectronicSci1&Tech1/Jan115,2010填充启发式算法的二维矩形排样问题杨彩君,张玉萍(上海师范大学信息与机电工程学院,上海200234)摘要针对小矩形切割的二维排样问题,尤其是对玻璃或厚钢板等材料,在切割时定向一次性切割到头的排布,结合综合蚂蚁算法和模拟退火算法思想,提出了一种最低水平线与填充式算法相结合的启发式排样算法。通过对计算机上随机产生的实验数据进行模拟,实现了自动排样。实验表明,该算法提高了单次切割的材料利用率,得到较好的排样效果。关键词排样;矩形件;启发式;填充式算法中图分
2、类号TP30116文献标识码A文章编号1007-7820(2011)01-050-03AFillingHeuristicAlgorithmfortheTwo-dimensionalRectanglePackingProblemYangCaijun,ZhangYuping(CollegeofMechanicalandElectronicEngineering,ShanghaiNormalUniversity,Shanghai200234,China)AbstractThepackingproblemofcuttingtheoptmiallayoutof
3、smallrectanglesonapalletisconsidered.Combiningtheantalgorithmwiththesmiulatedannealingalgorithm,amixednewalgorithmoflayoutoptmiization,whichismiplementedbythelowesthorizontalandfillingalgorithm,isproposedinthispaper.Inordertoinvestigatethecomputation,numericaltestswithrandomlyg
4、eneratedinstancesarecarriedout.Bycomparison,thesolutionsshowtherobusteffectivenessofthisapproach.Theresultsshowthatthisapproachachievesabettereffect.Keywordspackingproblem;rectangle;heuristics;fillingalgorithm二维矩形排样问题,从数学计算复杂性理论来程,从实际排样过程中所积累的经验出发,为矩形排看,它属于具有最高计算复杂性的一种NP(Nondet
5、er-样问题的高效快速求解提出了一种新颖的填充式启发[2-3]ministicPolynomial)完全问题。因为存在实际形状的式算法。复杂性和计算上的复杂性,求解困难,而排样布局的1排样模型优劣直接与材料成本及经济效益有关。目前存在的主要问题是材料利用率低,浪费严重。对于规模较大的设已知排样所用材料的长为L,宽为W(LW),机械制造、装物及皮革的箱包下料、玻璃切割等厂家所有待排的矩形件共有M种,第i种矩形件个数Ni,其来说,即使其材料利用率有很小的提高,也将会带来长为Li,宽为Wi(1[i[N)。则所有待排的矩形件的巨大的经济利益。由于这些问题可
6、以形式化为一个矩个数是N=ENi。优化排样的基本目标是:在待排矩形排样问题,因此,从简化下料工艺等角度出发,人形在材料上互不重叠,也不能超越材料边界的前提下,们开始寻找兼顾解的质量以及运行时间的高效启发式[1]快速生成排样,同时提高材料利用率。算法。定义排样布局的原材料的利用率为Emax,Emax越为此,不少中外学者提出了近似算法,如模拟退大,材料的利用率越高。则材料优化的排样模型为火(SimulatedAnnealing)、遗传算法(GeneticAlgo-rithms)等。但由于这些算法自身存在一定的局限性,Emax=E(Li@Wi@Ni)/L@
7、W(1)实际排样结果不尽人意。如遗传算法理论从概率上以2算法基本思想和基本策略随机方式寻求到最优解,但实际应用中却不是成功的最优化算法。文中通过实际钢板、玻璃等切割工艺过211填充式启发式思想的来源排放算法是实现矩形件排样的关键。使任何一个收稿日期:2010-07-06待排放小矩形在不超越材料的情况下,满足BL(Bo-t作者简介:杨彩君(1984-),女,硕士研究生。研究方向:tom-Left)算法。工人在切割钢板材料的过程中,一计算机辅助设计。个重要的规则是:先角后边。事实上,据观察和了50www1dianzikeji1org杨彩君,等:填充启发式
8、算法的二维矩形排样问题协议#算法及仿真解,有一个特别有用的规则:在切割钢板材料时,师{傅总是拉一根水平线,然
