一种基于递归技术的一维下料算法  

A Recursive Algorithm for One-dimensional Cutting Stock Problem

作　　者：郑文[1] 崔耀东[1] 周密[1] 

机构地区：[1]广西大学计算机与电子信息学院,广西南宁530004

出　　处：《广西科学院学报》2010年第4期415-417,共3页Journal of Guangxi Academy of Sciences

基　　金：国家自然科学基金项目(61063031);广西大学科研基金项目(XB2100145)资助

摘　　要：用递归技术进行排样,并将排样方式与线性规划相结合,提出一种基于递归技术的一维下料算法.该算法通过约束一个排样方式中所含毛坯种数,达到减少开堆数的目的,利用上界技术来减少计算时间.该算法可以大幅缩短计算时间,在材料利用率基本不下降的情况下,可以明显减少最大开堆数.A recursive algorithm to solve one-dimensional cutting stock problem is proposed.A recursive procedure is used for pattern generation and articulated with linear programming to generate the cutting plan.The algorithm reduces the open stacks by means of constraining the number of item types in each pattern,and using branch and bound method to decrease computing time.The computational results indicate that the presented approach can decrease the computing time significanthy and reduce effectively the open stacks with high material utilization rate.

关 键 词：递归算法 一维下料 开堆 线性规划 

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