计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (19): 266-270.DOI: 10.3778/j.issn.1002-8331.1706-0201

• 工程与应用 • 上一篇    

多尺寸圆木二维下料问题研究

张  雨,崔耀东,梁泽华   

  1. 广西大学 计算机与电子信息学院,南宁 530004
  • 出版日期:2018-10-01 发布日期:2018-10-19

Two-dimensional cutting stock problem of multiple logs

ZHANG Yu, CUI Yaodong, LIANG Zehua   

  1. College of Computer and Electronic Information, Guangxi University, Nanning 530004, China
  • Online:2018-10-01 Published:2018-10-19

摘要: 圆木二维下料问题是木材企业中常见问题,针对一些头部与尾部直径相差不大的木材,可以将这些木材看作是圆柱体,下料时将其切成和圆木长度相等的多个长方体毛坯,该问题可转化为二维下料问题。采用顺序价值校正框架和动态规划算法求解该下料问题。顺序生成排样图,每生成一个排样图便调整毛坯的价值,重复该过程直到满足毛坯需求为止。通过迭代生成多个下料方案以便优选。圆木下料的研究对减少木材企业的成本很有意义。

关键词: 圆木二维下料, 顺序价值校正, 动态规划

Abstract: The cutting stock problem of log can be seen in timber enterprise. If the diameter of head and tail is similar, the log is regarded as a cylinder. Assuming that the length of the log is equal to the length of the blank, then the three-dimensional problem can be converted to two-dimensional cutting stock problem. Sequential value correction and dynamic programming algorithm are proposed to solve the cutting stock problem of log. The pattern is generated in order. The value of the blank will be adjusted after each pattern is generated. Multiple cutting plans are generated through iteration and the best one will be selected. The proposed studies can help the enterprise to reduce the cost.

Key words: two-dimensional cutting of log, sequential value correction, dynamic programming