Information Technology Reference
In-Depth Information
data sets is yet a huge difficulty. We adopt another method to represent shapes called
grid approximation, in which pieces are represented by two-dimensional matrices.
With use of grid approximation, it's not necessary to introduce additional routines to
identify enclosed areas and geometric tool to detect overlap. The grid approximation
is used in several literatures [17, 18].
3
Methodology
In 2DCSP, two kinds of heuristics are generally used, namely the selection heuristic
for selecting pieces and objects, and the placement heuristic for placing pieces and
objects. Many heuristics have been studied in the literatures and have their own
superiority in some instances. In this research, Best Fit and Bottom Left irregular are
respectively chosen to be the selection heuristic and placement heuristic. Firstly, it is
decided by heuristic Best Fit that which stock sheet is chosen for the allocating piece.
Then a hybrid approach combining heuristic Bottom Left irregular and other
placement strategy is proposed to place the piece on this stock.
The proposed approach is composed of three steps. Firstly, the grid approximation
is used to represent irregular-shaped pieces in two-dimensional matrices. The
geometry of the stocks and pieces are converted into discrete form in order to make
the nesting process faster and the actual geometry of the sheets and pieces
independent. Secondly, a hybrid approach combining with heuristic Bottom Left
irregular and a two-stage placement strategy is used to pack the ordered pieces.
Finally, void regions are generated between the packed pieces and stock sheet after
some pieces are placed. Then these void regions are matched with the unpacked
pieces, according to their similarity of shape. Among the pieces that can be allocated
in the void region, the most similar one will be allocated on the void region. A
detailed description of every step is showed in following sections.
In order to evaluate the resulting solutions, we consider the ratio of the total area of
all the allocated shapes to the area of the occupied stocks as a performance measure
called packing density (PD). Its maximum value is 1, when there is no waste of
resource material.
Area of Allocated Pieces
Area of Occupied Stocks  
PD =
.
3.1
Pre-layout Phase
The operation of the method is divided into two phases: the pre-layout phase and the
layout phase. In the pre-layout phase, the pieces are represented as a matrix by taking
the grid approximation method and the initial sequence and orientation of the pieces
based on their geometrical features are determines.
In this research, the grid approximation, a digitized representation technique, is
used to represent multiple-shaped pieces including convex and concave. The matrix
representation approach was proposed by Dagli 1990[19]. Each piece is represented
Search WWH ::




Custom Search