基于价值修正的圆片下料顺序启发式算法  

Sequential Value Correction Heuristic Algorithm for the Circle Cutting Stock Problem

作　　者：胡钢[1] 杨瑞[2] 潘立武[3] 

机构地区：[1]四川信息职业技术学院信息工程系,四川广元628017 [2]郑州科技学院电气工程学院,河南郑州450064 [3]河南牧业经济学院自动化与控制系,河南郑州450011

出　　处：《图学学报》2016年第3期337-341,共5页Journal of Graphics

基　　金：河南省科技厅科技攻关项目(152102210320);河南省高等学校重点科研项目(15B52000)

摘　　要：讨论圆片剪冲下料方案的设计问题。下料方案由一组排样方式组成。首先构造一种生成圆片条带最优四块排样方式的背包算法,然后采用基于价值修正的顺序启发式算法迭代调用上述背包算法,每次都根据生产成本最小的原则改善目标函数并修正各种圆片的当前价值,按照当前价值生成一个新的排样方式,最后选择最优的一组排样方式组成下料方案。采用文献中的基准测题将文中下料算法与文献中T型下料算法和启发式下料算法分别进行比较。实验计算结果表明,该算法的材料利用率比T型下料算法和启发式下料算法分别高0.83%和3.63%,且计算时间在实际应用中合理。This paper discusses the problem of generating optimal cutting plan for circles. The cutting plan consists of several cutting patterns. First a knapsack algorithm that generating four-block cutting patterns of circle strips was constructed; then the sequential value correction heuristic algorithm was used to generate the cutting plan, it iteratively calls the above knapsack algorithm procedure improves the objective function based on the principle of minimum production cost and correct the current value of circles, generates a new pattern according to the current value; in the end a set of optimal cutting patterns was choose to form the cutting plan. The cutting stock algorithm was tested with the benchmark problems of literatures, and compared with the T-shape algorithm and heuristic algorithm. The results of numerical experiments show that, the material utilization rate of the algorithm is higher 0.83% and 3.63% than the above two algorithms.

关 键 词：圆片 剪冲下料 四块排样方式 背包算法 启发式算法 

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