A genetic algorithm for a 2D industrial packing problem

Cutting and packing problems are encountered in many industries, with different industries incorporating different constraints and objectives. The wood-, glass- and paper industry are mainly concerned with the cutting of regular figures, whereas in the ship building, textile and leather industry irregular, arbitrary shaped items are to be packed. In this paper two genetic algorithms are described for a rectangular packing problem. Both GAs are hybridised with a heuristic placement algorithm, one of which is the well-known Bottom-Left routine. A second placement method has been developed which overcomes some of the disadvantages of the Bottom-Left rule. The two hybrid genetic algorithms are compared with heuristic placement algorithms. In order to show the effectiveness of the design of the two genetic algorithms, their performance is compared to random search. (C) 1999 Elsevier Science Ltd. All rights reserved.