| Resumo: |
Os problemas de Cortes e Empacotamentos são problemas reais de indústrias e serviços, que surgem sempre que matérias-primas ou espaços têm que ser divididos em partes mais pequenas, sem sobreposições, de tal forma que o desperdício seja minimizado. São problemas difíceis de Optimização Combinatória e têm em comum a existência de um sub-problema geométrico, motivado pelas restrições de não sobreposição entre as peças. De entre os problemas de cortes e empacotamentos, os problemas de "nesting" (corte de figuras irregulares) são os que apresentam uma componente geométrica mais complexa, dado lidarem com peças e/ou matéria-prima de formas irregulares (não rectangulares, não circulares) - ficheiro nesting.pdf. Estes problemas surgem na prática nas indústrias do calçado, das confecções, máquinas-ferramenta, naval, etc. Como afirmado anteriormente, o problema de "nesting" acrescenta à dificuldade combinatória dos restantes problemas de cortes e empacotamentos a complexidade da manipulação geométrica de formas irregulares. O problema aparentemente básico de, dados dois polígonos não convexos e as suas posições relativas, saber de se sobrepõem ou não, é uma tarefa não trivial, consumidora de um tempo de cálculo significativo, limitando consideravelmente os esforço computacional que pode ser dedicado à tarefa de optimização das soluções de "nesting".
Apesar de estudado há já algumas décadas, vários desafios permanecem abertos na resolução de problema de "nesting", muitos dos quais residem na camada geométrica das abordagens de resolução. Estas limitações têm impedido o tratamento da componente combinatória com as ferramentas de optimização que são comuns noutros problemas. Assim, a maioria das abordagens descritas na literatura são simples heurísticas, e apenas recentemente meta-heurísticas mais complexas começaram a ser utilizadas, não existindo abordagens optimizantes.
Para além de limitar a qualidade das soluções  |
Resumo
Os problemas de Cortes e Empacotamentos são problemas reais de indústrias e serviços, que surgem sempre que matérias-primas ou espaços têm que ser divididos em partes mais pequenas, sem sobreposições, de tal forma que o desperdício seja minimizado. São problemas difíceis de Optimização Combinatória e têm em comum a existência de um sub-problema geométrico, motivado pelas restrições de não sobreposição entre as peças. De entre os problemas de cortes e empacotamentos, os problemas de "nesting" (corte de figuras irregulares) são os que apresentam uma componente geométrica mais complexa, dado lidarem com peças e/ou matéria-prima de formas irregulares (não rectangulares, não circulares) - ficheiro nesting.pdf. Estes problemas surgem na prática nas indústrias do calçado, das confecções, máquinas-ferramenta, naval, etc. Como afirmado anteriormente, o problema de "nesting" acrescenta à dificuldade combinatória dos restantes problemas de cortes e empacotamentos a complexidade da manipulação geométrica de formas irregulares. O problema aparentemente básico de, dados dois polígonos não convexos e as suas posições relativas, saber de se sobrepõem ou não, é uma tarefa não trivial, consumidora de um tempo de cálculo significativo, limitando consideravelmente os esforço computacional que pode ser dedicado à tarefa de optimização das soluções de "nesting".
Apesar de estudado há já algumas décadas, vários desafios permanecem abertos na resolução de problema de "nesting", muitos dos quais residem na camada geométrica das abordagens de resolução. Estas limitações têm impedido o tratamento da componente combinatória com as ferramentas de optimização que são comuns noutros problemas. Assim, a maioria das abordagens descritas na literatura são simples heurísticas, e apenas recentemente meta-heurísticas mais complexas começaram a ser utilizadas, não existindo abordagens optimizantes.
Para além de limitar a qualidade das soluções, a falta de ferramentas eficientes para lidar com a componente geométrica do problema provoca também falta de precisão e simplificações excessivas da geometria. Por exemplo, peças com lados não rectilíneos (arcos e "splines") são normalmente aproximadas por conjuntos de arestas exteriores à forma aproximada. Também é habitual restringir as orientações admissíveis para cada peça a um conjunto discreto e pequeno, por não existirem ferramentas que lidem eficientemente com rotações contínuas. São estes os dois desafios que este projecto se propõe resolver: criar um conjunto de ferramentas para lidar com arestas não rectilíneas e rotações contínuas, no contexto específico e adaptadas para a resolução de problemas de "nesting". Conseguir-se-à assim uma maior qualidade das soluções de "nesting", com menor desperdício e, consequentemente, impactos económico e ambiental positivos. |