Novas Contribuições para o Problema de Posicionamento de Figuras Irregulares

• Type: Thesis
• Date: 1995

Authors

António Miguel da Fonseca Fernandes Gomes (Author) FEUP; José Soeiro Ferreira (Technical adviser) FEUP

Associated Institutions

FEUP - Faculdade de Engenharia da Universidade do Porto

Other information

Resumo (PT): A presente tese aborda a resolução de Problemas de Posicionamento de figuras Irregulares. Este é um caso particular dos Problemas de Posicionamento. Nestes problemas pretende-se posicionar objectos pequenos no interior de um objecto maior, de modo a que eles não se sobreponham e a que uma função objectivo, habitualmente o desperdício, seja optimizada. Nos problemas de posicionamento de figuras irregulares apenas duas das dimensões dos objectos são relevantes para a sua resolução, os objectos pequenos têm um forma irregular (não rectangular) e o objecto grande (a placa) ou é rectangular ou é também irregular. Este é um problema de grande importância para diversas indústrias, como por exemplo a têxtil, a do calçado ou a do mobiliário em madeira. A resolução do problema de posicionamento de figuras irregulares supõe a existência de uma biblioteca de ferramentas geométricas capaz de verificar as restrições de índole geométrica inerentes a este problema. Um novo algoritmo, fundamental para esta biblioteca, é desenvolvido, descrito e implementado: o invólucro de posicionamento interno. O invólucro de posicionamento interno é a base de capacidades de alto nível dos algoritmos de posicionamento de figuras irregulares, como o preenchimento de buracos, o posicionamento no interior de placas com forma irregular ou mais simplesmente a implementação de algoritmos de posicionamento conhecidos, de uma forma mais simples. É o caso do algoritmo de Albano e Sappupo que, neste trabalho, é exaustivamente testado e o seu desempenho medido. Um novo algoritmo de posicionamento, baseado numa pesquisa em árvore, é também apresentado, testado e comparado com o algoritmo original de Albano e Sappupo. Testes computacionais mostram as potencialidades deste novo algoritmo na resolução de problemas de posicionamento de figuras irregulares.

Abstract (EN): This thesis deals with the Nesting Problem resolution. This is a special case of the Cutting and Packing Problems. In this problems small objects are positioned inside a bigger one, so that they dont overlap and some objective function, usually the waste, is optimized. In the nesting problems only two dimensions of the objects are relevant for the problem resolution, the small objects have irregular (non-rectangular) shapes and the big object (the plate) is either rectangular or also irregular. This is a quite important problem for several industries, such as the textile, footwear or furniture industries. The nesting problem resolution supposes the existence of a geometric tools library, capable of verifying the geometric constraints inherent to this problem. A new algorithm for a fundamental tool of this library, the inner-fit-polygon, is developed, described and implemented. The inner-fit-polygon is the base for the nesting algorithms advanced high level features like hole-filling, nesting inside an irregular plate or simply allows easier and simpler implementations of well-known nesting algorithms. This is the case of the Albano and Sappupo algorithm, which is, in this work, extensively tested and its performance, dependent of a set of parameters that control its execution, measured. A new tree-search algorithm, in seven different versions, is also presented, tested and compared with the original Albano and Sappupo algorithm. Computational tests show the potentiality of this new algorithm in the resolution of nesting problems.

Language: Portuguese

Type (Professor's evaluation): Scientific

No. of pages: 98