A separation technique for solving the two-dimensional skiving and cutting stock problem

Abstract

A two-dimensional skiving and cutting stock problem (2D-SCSP) is a version of the cutting stock problem (CSP) that allows for skiving. In this problem, output sheets are assumed to be longer but thinner than input coils. Consequently, subsets of two or more coils must be considered for joining and cutting to meet the demand of output sheets, leading to the joining cost. Solving this problem requires all subsets of coil groups and all patterns of each subset. Afterward, an integer linear programming problem is formulated to find optimal subsets of coil groups and patterns in order to minimize material and setup costs. However, it is nearly impossible to find all subsets of coil groups and their feasible patterns. Therefore, in this paper, we introduce a heuristic method that reduces the dimensions of a 2D-SCSP by separating it into two steps: generating the feasible subset of coil groups and finding optimal patterns by solving a one-dimensional CSP. The algorithm repeats until the demand is met. The results are then compared with the results obtained by using the column-and-row generation (C&R) approach. Based on the computational results, the proposed method can reduce the computational time by at least 70% compared with the C&R method, and the differences in the objective values of the two methods were found to be less than 0.0001%.