一种矩形件优化排样算法的研究.pdf

一种矩形件优化排样算法的研究 张摇 伟摇 摇 安鲁陵摇 摇 孙金虎 (南京航空航天大学机电学院,南京摇 210016) 文摇 摘摇 针对在具有一定长宽尺寸的板材上进行矩形件排样的问题,结合遗传算法,设计了一种矩形件优 化排样算法。 该算法考虑到排样高度不超过板材长度的要求,可以实现换板,使剩余待排矩形件在新板材上继 续排放。 通过算例验证了该算法的有效性和合理性。 关键词摇 二维装箱问题,矩形件排样,遗传算法,复合材料 Research on Rectangular Packing Algorithm Zhang Wei摇 摇 An Luling摇 摇 Sun Jinhu (College of Mechanical and Electrical Engineering,Nanjing University of Aeronautics and Astronautics,Nanjing摇 210016) Abstract摇 A rectangular packingalgorithmbasedontwo鄄dimensionalbinpackingproblemwasdesigned.Theal鄄 gorithm was hybridized with Genetic Algorithm to solve rectangular packing problem. In consideration of the packing height not exceeding thelength of board,anew boardwasaddedto arrangetheremaining components.Examplesshow that the presented rectangular packing algorithm is effective and reasonable. Key words摇 Two鄄dimensional bin packing problem,Rectangular packing algorithm,Genetic Algorithm,Composite [4] 1摇 前言 法 ,对29个具有不同长宽尺寸的复合材料矩形零 制造复合材料构件时需先完成预浸料毛坯展开、 件在一定长、宽的板材上排样,得到图2所示的结果, 进行排样、组合下料、然后再铺层、形成构件。 如何排 图中黑色区域是被浪费的区域,可以看出常规的方法 样、下料,以减少废料、降低成本是航空业迫切需要解 存在以下问题。 决的问题。 复合材料铺层排样通常可转化为矩形件 [1] 排样问题来研究 。 根据排样区域的具体情况,矩 形件排样可以分为二维条料排放和二维装箱问题两 大类。 目前,国内对二维条料排放问题研究较多,本 文主要研究二维装箱问题。 2摇 已有矩形件排样算法分析 [2] 二维矩形件的启发式和砌墙式算法 、最低水 [3] [4] 平线排样算法 、最低轮廓线有哪些信誉好的足球投注网站排样算法 等应 图1摇 换板排样示意图 用较多,由文献[4]可知,最低轮廓线有哪些信誉好的足球投注网站排样算法 Fig.1摇 Sketch map of packing on a new board 的排样效果较好。 在实际生产中,复合材料板材往往 (1)第一块板材上右边缘材料浪费过多。 有长度限制,将待排零件排放到板材上时,排样高度 (2)在第一块板材上排R零件时,虽然零件排放 不能超出板材的长度要求。 若零件排放到轮廓线后, 时排样高度会超出板材的长度范围,但是并不代表R 排样高度超过板材长度,则需要换板排放此零件(图