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

图学学报

• 可视化/可视分析 • 上一篇    下一篇

基于两段排样方式的矩形件优化下料算法

  

  1. 河南牧业经济学院软件学院，河南 郑州 450011
  • 出版日期:2018-02-28 发布日期:2018-02-06
  • 基金资助:
    河南省科技厅科技攻关项目(152102210320)；河南省高等学校重点科研项目(15B52000)

An Optimization Algorithm for Rectangular Items Cutting Stock Problem Based on Two-Segment Patterns

  1. Software College, Henan University of Animal Husbandry & Economy, Zhengzhou Henan 450011, China
  • Online:2018-02-28 Published:2018-02-06

PDF (PC)

220

摘要： 针对矩形件下料问题，提出一种基于两段排样方式的优化下料算法。首先构造一
种约束排样算法，生成矩形件在板材上的两段排样方式。然后采用列生成算法依据矩形件剩余
需求量迭代调用上述约束排样算法生成一个虚拟下料方案，按照不产生多余矩形件原则选取虚
拟下料方案中的部分排样方式加入到实际下料方案中，更新矩形件剩余需求量；重复上述步骤
直到矩形件剩余需求量为零。采用文献中基准例题将该算法与2 种文献算法进行比较，数值实
验结果表明该算法下料利用率比2 种文献算法分别高1.61%和0.78%。

关键词: 下料问题, 两段排样方式, 列生成算法, 约束排样, 矩形件

Abstract: For on the rectangular items cutting stock problem, an optimization algorithm based on
two-segment patterns is proposed. Firstly, a constrained packing algorithm is constructed to generate
the two-segment patterns of rectangular items on the plate. Then, column generation algorithm is used
to generate a virtual cutting plan according to the current remaining demand of rectangular items,
several patterns are added into actual cutting plan according to the rule that no redundant rectangular
item is generated, and the current remaining demand of rectangular items is updated. The above steps
are repeated until the remaining demand of rectangular items is zero. Compared the proposed
algorithm with two algorithms in the literature through benchmark instances, results of numerical
experiments show that material utilization of the proposed algorithm is higher than two literature
algorithms about 1.61% and 0.78%, respectively.

Key words: cutting stock problem, two-segment patterns, column generation algorithm, constrained
packing, rectangular items