欢迎访问《图学学报》 分享到:

图学学报

• 几何设计与计算 • 上一篇    下一篇

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

  

  • 出版日期:2016-06-30 发布日期:2016-06-28
  • 基金资助:
    河南省科技厅科技攻关项目(152102210320);河南省高等学校重点科研项目(15B52000)

Sequential Value Correction Heuristic Algorithm for the Circle Cutting Stock Problem

  • Online:2016-06-30 Published:2016-06-28

摘要: 讨论圆片剪冲下料方案的设计问题。下料方案由一组排样方式组成。首先构造一种生成圆片条带最优四块排样方式的背包算法,然后采用基于价值修正的顺序启发式算法迭代调用上述背包算法,每次都根据生产成本最小的原则改善目标函数并修正各种圆片的当前价值,按照当前价值生成一个新的排样方式,最后选择最优的一组排样方式组成下料方案。采用文献中的基准测题将文中下料算法与文献中T 型下料算法和启发式下料算法分别进行比较。实验计算结果表明,该算法的材料利用率比T 型下料算法和启发式下料算法分别高0.83%和3.63%,且计算时间在实际应用中合理。

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

Abstract: 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.

Key words: wafer, cutting stock, four block patterns, knapsack problem, heuristic algorithm