A new metaheuristic genetic-based placement algorithm for 2D strip packing

Journal of Industrial Engineering International

دوره 10، شماره 1، تیر 2014   

نویسندگان

Jaya Thomas؛ Narendra S. Chaudhari

Department of Computer Science and Engineering, Indian Institute of Technology Indore, Indore, India

چکیده

Given a container of fixed width, infinite height and a set of rectangular block, the 2D-strip packing problem consists of orthogonally placing all the rectangles such that the height is minimized. The position is subject to confinement of no overlapping of blocks. The problem is a complex NP-hard combinatorial optimization, thus a heuristic based on genetic algorithm is proposed to solve it. In this paper, we give a hybrid approach which combined genetic encoding and evolution scheme with the proposed placement approach. Such a combination resulted in better population evolution and faster solution convergence to optimal. The approach is subjected to a comprehensive test using benchmark instances. The computation results validate the solution and the effectiveness of the approach.

کلیدواژه‌ها

Combinatorial optimization  Crossover ؛ Fitness  Genetic algorithm  Operation research ؛ Placement approach  Strip packing