矩形件优化排样的一种启发式算法.pdf

2302010,46(12)
Computer Engineering and Applications计算机工程与应用
矩形件优化排样的一种启发式算法
陈仕军,曹炬
CHEN Shi-jun, CAO Ju
华中科技大学数学与统计学院,武汉430074
School of Mathematics Statistics, Huazhong University of Science &Technology, Wuhan 430074, China
E-mail:chenshijun10@gq.com
CHEN Shi-jun, CAO Ju Heuristic algorithm for rectanular uing stock problem. Computer Engineering and Applica
tions,2010,4(12):230-232
Abstract: A fast and efficient heuristic packing algorithm is presented for large-scale orthogonal packing problem. For the present
packing position horizontal line), this paper uses greedy method to choose the combination of unpacked rectangles that satisfy pack
ing conit on Acring o e matching degree of packing osit on and its corresponding combination of rectangles, it chooses op-
timal packing position(optimal horizontal line)for packing For the convenient of later packing, it ranks the rectangles combination
of packing position with height before packing Three largest-scale st instances containing 196 or 17 pieces supplied by E Hop
per are computed by the algorithm of his paper, he utilization ratios of all are beyond 99%, the average utilization ratio and
consumed time are 99.38% and 1.12 seconds respectively. Compared with
the best results that have been published in related pa
pers it is showed the efficien of a thm of this paper for solving large scale rectangle packing problem.
Key words: rectangular cutting stock problem optimal horizontal line; packing algorithm
摘:对大規模矩形件正交排样问题,提出了一种快速高效的启发式排放算法。对当前的可排放位置(水平绒),用贪婪算法从未
排矩形件中选择可排放于该水平的最倪矩形件组合块;根据各个排放位置与其对应的矩形件组合块的匹配程度,选择最优的可
排放位置(最优水平线)优先排放。在排放时,为了便于后续排放,先将待排放位置对应的矩形件组合块从低到高进行排序,再排
放。对E.Hper提供的规模最大的一类实例进行计算,排样率都在99%以上,平均排样率达到了9938%,平均计算时间只用了
1.12秒。与相关文献最好结果进行了比较,结果表明该文算法解决大規模的矩形件排样具有高效性
关键词:矩形件排样;最优水平线;排放算法
DOL:10.3778-isn-1002-8331.2010.12.069文章编号:1002-833(2010)12-0230-03文献标识码:A中图分类号:TP3016
1引言
上述算法,虽然都取得了一定的效果,并且有一些已经应用于
矩形件排样的优化问题,是将数量大的小矩形件尽可能多生产中,但当诃题规模较大时,计算时?仍然较长。因此,找到
地无重叠地排放到一个定宽、定长(或无限长)的矩形板材上,一种高效的针对大规模矩形件的优化排样方法,意义重大。矩
使其利用率达到最大。矩形件排样问题,广泛存在于钣金下料、形件排样问题的种类较多,目前还不存在一种实用于所有问题
玻璃切割、电路布局、报刊排版等T业生产中。当前,工业原材的有效算法。受到前人工作的启发,作者提出一种新的针对大
料特别是钢材等重工业原料资源短缺,如何提高材料的利用率规模矩形件排样的启发式算法。与一般启发式算法一样,主要
是企业面临的重大问题,对节能减排,建没资源节约型、环境友解决如下两个问题:如何从未排矩形件中选择待排矩形件,以
好型杜会具有重要意义。对企业来讲,如果花费太长的时间来及如何选择排放位置。该文基于对当前和长远相结合的启发式
提高原材料的利用率,就无益于提高生产效率。因此,如何用最思想,即:一方面,要使排放过的矩形件尽可能紧凑(尽可能少
短的时间将材料的利用率提高到最高,是目前研究的热点。为地产生浪费区域);另一方面,还要使当前排放有利于未排矩形
此,国内外众多学者提出了一些有效的算法。这些算法大致分件的后续排放。在具体做法上,与一般文献中将矩形件选择和
为两类:一类是启发式算法,例如曹炬提出了青包算法叩、黄文位置选择分成两步或者毎次考虑一个未排矩形件不同?,该文
奇提出了基于占穴思想的启发式算法の、贾志欣提出了最低水将矩形件的选掙和位置的选择结合起来考虑,利用贪婪算法,对
平线排放算法?,都取得了较好的效果。另一类算法主要是利用各个可排位置选择出最合适的一组矩形件,即最优矩形件组
现代智能算法,例如遗传算法、模扎拟退火算法、蚂蚁算法、粒子合。根据各可排位置与其最优矩形件组合的匹配程度,选择最
群算法等,结合某种排放规则,例如BL、DP等,进行优化排样。优的排放位置(最优水平线)优先排放,这使得当前排放矩形件
作者简介:陈仕军(1980-),男、硕土研究生,主要研究领域为NP难问题的近似计算;曾炬(1955),男,博土,教授,主要研究领域为NP难问题的
近似计算、计算机辅助设计。
收日期:2008-10-27修回日期:2009-01-13
万方数据