目的 针对矩形件无约束二维剪切排样问题。构造一种可简化切割工艺的简单块占角排样方式及其生成算法。方法 该排样方式在板材左下角按照简单块方式排样若干行若干列同种矩形件,将板材剩余部分划分为两个子板；将子板按照上述方法继续递归排样和划分,直至子板排满矩形件为止。采用动态规划算法确定板材左下角排样的最优矩形件、矩形件的最优行列数和板材剩余部分的最优子板划分。运用规范尺寸排除不必要的计算。结果 采用基准例题将本文算法与文献算法进行比较,实验结果表明本文算法计算时间合理,生成的排样方式切割工艺比较简单,排样价值较高。结论 本文算法计算时间远小于精确排样算法,优化效果接近精确排样算法；本文算法计算时间与多种启发式排样算法接近,但优化效果好于多种启发式排样算法。
A dynamic programming algorithm for simple block corner-occupying pattern of rectangular blanks
Pan Weiping,Zhang Ruiyou(College of Information Science and Engineering,Northeastern University)
Objective In industrial production, we often encounter two-dimensional cutting problems, such as the cutting process of metal sheet, glass, plywood and so on. Good cutting pattern can effectively simplify the cutting process, improve the utilization rate of sheet metal, reduce resource consumption, and reduce the production costs of enterprises. Two-dimensional cutting problem can be divided into rectangular cutting problem and other shape cutting problem according to the geometric shape of the workpiece. According to whether the workpiece is allowed to rotate, it can be divided into rotatable cutting problem and non-rotatable cutting problem. According to the number of times each workpiece is allowed to appear in the sheet, it can be divided into constrained cutting problem and unconstrained cutting problem. According to whether the cutting process of blanking meets the requirement of guillotine cuts, it can be divided into guillotine cutting problem and non-guillotine cutting problem. This paper focus unconstrained two-dimensional guillotine cutting problem of rectangular pieces (UTGCR ), it refers to cutting a sheet into several rectangular pieces of different sizes and values, and the number of occurrences of each rectangular piece in the sheet is unconstrained. The optimization goal of this problem is to maximize the total value of rectangular pieces cut out of the sheet. The cutting stock algorithm iteratively calls the cutting algorithm to generate the cutting pattern of rectangular pieces on a sheet. After a new cutting pattern is generated, the number of times of using the new cutting pattern is determined by the residual demand of rectangular pieces. The value of the rectangle is corrected by the number of the rectangular pieces include in the new cutting pattern to make the subsequent cutting pattern more reasonable.A good cutting algorithm can improve the material utilization of sheet, reduce resource consumption, reduce production costs and improve the competitiveness of enterprises. From the point of view of computational complexity, the UTGCR problem is a complex combinatorial optimization problem with NP complexity. Because the solution space of the feasible cutting pattern is very large, the exact algorithm takes too long to solve large-scale problems, and can not meet the practical application requirements. In practice, heuristic algorithms are generally used to solve UTGCR problems, which can be divided into two categories according to the construction idea of the algorithms.The first is intelligent optimization algorithm, which is widely used in rectangular Non-guillotine cutting problem and relatively less used in UTGCR problem. Because of the unknown convergence of the algorithm, it is difficult to guarantee the quality of the solution. In addition, the structure of the cutting pattern is complex, which is not conducive to the sheet cutting process.The second is to reduce the solution space and the computational complexity of the algorithm by restricting the cutting pattern to satisfy a certain geometric characteristic. Although this kind of algorithm is not guaranteed to get the optimal solution, it is widely used because of its less calculation time and simple layout structure, which is conducive to the sheet cutting process. A simple block corner-occupying pattern which can simplify the cutting process of sheet is presented, and a dynamic programming algorithm for generate this pattern is constructed. Method The dynamic programming principle is used to construct simple block corner-occupying pattern with different sizes of sub sheets one by one from small to big. The pattern information of sub sheets with smaller sizes can be directly used when constructing the sub sheet with current sizes. A simple block corner-occupying pattern is obtained when the simple block corner-occupying pattern of the sub sheet is obtained. With this pattern, several rows and columns of identical pieces are packing at the lower left corner of the sheet according to a simple block mode. The remaining part of the sheet is divided into two sub sheets. Recursive packing and partitioning of the sub sheet is continued according to the above method, until the sub sheets are full filled with rectangular pieces. A dynamic programming algorithm is used to determine the optimal piece type, the optimal number of rows and columns of pieces and the optimal partitioning of the remaining part of the all possible size of sheets. The normal size is used to exclude unnecessary calculations. Result There are five groups of instances in literature were used. The first group, the second group and the fourth group are international benchmark instances, which can be found at http://www.laria.u-picardie.fr/hifi/OR-Benchmark. The third group is random instances and the fifth group is actual production instance. Comparing the algorithm in this paper with the algorithms in common literature ,the experimental results show that the algorithm in this paper has reasonable calculation time and high pattern value. In the first set of 41 benchmark instances, the algorithm in this paper has found the exact solution to all instances, while homogeneous block T-shape algorithm, homogeneous block two-segment algorithm and compound strip two-segment algorithm have not found exact solution of 7, 5 and 4 instances respectively. In the second set of 20 benchmark instances, only one of them has not been solved accurately by this algorithm. There are 18, 15 ,15 and 20 instances have not been solved accurately by the common three-stage algorithm, homogeneous block T-type algorithm, homogeneous block two-stage algorithm and homogeneous strip three-block algorithm, respectively. In the third set of 50 random instances, the sheet utilization rates of this algorithm, ordinary two-stage algorithm and homogeneous block two-stage algorithm are 99.9137%, 99.8623% and 99.7961%, respectively. In the fourth set of 31 benchmark instances, the exact solutions of all the instances are solved by the algorithm in this paper, and the exact solutions of two instances are not solved by the common corner-occupying algorithm. Conclusion The computation time of the algorithm in this paper is much less than that of the exact cutting algorithms, and the optimization effect is close to the exact cutting algorithm. The computation time of the algorithm in this paper is close to that of many heuristic cutting algorithms, and the optimization effect is better than that of many heuristic cutting algorithms. As a cutting pattern generation algorithm, this algorithm can combines with linear programming, integer programming and sequential heuristic algorithm to solve the two-dimensional guillotine cutting stock problem of rectangular pieces.