资源描述：
《基于填充算法的矩形件排样优化求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、中国机械工程第14卷第13期2003年7月上半月文章编号:1004-132Ⅹ(2003)13-1104-04基于填充算法的矩形件排样优化求解陶献伟王华昌李志刚摘要:针对矩形件优化排样问题,提出了一种将填充算法和遗传算法相结合的优化排样方法。该方法应用填充算法对遗传算法作预处理,使矩形件排样适用于“一刀切”的下料工艺,并克服了填充算法局部搜索的缺点,使搜索空间由一点扩大为多点,最终可获得总体最优的排样结果。算例表明,该优化排样算法运算速度快,具有广泛的适应性。关键词:矩形件;优化排样;填充算法;遗传算法陶献伟硕士研究生中图分类号
2、:TH162文献标识码:A矩形件优化排样是在给定的矩形板材上将一零件所有可能位置均进行测试和评估,且从中选系列矩形件按最优方式进行排布,以达到最大限择利用率最高的布局,则计算量极大。因此,必须度利用板材的目的,其实质是一个组合优化的二规定一些约束条件,以减少计算量,加速搜索。实维布局问题,具有工件种类多、数量大等特点,是际应用中,主要应满足如下约束:¹排样方案需计算复杂性最高的一类NP完全问题,至今还无要满足剪切工艺要求,采用一刀切的切割方式,且法找到解决该问题的有效多项式时间算法。同一类型的零件尽可能相邻排列,以提高切割生国
3、内外不少学者做了很多研究工作,曹炬产率;º工件相互靠紧,互不重叠,不能排到板材等[1]的背包算法具有很高的实用价值,崔耀东[2]之外;»符合最左最低原则,即第一个被选中的零件应放置在原料的左下角,其余零件则尽量放的组块技术能够得到较好的排样效果。但是,前者置在剩余空白的最左最低位置;¼对已经排放好是近似优化算法,后者是局部搜索方法,均未对遗的零件,在排放下一个零件时,其位置不变。传算法作任何预备处理,仅将遗传算法选择、复1.3生成条料制、交叉、变异思想应用于矩形件排样,达不到排排样问题是二维布局的问题,化二维布局为样的总体最优
4、,前者虽可达到最优解,但使运算量一维布局,即沿板材的宽度方向不断产生条料。按大规模增加,且不适合“一刀切”的下料工艺,仅适照何种方式在板材上产生条料,是优化排样需考用于“正交切割”。虑的问题。矩形件优化排样的条料生成方式一共笔者提出了一种填充算法,该算法是一种接有4种,本算法只涉及其中2种,即沿板材宽度方近最优解的局部搜索算法,适用于矩形件毛坯的向连续横排和连续纵排。优化排样。1.3.1连续横排1填充算法沿板材宽度方向对同一工件i连续横排,则沿板材宽度方向排满一列该种工件的数量t1=1.1毛坯排样的目标函数W/Wi,工件所排的
5、列数c1=Ni/t1。由于工件数目如何在板材上最大限度地下料,使板材的利的不同,可能会出现图1所示的4种情况。用率最高,是算法要解决的问题。设板材的长度为如果工件长度大于板材宽度,若采用连续横L、宽度为W、工件种类数为N,第i种工件长度为排方式,则与图1d对应的排样方式见图2。Li、宽度为Wi、数量为Ni,则优化排样的目标函数1.3.2连续纵排为沿板材宽度W方向对同一工件i连续纵排,Nmax6LiWiNi/(LW)则沿板材宽度方向排满一列该种工件的数量t2=i=1W/Li,工件所排的列数c2=Ni/t2。由于工件数目1.2约束
6、条件的不同,可能会出现图3所示的4种情况。为寻求零件在板材上的一个最优布局,若对根据工件的信息,算法判定工件是否排完。如收稿日期:2002—05—09修回日期:2002—06—30果没有,则依据判断准则决定选用连续横排或者·1104·基于填充算法的矩形件排样优化求解——陶献伟王华昌李志刚R1=NiLiWi/(c1W)R2=NiLiWi/(c2W)计算二者的最大值,即max{R1,R2},根据计算结果来决定选用何种排样方式,以确保局部利用率最高。1.5空白矩形的填充(a)工件数目(b)工件数目大于t1,由上述排样过程可知,不论采
7、用何种排列方小于t1且为整数列式,一般都会产生一块或者多块空白矩形(图1～图3中阴影部分为待填充的空白矩形)。如何对这些空白矩形进行填充,如何判断所选用的填充工件是最合适的工件,是问题的关键。1.5.1一般空白矩形的填充(c)工件数目大于t1,(d)工件不能在单第i种工件在对当前空白矩形进行填充时恰且为非整数列块板材上全部排列好能完全排样,从而产生的空白矩形,称为一般空图1连续横排的4种情况白矩形。显然,最原始的一般空白矩形即是板材本身。排列工件时,已经记录了空白矩形长度Lj和宽度Wj的信息,例如,图1c有2块待填充空白矩形,
8、分别为空白矩形1与空白矩形2。空白矩形1图2工件长度大于板材宽度与的参数为Lj1=Lic1,Wj1=W-Wit1;空白矩形2图1d对应的横排方式的参数为Lj2=Li,Wj2=W-Wi(Ni%t1)(%表示取余)。类似地,可以得到其它排样情况空白矩形的参数。每块空白矩形都可以视
