| |
| Acadêmico(a): Rodrigo DAvila |
| Título: JPACKING: PROGRAMA PARA DISTRIBUIÇÃO OTIMIZADA DE POLÍGONOS EM UM PLANO BIDIMENSIONAL UTILIZANDO ALGORITMOS GENÉTICOS |
| |
| Introdução: |
Um problema frequente na indústria de manufatura de peças de roupa, tecido, couro, até metal e madeira é o empacotamento de peças para corte. Também conhecido como distribuição otimizada de polígonos em um plano bidimensional, esse problema tem por objetivo agrupar polígonos visando maximizar a utilização do material de maneia a ocupar o menor espaço possível, evitando desperdício de matéria-prima (BRANDT, 2011; HAIMING, 2006; JUNIOR, 2013). A distribuição otimizada trata-se de uma tarefa de natureza NP-Difícil, sendo assim, acredita-se não haver uma resposta determinística em um tempo polinomial (JUNIOR; PINHEIRO; SARAIVA, 2013). Contudo, este problema pode ser separado em dois passos distintos: o primeiro se refere a estratégia de encaixe, onde é utilizado um algoritmo geométrico para posicionar as peças no plano; o segundo trata a ordem de disposição, onde procura-se uma ordem que permita maximizar a utilização do material (HAIMING; JIONG; XINSHENG, 2006). Para realizar o encaixe dos polígonos, dado a sua forma irregular, uma estratégia comumente utilizada na literatura é a aplicação do algoritmo de Botton-left fill com No-Fit- Polygon (NFP). Esses algoritmos utilizam a natureza geométrica dos polígonos para realizar a rotações e translações dos polígonos, de forma a evitar a sobreposição e respeitar as dimensões definidas por recipiente (MUNDIM; QUEIROZ, 2012). Além da realização do encaixe, torna-se necessário a aplicação de um método heurístico para determinar a ordem de disposição das peças (HAIMING; JIONG; XINSHENG, 2006). Existem implementações que aplicam técnicas de heurística local, como Hill Climbing e Tabu Search. Essas técnicas visam buscar soluções através da seleção de uma peça e a manipulação das suas peças vizinhas, a diferença entre as duas é que o Hill Climbing aplica somente a solução corrente e o Tabu Search procura manter um histórico de soluções geradas (BRANDT, 2011). Além da aplicação destas técnicas para determinar a disposição das peças, técnicas que utilizam Algoritmos Genéticos são amplamente utilizadas (HAIMING; JIONG; XINSHENG, 2006). Diferente das técnicas utilizadas por Brandt (2011), onde a aplicação ocorre em uma peça e seus vizinhos, os operadores do Algoritmo Genético permitem aplicar em todo o conjunto de peças, possibilitando uma melhor convergência, resultando na maximização da ocupação de matéria-prima (HAIMING; JIONG; XINSHENG, 2006).
Por esse motivo, o objetivo desse trabalho é implementar um programa capaz retornar uma solução completa para o problema de disposição de formas irregulares em uma superfície plana bidimensional, utilizando a técnica de Bottom-left fill com NFP. Além de prever a disposição das peças utilizando Algoritmo Genético. |
| |
|
