TITLE:
A Particle Swarm Optimization Algorithm for a 2-D Irregular Strip Packing Problem
AUTHORS:
Mohamed A. Shalaby, Mohamed Kashkoush
KEYWORDS:
Cutting and Packing; Irregular Strip Packing; Nesting; Placement Procedures; Particle Swarm Optimization
JOURNAL NAME:
American Journal of Operations Research,
Vol.3 No.2,
March
28,
2013
ABSTRACT:
Two-Dimensional
Irregular Strip Packing Problem is a classical cutting/packing problem. The
problem is to assign, a set of 2-D irregular-shaped items to a rectangular
sheet. The width of the sheet is fixed, while its length is extendable and has
to be minimized. A sequence-based approach is developed and tested. The
approach involves two phases; optimization phase and placement phase. The
optimization phase searches for the packing sequence that would lead to an
optimal (or best) solution when translated to an actual pattern through the
placement phase. A Particle Swarm Optimization algorithm is applied in this
optimization phase. Regarding the placement phase, a combined algorithm based
on traditional placement methods is developed. Competitive results are
obtained, where the best solutions are found to be better than, or at least
equal to, the best known solutions for 10 out of 31 benchmark data sets. A
Statistical Design of Experiments and a random generator of test problems are
also used to characterize the performance of the entire algorithm.