Abstract: The Heuristic Recursive(HR)algorithm for two-dimensional strip packing problem was adjusted, and a judgment theorem which was used to determine whether two neighbor wasted spaces in same layer could be combine or not was presented. A multi-recursive algorithm for two-dimensional strip packing problem(2D-SPP)was constructed, and a Two-Stage Approach(TSA)for two-dimensional oriented guillotine bin packing problem was proposed by combining the algorithm with Best-Fit Decreasing(BFD)algorithm of one-dimensional bin packing problem. On the basis of 500 group benchmark problems, the approach was compared with multiple algorithms, the experiments showed that the proposed approach could obtain better results for almost all test instances.

Key words: recursive algorithms, heuristic algorithms, guillotine, 2D oriented bin packing problem

摘要： 对用于二维带排样问题的Heuristic Recursive算法进行了调整,给出同一层中两个相邻浪费区域在满足一刀切约束下是否可合并的判定定理。构造了二维带排样问题的多递归层算法,并将它与一维装箱问题的最优匹配递减算法相结合,提出适应二维一刀切非旋转装箱问题的两阶段算法。在500组标准测试案例的基础上,与多种算法进行了比较。实验结果表明,所提算法在绝大多数测试案例上能够获得更好的排样布局。

关键词: 递归算法, 启发式算法, 一刀切, 二维非旋转装箱问题