Research On The Algorithms For Rectangular Two-Dimensional Cutting Stock Problem

The two-dimensional cutting stock problem of rectangular items appears in industries like glass, sheet metal processing, cloths cutting. For the two-dimensional cutting stock problems in different occasions, the cutting algorithms with three-block patterns and simple block patterns are considered. Three-block patterns with simple structure can improve the cutting efficiency effectively. While simple block Patterns can improve material utilization, therefore, it is suitable for cutting expensive plates. The main research works are as follows:(1) Applying three-block patterns with sequential value correction frame. The sequential heuristic procedure generates cutting patterns in a cutting plan sequentially. A pattern is generated to fulfill a portion of the remaining item demand. When all the required items are fulfilled, all the patterns in a cutting plan are generated. The value of items is adjusted dynamically to generate multiple plans, and then choose the best one. A constrained three-block pattern generating algorithm based on incomplete enumeration method is proposed. By comparing with the published algorithm based on linear programming, experimental results show that this algorithm can effectively reduce plate consumption when item demands are small.(2) Applying three-block patterns with linear programing frame. Column generation is used to generate a set of patterns. The frequency of each pattern in the set is obtained by solving the integer programming model of the cutting problem, thus a cutting plan is obtained. In the pattern generating algorithm, an integer programing model is proposed to generate the optimal three-block patterns. Experimental results suggest that this algorithm can significantly reduce the plate consumption in the cases which item demands are small. The effectiveness of applying the optimal three-block pattern generating algorithm and that of the rounding strategy are verified respectively.(3) Applying simple block patterns with linear programing frame. The linear programing frame used here is the same as that in (2). The simple block pattern generating algorithm is extended by allowing 90-degrees rotation of the items. It generates the patterns through recursion. The comparison with the existing commercial software and an algorithm published in a foreign journal suggests that the proposed algorithm can lead to lower plate consumption and better material utilization.