冲裁件条料最优四块剪切下料方案的生成算法  

Algorithm for generating optimal four-block cutting stock patterns of punched strips

作　　者：曾兆敏[1] 管卫利[2] 潘卫平[3] ZENG Zhaomin;GUAN Weili;PAN Weiping(Sichuan Institute of Information Technology, Guangyuan, Sichuan 628017, China;College of Information Engineering, Nanning University, Nanning 530200, China;College of Computer and Electronic Information, Guangxi University, Nanning 530004, China)

机构地区：[1]四川信息职业技术学院,四川广元628017 [2]南宁学院信息工程学院,南宁530200 [3]广西大学计算机与电子信息学院,南宁530004

出　　处：《计算机工程与应用》2016年第20期75-79,共5页Computer Engineering and Applications

基　　金：四川省教育厅科研项目(No.GZY15C45);广西科学研究与技术开发计划(No.12118017-10A)

摘　　要：讨论冲裁件条料剪切下料方案的设计问题。下料方案由一组排样方式组成。首先构造一种生成条料最优四块排样方式的背包算法,然后采用基于列生成的线性规划算法迭代调用上述背包算法,每次都根据生产成本最小的原则改善目标函数并确定各种冲裁件的当前价值,按照当前价值生成一个新的排样方式,最后选择最优的一组排样方式组成下料方案。采用例题将该排样方式生成算法和文献中多段排样方式生成算法进行比较,实验计算结果表明,该算法得到的排样方式排样价值较高。最后通过文献中实例的下料方案求解,可以看出该算法解决实际下料问题是有效的。This paper discusses the problem of generating optimal cutting scheme for punch items. The cutting scheme alsoconsists of several cutting patterns. First a knapsack algorithm generating four-block cutting patterns of punched strips isconstructed, then the linear programming algorithm which based on column-generation is used to generate the cuttingplans, it iteratively calls the above knapsack algorithm, improves the objective function based on the principle of minimumproduction cost and changes the current value of punched items, generates a new pattern according to the current value, inthe end a set of optimal cutting patterns are chosen to form the cutting scheme. It makes this paper’s four-block generationalgorithm compared with the literature’s multiple-segment generation algorithm through example testing, the experimentalresults show that, four-block generation algorithm can obtain a higher value pattern. Finally through the solving cuttingscheme of an example, it can be seen that the proposed algorithm is effective in solving the practical problem.

关 键 词：冲裁件 剪切下料 背包算法 列生成 线性规划算法 

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