关键词: 二维板材下料, 矩形件, 八块排样方式, 列生成算法, 板材利用率

Abstract: The two-dimensional cutting problem of rectangular plates refers to cutting several types of rectangular parts from a set of plates, and minimizing the number of plates used while ensuring that the demand for each type of rectangular part is met. This problem has a wide range of applications in the industrial field. A good cutting plan can improve the utilization rate of plate metal, reduce production costs, and enhance the competitiveness of enterprises. The cutting plan generally consists of multiple layouts, each of which provides the layout of rectangular parts on a single plate of material. Therefore, the two-dimensional cutting problem of rectangular plates includes two combinatorial optimization problems: the one is determining the layout by combining rectangular parts on a single plate; the other is combining the feasible layouts in the set to determine the cutting plan.
The commonly used methods for solving the cutting problem of two-dimensional rectangular plates can be divided into three types. The first type is the integer programming method. The second type is the sequential heuristic method. This method generates a layout using the remaining rectangular parts to meet the partial demand for the rectangular parts, and repeats the process until all the demands for the rectangular parts are met. The third type is the linear programming method. Due to a large number of decision variables in the model, it is difficult for the integer programming method to calculate solutions for medium to large-scale cutting problems in a reasonable time. Sequential heuristic algorithms are generally used for cutting problems with low demand for rectangular parts. For cutting problems with high demand for rectangular parts, the calculation time is too long and it is difficult to meet practical application requirements. The utilization rate of the cutting plan generated by the linear programming method and the complexity of the cutting process depend on the layout used.
The two-dimensional plate cutting stock problem of rectangular parts is discussed in this study. A two-dimensional plate cutting stock optimization model and solution algorithm of multiple-block layout are proposed. In order to balance the computational complexity and plate utilization of multiple-block layout, the number of blocks of multiple-block layout is set as eight. The eight-block layout first divides the plate into eight rectangular blocks through three times as many as one-in-two cutting operations, and then cut each block into the same rectangular parts with the same direction. Firstly, an eight-block layout algorithm is constructed to determine the optimal layout of rectangular parts and the optimal eight-block partition of plates in all possible sizes according to the principle of maximum layout value. Then, the column generation algorithm is used to iteratively call the above eight-block layout algorithms to generate a series of cutting plans, and the cutting plan with the least plate consumption is selected as the final solution.
We compare the layout algorithm and cutting algorithm in this study with the literature layout algorithm and cutting stock algorithm using benchmark examples and actual production examples. By using 10 literature layout instances, the eight-block layout algorithm is compared with three literature layout algorithms. The experimental results show that the layout value of only one instance of the eight-block layout algorithm is lower than two literature layout algorithms, and the layout value of the other nine instances is higher than three literature layout algorithms. Using the actual cutting instance in the literature, the eight-block cutting stock algorithm is compared with the cutting stock algorithm in the literature. The experimental results show that the cutting plan of the eight-block cutting stock algorithm consumes 2269 plates and the utilization rate of plates is 99.88%. The cutting plan generated by the literature cutting stock algorithm consumes 2285 plates, and the utilization rate of plates is 99.18%. It can be seen that the plate utilization rate of the cutting plan generated by the eight-block cutting stock algorithm is 0.7% higher than that of the cutting stock algorithm in the literature, and the number of plates consumed is very close to the theoretical lower bound. The calculation time of the eight-block layout algorithm and eight-block cutting stock algorithm in this study can meet the needs of practical application.
The method proposed in this article has the following characteristics. Each plate of the cutting scheme only contains a maximum of 8 types of rectangular parts, which is conducive to the sorting of rectangular parts in the plate cutting process. After the board is cut into blocks, each block only needs to be cut into a rectangular part with the same direction, and the cutting process is relatively simple. It is suitable for solving the cutting and cutting problem of large-scale rectangular two-dimensional plate metal. The utilization rate of the cutting plan is high, and the calculation time can meet the practical application needs. Future research work can consider using a multi-block layout to solve the cutting and punching problem of two-dimensional circular plate metal.

Key words: two-dimensional plate cutting stock, rectangular parts, eight-block layout, column generation algorithm, utilization rate of plate