求解矩形切割问题快速启发式-动态规划算法*

EasyChair Preprint 946

Abstract

讨论了含砂眼的二维矩形切割问题。目标是在满足若干约束条件的前提下从含有多个砂眼的大矩形原板上切割出已给定高和宽的小矩形块，使得切割下来的小矩形块的面积和最大。约束条件为每一次切割操作必须是一刀切并且不能穿过砂眼，每一类小矩形块的数量不限且保持给定的方向。将该问题看做是用矩形块覆盖原板，提出一种基于动态规划的快速启发式算法(Quick Heuristic-Dynamic Programming, QHDP)。首先，根据小矩形块的高和宽建立一维背包问题，分别生成高效的离散集，然后，以离散集中的每一个值作为可能的切割线坐标进行子问题划分。如果某个切割线穿过砂眼，则剪切掉该递归分支。该算法计算了国际公认的14个典型算例，实验结果表明，它都得到了全部算例的最优解，且计算时间少于当前文献中最好算法的十分之一。算法复杂度得到分析和证明。

Keyphrases: NP-hard, Optimization, defects, dynamic programming, two-dimensional cutting

@booklet{EasyChair:946,
  author    = {Yin Aihua and Huang Jianghai and Hu Dongping and Chen Chong},
  title     = {A Quick Heuristic-Dynamic Programming for The Two-Dimensional Cutting Problem*},
  howpublished = {EasyChair Preprint 946},
  year      = {EasyChair, 2019}}