Algoritmo genético com chaves aleatórias para o problema de corte guilhotinado bidimensional em três estágios e com restrições de precedência

Abstract

This dissertation addresses the 3-staged 2D Guillotine Cutting Stock Problem With Precedence Constraints (2DCSP-PC). This problem is a generalization of the 3-staged 2D Guillotine Cutting Stock Problem (2DCSP), which deals with precedence constraints between the items to be cut. The goal is to minimize the amount of material used to cut all the items. As far as one can tell, this new precedence constraint prevents the use of most algorithms in the literature for 2DCSP, because they have not been designed to consider it. First, two constructive heuristics present in the literature have been adapted for the 2DCSP-PC, a Finite First-Fit heuristic (FFF) and a Sequential Heuristic Procedure (SHP). Since the pre-processing stage of the instances chooses an orientation for the items and fixes it, two Biased Random-Key Genetic Algorithms (BRKGA) were proposed, the first fixes the items horizontally, in other words, with their width greater than or equal to their height (BRKGA), and the second chooses the orientation of the items (BRKGA-R). The latter and the former were compared with the Evolutionary Algorithm with Elements Representation (EAe) present in the literature. The experiments showed that the BRKGA heuristic achieved strictly better results than the others for the vast majority of the instances that have been tested.