A Heuristic Approach Based on Shape Similarity for 2D Irregular Cutting Stock Problem - Intelligent Computing for Sustainable Energy and Environment - page 279

intelligence is adopted to increase the packing density of the nesting piece at a
particular stage by reusing the complements of the allocated pieces on the sheet.

3.2.1 Hybrid Approach Combining with Heuristic Bottom Left Irregular and
Two-Stage Placement Strategy
The heuristic Bottom Left irregular is used to allocate the current pieces on the stock
sheet without affecting any other allocated pieces. The purpose is to minimize the
total required area and the objective value can be stated as:

=∗+
Where x and y is respectively the coordinate of the piece along X axis and Y axis of
the matrix representation of the stock sheet; W is the width of the stock sheet. By
using this approach, the first packing piece is placed at the lower left-hand corner of
the empty stock sheet. The following pieces are allocated along the Y axis until there
is no enough space. Then a new row of pieces along X axis is formed. The two-stage
placement strategy is referred to W.K. Wong and X.X. Wang 2009. In this case, the
enclosing rectangles of the packing pieces are first examined, and then the packing
pieces are compacted directly. The differences are that the compaction routine is done
when each enclosing rectangle is placed rather than implement it in a single step after
all the enclosing rectangles are allocated. This compaction routine is able to obtain a
tighter packing pattern and provide more space for the unpacked pieces. The hybrid
approach improves the quality of packing pattern without more computational effort.

x y

objective value of sliding part W

3.2.2 Packing Approach Based on Shape Similarity
After pieces are placed, a number of void regions are generated by previous
allocations, namely the complements of the allocated pieces. These void regions may
be reused to increase the packing density at a particular stage. The packing approach
is based on shape similarity draw from computer vision and artificial intelligence. The
characteristic is the utilization of a shape similarity criterion for matching void
regions of the layout and remaining pieces. As the grid of the allocated pieces in sheet
partially or wholly covered is assigned by '1', then the void region between these
pieces is the region assigned by '0' among '1's. The void regions are extracted from
the stock sheet by scanning each row of the matrix representation of the stock plate.
The result of scanning the sheet is a pool of line segments as sections of void regions.
These line segments are later combined and form void regions.
Whenever a new row along X axis of the stock sheet appears as described in 3.2.1,
the rectangular area with the size of the width of the stock sheet at end of the new row
is considered as the active portion of the stock sheet at each allocation stage. Then the
scanning operation as described above is done in the active portion.
Having defined what constitutes a void region in the layout, we can now describe
how the approach attempts to find effective placements of the remaining pieces. This
approach is referred to Alexandros and Murray 2007, but this research employs
another method to solve it. In order to determine whether it is appropriate to place a
piece to a void region, the approach considers the ratio of their areas. Firstly, the