基于均匀条带排样方式的二维下料启发式算法  

A heuristic algorithm for two dimensional cutting stock problem based on uniform strip pattern

作　　者：王祺[1] 张春利[1] 龚击 Wang Qi Zhang Chunli Gong Ji(Experimental Teaching Center, Hebei Finance University, Baoding 071051, China Nanning University, Nanning 530200, China)

机构地区：[1]河北金融学院实验教学中心,河北保定071051 [2]南宁学院,广西南宁530200

出　　处：《锻压技术》2017年第4期63-67,共5页Forging & Stamping Technology

基　　金：广西科学研究与技术开发计划(桂科攻12118017-10A)

摘　　要：条带结构排样方式在机械制造业下料领域有广泛的应用。针对矩形件二维下料问题,提出一种基于均匀条带排样方式的启发式下料算法。下料方案包含多个排样方式,每个排样方式满足部分矩形件的需求量。首先构造均匀条带四块排样方式的约束排样算法;然后采用列生成法反复调用上述约束排样算法生成各个排样方式,直到所有矩形件需求量得到满足为止。采用文献中的基准例题,将本文下料算法和文献中下料算法进行比较,数值实验结果表明本文下料算法能有效地提高板材利用率,且计算时间能满足实际应用要求。Strip structure pattern was widely used in the field of machinery manufacturing industry. For the problem of two dimensional cutting stock for rectangles,a heuristic algorithm was proposed based on uniform strip pattern. However,the cutting plan included a number of patterns,each of which met the demands of some rectangles. Firstly,the constrained packing algorithm for generated uniform strip four-block pattern was constructed,and then every pattern was generated by applying column generation method to call the constrained packing algorithm repeatedly until all demands of rectangles were met. At last,the literature benchmark instance was applied,and this algorithm was compared with the cutting stock algorithm in literature. The numerical results show that this algorithm can effectively improve the utilization ratio of plates,and the calculation time can meet the requirements of practical application.

关 键 词：二维下料问题 约束排样算法 列生成 均匀条带 四块排样方式 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]