A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces

A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces

0.00 Avg rating0 Votes
Article ID: iaor20083871
Country: Netherlands
Volume: 172
Issue: 3
Start Page Number: 814
End Page Number: 837
Publication Date: Aug 2006
Journal: European Journal of Operational Research
Authors:
Keywords: heuristics: genetic algorithms
Abstract:

Given a set of rectangular pieces and a container of fixed width and variable length, the two-dimensional strip packing problem (2D-SPP) consists of orthogonally placing all the pieces within the container, without overlapping, such that the overall length of the layout is minimised. Until now mainly heuristics, for example genetic algorithms (GA), were proposed for the 2D-SPP which use encoded solutions that are manipulated by standard operators. In this paper a GA for the 2D-SPP is suggested that works without any encoding of solutions. Rather fully defined layouts are manipulated as such by means of specific genetic operators. Two additional constraints, namely the orientation constraint and the guillotine constraint, can be taken into account. The GA is subjected to a comprehensive test using benchmark instances with up to 5000 pieces. Compared to eleven competing methods from the literature the GA performs best.

Reviews

Required fields are marked *. Your email address will not be published.