生成最优同形块两阶段布局方式的确定型算法  

Deterministic algorithm for optimal two-stage cutting layouts with same-shape block

作　　者：季君[1] 邢斐斐[2] 杜钧[1] 师宁[1] 崔耀东[3] 

机构地区：[1]北京电子科技职业学院自动化工程学院,北京100176 [2]北京机电院高技术股份有限公司,北京100027 [3]广西大学计算机与电子信息学院,南宁530004

出　　处：《计算机应用》2014年第5期1511-1515,共5页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61063031;60975046);北京电子科技职业学院科研项目(YZK2013009)

摘　　要：为解决大规模二维布局问题,提出一种生成同形块两阶段布局方式的确定型算法。首先通过动态规划确定最优同形块;然后求解背包问题确定同形块在同形级中的布局方式和同形级在同形段中的最优布局方式;最后选择两个同形段生成最优同形块布局方式。通过43道基准测题,将该算法与经典两阶段和三块算法进行比较。实验结果表明,该算法不仅能满足剪切工艺,在计算时间和板材利用率上优于以上算法,而且能在合理时间内取得好的优化结果。A deterministic algorithm for two-stage cutting layout with same-shape block was proposed to solve the large- scale two-dimensional cutting problems. The algorithm used dynamic programming to generate the optimal same-shape block, solved the knapsack problem to determine the optimal layout of the same-shape block in the same-shape section and the same- shape section in the same-shape segment, and optimally selected the two segments to compose the optimal same-shape block layout. The algorithm was tested through 43 benchmark problems, and compared with the classic two-stage and the three-block algorithms. The experimental results indicate that the algorithm is superior in both computation time and material usage rate, it not only meets the requirements of shearing and punching process, but also achieves good results within reasonable time.

关 键 词：布局 同形块 动态规划 背包问题 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]