|
Acadêmico(a): Rodrigo DAvila |
Título: JPACKING: PROGRAMA PARA DISTRIBUIÇÃO OTIMIZADA DE POLÍGONOS EM UM PLANO BIDIMENSIONAL UTILIZANDO ALGORITMOS GENÉTICOS |
|
Abstract: |
This work presents the development of the JPacking program, capable of performing the optimized distribution of polygons in a two-dimensional plane using Genetic Algorithms. Programs such as JPacking are fundamental for the cutting of fabric, metal, wood, among others. They help to maximize the use of raw materials to avoid waste. The optimized arrangement is an NP-Difficult problem with no deterministic response in a polynomial time. Therefore, the implementation of JPacking uses Genetic Algorithms to generate the order of insertion of the polygons and the algorithms of No-fit polygon and Bottom-left fill to arrange the polygons. The possibility of importing and exporting the results through SVG files was also implemented. To evaluate the results were created tests comparing parameters such as number of generations and population, rotations, Crossover and Mutation factors, occupation comparison with the Hill Climbing and Tabu Search algorithms, variation of the height of the raw material and behavior of the packaging. The results showed that JPacking is capable to perform the optimized packaging of irregular polygons, also being able to achieve the same results of algorithms like Hill Climbing and Tabu Search on certain datasets, and to perform error-free behavior in most of the tests. It was concluded that JPacking can be optimized by running tests for calibration of the execution parameters for certain datasets, and by implementing its extensions and applying improvements can make JPacking usable in production environments. |
|
|