A hybrid heuristic for the constrained two-dimensional non-guillotine orthogonal cutting problem
José F. Gonçalves (jfgoncalfep.up.pt)
Abstract: This paper addresses a constrained two-dimensional (2D) non-guillotine cutting problem, where a fixed set of small rectangles has to be cut from a larger stock rectangle so as to maximize the value of the rectangles cut. 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: Cutting, packing, two-dimensional packing, two-dimensional cutting, non-guillotine cuting, genetic algorithm.
Category 1: Applications -- OR and Management Sciences (Other )
Category 2: Combinatorial Optimization (Meta Heuristics )
Citation: AT&T Labs Research Technical Report TD-6UNQN6. AT&T Labs Research, Florham Park, NJ 07932 USA, October 17, 2006.
Entry Submitted: 10/17/2006
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|