求解矩形切割问题的改进启发式动态规划算法*

EasyChair Preprint no. 953

Abstract

讨论了含砂眼的二维切割问题，从包含多个砂眼的大矩形板材切割出若干给定尺寸和方向的小矩形块，所切割出的每种小矩形块数量不限，每个切割都限制为一刀切且切割线不能切到砂眼。另外，所切割出的小矩形块不能含有砂眼，目标是最大化切割小矩形块的总价值。为了解决上述问题，提出一种改进启发式-动态规划算法(Improved Heuristic-Dynamic Programming, IHDP)，并证明了关于其复杂度的重要定理。该算法降低了离散集规模，用小矩形块的宽和高建立一维背包问题，利用所得解与砂眼的左右边沿和上下边沿构造两个离散集，以离散集的每一个元素做试切线进行子问题划分，放弃穿过砂眼的切割线。该算法计算了国际公认的14个典型算例，实验结果表明，它得到了这些实例的最优解，其计算效率比最新文献算法高了近十倍。

Keyphrases: improved heuristic-dynamic programming, Two-Dimensional Cutting Problem, two-dimensional cutting problem with defects

@Booklet{EasyChair:953,
  author = {Yin Aihua and Chen Chong and Hu Dongping and Huang Jianghai and Yang Fan},
  title = {求解矩形切割问题的改进启发式动态规划算法*},
  howpublished = {EasyChair Preprint no. 953},

  year = {EasyChair, 2019}}