Double chromosome GA with Corner Junction for solving the 2D strip packing problem

摘要

In this paper, a new approach is proposed for solving the two-dimensional rectangle packing problem. The Corner-Junction (CJ) method [1] is combined with a Genetic Algorithm (GA) approach which enables 90-degree rotation of the rectangles in the chromosome structure. Unlike the original CJ+GA approach, which adopted a single chromosome structure, this refinement adopts a double chromosome structure which substantially reduces the bulk of computational processing and facilitates broader application of genetic operations. Experimental results show that this new CJ+DC approach provided good performance and significant savings of time for recognized benchmark tests C1-C6 for two dimensional strip packing problems [2], and significantly enhanced quality in terms of elimination or reduction of gap in comparison to established packing approaches. Results also compare favorably to those of the previous CJ+GA approach [1], which had a single-straight chromosome.