A genetic algorithm for the two-dimensional strip-packing problem

The paper presents a genetic algorithm (GA) for the two-dimensional strip-packing problem (SPP) with rectangular shaped pieces. Both the non-guillotinable SPP and the guillotinable SPP can be tackled. The genetic algorithm has been derived from a GA that was proposed earlier for solving the containter-loading problem (CLP) with a single container to be loaded. The characteristic features of the earlier GA have been maintained: solutions are represented by data structures tailored to the problem at hand and specific genetic operators are used to generate offspring. In order to deal with a given instance of the SPP, a sequence of CLP instances with descending container lengths has to be solved. Th GA for the SPP is subjected to a comparative test which includes methods from other authors. The results for well-known benchmark problems show a high performance of the GA for strongly heterogeneous sets of pieces.