Slimane Abou-Msabah, Ahmed Riadh Baba-Ali and Basma Sagr, University of Science and Technology Houari Boumedienne (USTHB), Algeria

The Bin Packing problem is met in several domains of application, especially in the industry of: sheet metal, wood, glass, paper etc. In this article we are interested to the orthogonal cutting problem, with the hold in charge of the constraint of end-to-end cutting, and orientation constraint. The bin packing problem belongs to the class of NP-hard problems; therefore, our work has turned towards heuristic methods of resolution, and more particularly evolutionary methods. The application of genetic algorithms that are part of the evolutionary methods has limitations for solving the bin packing problem with large data. To minimize this disadvantage, we propose an original method which consists in subdividing the initial problem into two subproblems. The first step tries to apply a hybrid genetic algorithm based on the order of appearance of pieces, to be packed on levels in an infinite band by applying the new placement routine (BLF2G). The second step uses the results of the first, namely the levels, and tries to project them on Bins by applying a second hybrid genetic algorithm. Besides that, we propose a new definition of the problem, it’s about seeing the strip not as usual, with a fixed width and infinite height, but with a fixed height and infinite width. And we must apply some improvements, found in the literature, to the classic genetic algorithm to improve results, by introducing greedy heuristics to the population. Results are compared with other heuristic methods on data sets found in the literature.

Rectangular Bin Packing, Orthogonal Cutting stock, Combinatorial Optimization, Heuristic, Hybrid Genetic Algorithm.