Meta-heurísticas bioinspiradas aplicadas ao problema do corte bidimensional guilhotinado em uma indústria vidreira

Abstract

The two-dimensional guillotined cutting is a combinatorial optimization problem that consists in determining an arrangement of items to be cut from a larger piece, maximizing the material use, but respecting the restrictions imposed by the cutting equipment and the production flow. The optimization of two-dimensional guillotined cutting is an important factor for production systems performance at glassworks industries, because it maximizes the materials use. Several research have shown the application of bio-inspired metaheuristics like Genetic Algorithm and Ant Colony Algorithm in solving combinatorial optimization problems as two-dimensional guillotine cutting. The Genetic Algorithm is an abstraction of natural evolution models which operate on a population of individuals, through the application of mechanisms of selection, crossover and mutation, generating new and fitter individuals in each generation. The Ant Colony Algorithm is inspired in ant colonies behavior, that are capable of finding the shortest path between their colony and food sources. Influenced by pheromones presence in this way, these ants tend to follow the direction in which the concentration of pheromone is stronger. This work aimed to apply, individually and combined, the Genetic Algorithm and Ant Colony Algorithm to solve the two-dimensional guillotine cutting problem in a glass industry. For the experiments it was used a real-world database of 50 requests provided by a cut glass industry in São Paulo city and 500 instances, obtained from literature, divided into 10 classes with varying sizes of items and objects. The best results were compared with two commercial softwares focused on two-dimensional cutting optimization. The final results were satisfactory, confirming the bio-inpired metaheuristics as an option to solve the two-dimensional guillotine cutting problem in a glass industry.