Local search algorithms for the two dimensional cutting stock problem

We consider the two dimensional cutting stock problem, which arises in many industries. In recent industrial applications, it is argued that the setup costs for changing patterns become more dominant and it is impractical to use many different patterns. Therefore, we consider the pattern restricted two dimensional cutting stock problem, in which the total number of applications of cutting patterns is minimized while the number of different cutting patterns is given as a parameter n. For this problem, we develop a local search algorithm. As the size of the neighborhood plays a crucial role in determining the efficiency of local search, we propose to use linear programming techniques for the purpose of restricting the number of solutions in the neighborhood. To determine a cutting pattern in each solution, we have to place all products (rectangles) in the two dimensional area without mutual overlap. For this purpose, we develop a heuristic algorithm using an existing rectangle packing algorithm with a coding scheme called sequence pair. Finally, we generate random test instances of this problem, and conduct computational experiments to see the effectiveness of the proposed algorithm.