一维下料问题中提高计算效率方法的研究  

Several heuristic strategies to improve computational efficiency for One-Dimensional Cutting Stock Problem

作　　者：刘睿[1] 于波[1] 崔耀东[2] 

机构地区：[1]聊城大学计算机学院,山东聊城252000 [2]广西大学计算机与电子信息学院,南宁530012

出　　处：《计算机工程与应用》2013年第9期247-250,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61063031)

摘　　要：讨论一维下料问题,对原有的基于顺序价值修正的启发式算法进行改进。每次使用动态规划算法求解当前最优排样方式的背包问题,保存多个价值最优的排样方式提供给SHP算法选择,修改对应的回退算法,提高算法的计算效率。综合考虑材料利用率和可重复次数,优先选择有利于后面排样方式生成的排样方式。在记录下的大量较优结果中,最终选取满足需要的排样方案进行使用。在计算过程中,结合多线程技术,进一步提高计算效率。实验结果表明,改进后的算法能够有效地提高材料利用率,简化切割方式,在计算时间上优势明显。This paper discusses the One-Dimensional Cutting Stock Problem, improves the original heuristic algorithm based on Sequential Value Correction. Every time it uses dynamic programming algorithm to solve the bounded knapsack problem of optimal cutting pattern and preserves many cutting patterns of best value to provide for SHP algorithm selection, modifies the corresponding backtrack algorithm to improve the computing efficiency. It comprehensively considers the utilization rate and repeatable times of materials, gives priority to choose the pattern helpful to generate the one behind. From the lots of better results recorded, it finally chooses the scheme meeting needs to use. In the calculating process, it combines with the multi-threading technology to further improve computational efficiency. The experiment results indicate that the improved algorithm can improve the material utilization ratio effectively, simplify the cutting process, and have an obvious advantage in computation time.

关 键 词：一维下料 顺序启发式算法 动态规划算法 多线程技术 提高计算效率 

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