应用递归划分策略解决矩形件剪切排样问题  

Application of recursive partitioning strategy in solving guillotine cutting problem of rectangular piece

作　　者：沈萍[1] 邓国斌[1] Shen Ping,Deng Guobin(Department of Computer and Electronic Information Engineering, Guangxi Vocational ＆ Technical College, Nanning 530226, Chin)

机构地区：[1]广西职业技术学院计算机与电子信息工程系

出　　处：《锻压技术》2018年第3期181-185,共5页Forging & Stamping Technology

基　　金：广西自然科学基金资助项目(2015GXNFBA139264);广西教育厅科研项目(KY2016YB610)

摘　　要：针对机械制造领域的矩形件剪切排样问题,提出一种基于递归划分思想的排样算法。用两条互相垂直呈T型的剪切线将板材划分为3个子板,称板材的左下角子板为排样块,称其余两个子板为递归块。对于排样块,按照简单方式排放矩形件;对于递归块,将其看做板材继续划分。用隐式枚举算法确定排样块的最优排样方式,得到块中排放的最优矩形件种类和矩形件的行列数;用分支定界算法确定递归块是否继续划分。采用基准例题将本文算法与文献算法进行对比,实验结果表明,本文算法排样价值高于文献算法,且计算时间能满足实际应用需要。To discuss the guillotine cutting problem of rectangle piece in machinery manufacturing field,a cutting algorithm based on recursive partitioning was proposed. With two cutting line that perpendicular to each other and with T shape,the plate was divided into three sub plates,in which the lower left corner sub plate was called layout block,and the remaining two sub plates were called recursive blocks. For layout block,rectangle piece was discharged in a simple way,and for the recursive block,it was considered as plates to be divided. The implicit enumeration algorithm was used to determine the optimal pattern of the layout block,and the optimal rectangle type and the number of rows and columns of rectangles in the block were obtained. The branch and bound algorithm was used to determine whether the recursive block continues to be divided or not. The benchmark instances are used to compare the proposed algorithm with the literature algorithms. Experimental results show that the proposed algorithm is superior to the literature algorithms in the pattern value,and the computation time can meet the practical use.

关 键 词：剪切排样问题 排样算法 递归划分 隐式枚举 分支定界 

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