A multiobjective evolutionary algorithm for the 2D Guillotine Strip Packing Problem

This paper presents a specialized multiobjective evolutionary algorithm SPEA2 (Strength Pareto Evolutionary Algorithm 2) coupled, separetely, with four placement heuristics for solving the 2D Guillotine Strip Packing Problem. In this study, the problem requires minimization of both the amount of wasted material and the number of independent cuts required by a packing. With the goal of solving this multiobjective version of the problem, the construction phase of the GRASP algorithm (Greedy Randomized Adaptive Search Procedure) is used to generate a portion of the initial population of SPEA2. Four different placement heuristics, Next-Fit, a variation of Next-Fit, Best-Fit and First-Fit, were coupled with SPEA2 and were tested on a set of test data. The results show that the presented methodology is able to generate a good set of candidate solutions for each test problem. A statistical comparison methodology, based on multiobjective principles, was used to compare the four algorithm variants.