On the one‐dimensional stock cutting problem in the paper tube industry

On the one‐dimensional stock cutting problem in the paper tube industry

0.00 Avg rating0 Votes
Article ID: iaor20115768
Volume: 14
Issue: 3
Start Page Number: 281
End Page Number: 290
Publication Date: Jun 2011
Journal: Journal of Scheduling
Authors: , ,
Keywords: heuristics: tabu search
Abstract:

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 total length of used stock rolls, the efficiency of cutting processes has become more important in recent years. The crucial bottleneck of the cutting process often occurs at handling operations in semiautomated manufacturers such as those in the paper tube industry. To reduce interruptions and errors at handling operations in the paper tube industry, we consider a variant of 1D‐CSP that minimizes the total length of used stock rolls while constraining (C1) the number of setups of each stock roll type, (C2) the combination of piece lengths occurring 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,’ 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.

Reviews

Required fields are marked *. Your email address will not be published.