Information Technology Reference
In-Depth Information
A Heuristic Approach Based on Shape Similarity
for 2D Irregular Cutting Stock Problem
Yanxin Xu
∗
, Genke Yang, and Changchun Pan
Department of Automation, Shanghai JiaoTong University, Dongchuan Road. 800,
200240 Shanghai, China
iamxuyanxin@sjtu.edu.cn
Abstract.
Cutting stock problem is an important problem that arises in a variety
of industrial applications. This research constructs an irregular-shaped nesting
approach for two-dimensional cutting stock problem. The techniques of shape
similarity are utilized, drawn from computer vision and artificial intelligence.
These techniques enable the approach to find potential matches of the unplaced
pieces within the void regions of the sheet, and thus the packing density and the
performance of solutions are highly improved. The proposed approach is able to
deal with complex shapes in industrial application and achieve high-quality
solution with shorter computational time. We evaluate the proposed method
using 15 established benchmark problems available from the EURO Special
Interest Group on Cutting and Packing. The results demonstrate the
effectiveness and high efficiency of the proposed approach.
Keywords:
Cutting Stock Problem, Grid Approximation, Shape Similarity,
Fourier Descriptor.
1
Introduction
Cutting and Packing Problem are a large family of problems arising in a wide variety
of industrial applications, including the cutting of standardized stock units in the
wood, steel and glass industries, packing on shelves or truck beds in transportation
and warehousing, and the paging of articles in newspapers. There are many classic
cutting and packing problems, including knapsack problem, bin packing and cutting
stock problem etc. In this paper, we focus on the cutting stock problem (CSP). In
CSP, a number of two-dimensional pieces must be cut from a couple of same stocks.
The objective is to minimize the number of stocks. Using the typology of W
scher,
this is a Two-Dimensional Single Stock-Size Cutting Stock Problems (2DCSP) [1].
The 2DCSP has been proved to be NP-hard [2].
The 2DCSP can be defined as follows: Given a set L = (a1, a2, ..., an) of regular
and irregular pieces to be cut (size of each piece s(a
i
)
ä
∈
(0,A
o
]) from a set of
rectangular stock-cutting sheets (objects) of size A
o
(with fixed Length L and Width
W), the CSP is to find cutting patterns to minimize the number of objects used.
Typical assumptions are summarized as:
Search WWH ::
Custom Search