Um comparativo de duas metaheurísticas aplicadas a problemas de bin packing bidimensional

Abstract

Cutting and Packing processes are widely used by industries and constantly being studied by the field of Operational Research as their costs significantly affect the final cost of a product. It is important to reduce these costs by managing the industrial processes in a way that industries can minimize their waste and increase the profits. However, cutting and packing problems are considered NP-hard combinatorial optimization problems, and they can not be solved by exact algorithms because it requires a wide variation in computational time. The objective of this study is to compare the results obtained by Tabu Search and Genetic Algorithm metaheuristics in solving 2D multiple bin size bin packing problems in order to achieve viable solutions that optimize the number of bins in a reduced computational time. The metaheuristics were coded and 15 bin packing problems instances from the OR-Library were solved in order to evaluate their performance. The problems have a maximum of 150 objects and the largest object has 30x30 of dimensions. The Bottom-Left heuristic proved to be more efficient than the metaheuristics, and the Tabu Search achieved better results than the Genetic Algorithm in 80% of the problems.