Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2008-008 (August 04, 2008)

One-dimensional cutting stock problem for a paper tube industry
by Kazuki Matsumoto, Shunji Umetani, Hiroshi Nagamochi

pdf File


The one-dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems, which arises in many industrial applications. Although the primary objective of 1D-CSP is to minimize the totallength of used stock rolls, efficiency of cutting process has become more important to be considered in recent years. The crucial bottleneck of cutting process often occurs at handling operations in semiautomated manufactures such as a paper tube industry. To reduce interruptions and errors at handling operations in a paper tube industry, we consider a variant of 1D-CSP that minimizesthe total length of used stock rolls while constraining (C1) the number of setups of each stock roll type, (C2) the combination of piece lengths occurred in open stacks simultaneously, and (C3) the number of open stacks. For this problem, we propose a generalization of the cutting pattern called the ``cutting group," each of which is a sequence of cutting patterns that satisfies the given upper bounds of setups of each stock roll type and open stacks. To generate good cutting groups, we decompose the 1D-CSP into a number of auxiliary bin packing problems. We develop a tabu search algorithm based on a shift neighborhood that solves the auxiliary bin packing problems by the first-fit decreasing heuristic algorithm. Experimental results show that our algorithm improves the quality of solutions compared to the existing algorithm used in a paper tube factory.