A Genetic Algorithm for the Rectangular Strip Packing Problem

A genetic algorithm is proposed for the rectangular strip packing problem. It uses the sorted integer string with symbol as individuals of the initial population, so that the quality of the related solutions can be improved. An approach adapted from the minimum horizon approach is used to decode the strings. It dynamically adjusts the orders of the elements in a string, and selects the most appropriate to pack at the current position, such that the material utilization may be improved. The computational results from more than twenty benchmark problems indicate that the algorithm is efficient both in computation time and in material utilization. Finally, a framework based on the algorithm is proposed for the VLSI module placement problem.