单规格一刀切矩形排样问题的启发式搜索算法

发布时间：2018-08-22 10:06

【摘要】：针对单规格一刀切二维矩形排样问题,提出了一种启发式搜索算法,称为大小工件分治择优匹配(bigitem smallitem divide-and-conquer best-fit,简称BSDBF)启发式算法.该算法基于组化规则,提出了大小工件分治策略和组块快速举荐算法,是对组化策略的关键补充,这对优解获得至关重要.然后,择优选择适应度高的组块进行递归排样,贪心获得各块板材的排样方案.最后,基于设计的工件拆分方法,对初始解进行后处理小规模重排,进一步提升解的质量.因为没有随机因素,其获得的优解可复现,也是BSDBF算法区别于其他算法的典型特征.大量Benchmark案例的实验结果表明,BSDBF算法求解质量优于其他算法的报道结果.
[Abstract]:In order to solve the problem of one-size-fits-one-size-fit-2-dimensional rectangular layout, a heuristic search algorithm is proposed, which is called (bigitem smallitem divide-and-conquer best fit (BSDBF) algorithm. Based on the histochemical rules, this algorithm proposes a partition and conquer strategy for large and small jobs and a fast recommendation algorithm for blocks, which is a key supplement to the histochemical strategy, which is very important for obtaining optimal solutions. Then, the best selection of the high fitness of the block for recursive layout, greedy to obtain the layout of each plate. Finally, based on the proposed method, the initial solution is rearranged on a small scale to further improve the quality of the solution. Because there are no random factors, the obtained optimal solutions are repeatable, which is a typical characteristic of BSDBF algorithm which is different from other algorithms. Experimental results of a large number of Benchmark cases show that the solution quality of BSDBF algorithm is better than that of other algorithms.
【作者单位】： 广东省计算机集成制造重点实验室(广东工业大学);广东科贸职业学院信息工程系;
【基金】：国家科技支撑计划(2012BAF12B10) 广东省产学研项目(2012B091100025) 广东省科技计划(2015B010128007,2016A010106006) 国家自然科学基金(51675108)~~
【分类号】：TP18

【相似文献】

相关期刊论文 前10条

1 司佑全;二维排样问题中的优化算法及其在实际应用中的改进[J];煤矿机械;2005年11期

2 贾丹;董方敏;;二维优化排样问题研究[J];计算机系统应用;2008年07期

3 李薇;李健;;板料优化排样问题[J];电脑知识与技术;2011年20期

4 马广;刘嘉敏;黄有群;岳勇;Malcolm Keech;;一种有约束矩形排样问题的求解算法[J];沈阳工业大学学报;2006年04期

5 陈学松;;一种矩形排样问题的优化设计方法[J];锻压技术;2007年05期

6 赵政宝;楚纪正;尚颖;;用于求解二维圆形排样问题的自适应混合算法[J];计算机工程;2012年08期

7 杨彩君;张玉萍;;填充启发式算法的二维矩形排样问题[J];电子科技;2011年01期

8 宋亚男;徐荣华;杨宜民;叶家玮;;混合算法在排样问题上的应用研究[J];计算机工程与应用;2009年34期

9 宋亚男;徐荣华;叶家玮;;混合算法的邻域结构变更研究及在排样问题上的应用[J];计算机工程与科学;2011年02期

10 张玉萍,宋健,蒋寿伟;基于离散化和遗传算法的皮革制造中的排样问题[J];计算机工程;2004年23期

相关会议论文 前1条

1 黄红兵;蒋望东;;二维不规则零件排样问题的研究[A];广西计算机学会2004年学术年会论文集[C];2004年

相关博士学位论文 前1条

1 尚颖;圆形排样问题的研究与应用[D];北京化工大学;2011年

相关硕士学位论文 前10条

1 周炯;基于临界多边形方法的二维不规则件排样问题及其算法研究[D];华南理工大学;2015年

2 李华;基于块结构的二维排样问题的研究[D];广西大学;2016年

3 盛敬源;高层建筑模板排料问题研究[D];浙江理工大学;2015年

4 陈竞驰;二维不规则排样问题研究[D];厦门大学;2009年

5 石岩;基于遗传模拟退火算法的二维不规则多边形排样问题[D];西北工业大学;2007年

6 刘毅;排样问题及其算法的研究[D];华中科技大学;2006年

7 靳旭玲;二维不规则排样问题的研究[D];山东科技大学;2003年

8 方仍存;优化排样问题的近似算法[D];华中科技大学;2004年

9 晏贤梁;各向异性材料二维排样问题研究[D];武汉理工大学;2013年

10 凌少东;进化算法在排样问题上的应用[D];华中科技大学;2006年

，

本文编号：2196774