Optimization Online


A multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem

José F. Gonçalves(jfgoncal***at***fep.up.pt)
Mauricio G. C. Resende(mgcr***at***research.att.com)

Abstract: This paper addresses a constrained two-dimensional (2D), non-guillotine restricted, packing problem, where a fixed set of small rectangles has to be packed into a larger stock rectangle so as to maximize the value of the rectangles packed. The algorithm we propose hybridizes a novel placement procedure with a genetic algorithm based on random keys. We propose also a new fitness function to drive the optimization. The approach is tested on a set of instances taken from the literature and compared with other approaches. The experimental results validate the quality of the solutions and the effectiveness of the proposed algorithm.

Keywords: Packing, cutting, two-dimensional packing, two-dimensional cutting, non-guillotine cutting, genetic algorithm.

Category 1: Combinatorial Optimization (Meta Heuristics )

Category 2: Global Optimization (Stochastic Approaches )

Category 3: Applications -- OR and Management Sciences (Production and Logistics )

Citation: AT&T Labs Research Technical Report TD-7M7QJG, AT&T Labs Research, Florham Park, NJ 07932, December 10, 2008.

Download: [PDF]

Entry Submitted: 01/07/2009
Entry Accepted: 01/08/2009
Entry Last Modified: 01/07/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society