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

Subject Areas : Mathematical Optimization

Jaya Thomas ¹ , Narendra S. Chaudhari ²

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

Received: 2020-10-02 Accepted : 2020-10-02 Published : 2014-04-01

Keywords: Combinatorial optimization  Crossover , Fitness  Genetic algorithm  Operation research , Placement approach  Strip packing,

Abstract :

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.