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

图学学报

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

二维板材切割下料问题的一种确定性算法

  

  1. 1. 四川信息职业技术学院，四川 广元 628017；2. 郑州科技学院电气工程学院，河南 郑州 450064；
    3. 南宁学院信息工程学院，广西 南宁 530200
  • 出版日期:2016-08-31 发布日期:2016-08-09

A Deterministic Algorithm for Solving the Problem of#br# Two-Dimensional Sheet Cutting Stock

  1. 1. Sichuan Institute of Information Technology, Guangyuan Sichuan 628017, China;
    2. School of Electrical Engineering, Zhengzhou University of Science＆Technology, Zhengzhou Henan 450064, China;
    3. Information Engineering College, Nanning University, Nanning Guangxi 530200, China
  • Online:2016-08-31 Published:2016-08-09
  • Supported by:
    四川省教育厅科研项目(GZY15C45)；广西科学研究与技术开发计划项目(12118017-10A)

PDF (PC)

567

被引次数

7

摘要： 研究二维板材切割下料问题，即使用最少板材切割出一定数量的若干种矩形件。
提出一种结合背包算法和线性规划算法的确定性求解算法。首先构造生成均匀条带四块排样方
式的背包算法；然后采用线性规划算法迭代调用上述背包算法，每次均根据生产成本最小原则
改善目标函数并修正各种矩形件的当前价值，按照当前价值生成新的排样方式；最后选择最优
的一组排样方式组成排样方案。采用基准测题，将该算法与著名的T 型下料算法进行比较，实
验结果表明，该算法比T 型下料算法更能节省板材，计算时间能够满足实际应用需要。

关键词: 二维切割, 矩形件下料, 背包算法, 线性规划算法

Abstract: This paper discusses the two dimensional sheet cutting stock problem, that is, use the least
number of sheets to cut out a certain number of rectangular pieces. A deterministic algorithm is
proposed which based on the combination of knapsack algorithm and linear programming algorithm.
First, a knapsack algorithm is constructed to generates the four blocks uniform strip pattern, then the
linear programming algorithm is used to generate the cutting plans which iteratively calls the above
knapsack algorithm to improve the objective function based on the principle of minimum production
cost and changes the current value of punched items to generate a new pattern according to the
current value. Lastly, a set of optimal cutting patterns is selected to form the cutting scheme. The
algorithm was compared with the famous T-shape algorithm using some benchmark problem tests.
The results show that the algorithm can save more sheets than the T-shape one, and the calculation
time is reasonable in practical application.

Key words: two-dimensional cutting, rectangle cutting stock, knapsack algorithm, linear
programming algorithm