Abstract:
The irregular nesting problem, also known as stock placement problem has been studied
and investigated over many decades where convex/non-convex pieces have to be
placed inside the main sheet such that no piece overlap and cross the boundary of
sheet. Nesting problem is widely used in raw material industries, like clothing, wood,
metal, leather and paper making industries. The objective is to maximize the utilization
of sheet and minimize the waste of sheet keeping the sheet width constant. There
are many heuristic techniques in the literature used to solve the nesting problems. In
nesting problem, there are two basic categories that are used by the researchers; one
is placement strategy and second one is sorting strategy. Geometric constraints are the
fundamental problems in nesting problems.
In this thesis, a heuristic algorithm is used to solve nesting problems which uses the
concept of optimal groups of unique shapes based on placement routine which is a combination of three optimization functions, boundary overlap, convex hull and wastage.
Overlap detection is performed to check the polygons overlap. Iterative method is used
to generate a list of polygons placement and an objective function is measured against
each placement which is again a combination of three optimization functions: boundary
overlap, compaction and wastage. The polygon is placed at the placement which has
maximum value of boundary overlap, maximum compaction and minimum wastage.
The proposed technique is tested with few examples of convex and non convex
shapes. Our proposed algorithm’s results are compared with previous benchmark algorithms already available in the literature. Our proposed algorithm’s results are superior to previous works in the literature and is a strong candidate for real industries.
