Abordagens Heurísticas ao Posicionamento de Formas Irregulares

• Type: Thesis
• Date: 2006

Authors

A. Miguel Gomes (Author) FEUP

Scientific classification

FOS: Engineering and technology > Electrical engineering, Electronic engineering, Information engineering

CORDIS: Physical sciences > Mathematics > Applied mathematics > Operations research

Other information

Resumo (PT): Nesta tese aborda-se o problema de Posicionamento de Formas Irregulares, com especial ênfase na resolução de instâncias reais destes problemas. É feita uma classificação dos problemas de Posicionamento em geral e apresentada uma caracterização dos problemas de Posicionamento de Formas Irregulares. São ainda discutidas e analisadas diversas ferramentas geométricas necessárias para a resolução eficiente de problemas de Posicionamento de Formas Irregulares. É apresentado um modelo matemático global para o problema de Posicionamento de Formas Irregulares, assim como simplificações ao modelo global que permitem resolver dois subproblemas de posicionamento: o de compactação e o de separação. Experiências computacionais com os modelos matemáticos permitiram mostrar as limitações na utilização do modelo global e as potencialidades e capacidades dos modelos simplificados na resolução de problemas de compactação e de separação. Foi desenvolvida uma nova heurística construtiva de posicionamento de formas irregulares, baseada na ordenação prévia das formas irregulares e no posterior posicionamento de sucessivas formas irregulares por uma regra de posicionamento gulosa do tipo “bottom-left”. Foram também estudados diversos critérios de ordenação das formas irregulares. Foi proposto um novo algoritmo de pesquisa local, “2-exchange”, que se baseia na representação de padrões de corte por sequências de formas irregulares e na realização duma pesquisa local sobre a sequência de formas irregulares, por operações de troca entre todos os elementos de uma subvizinhança. Foi ainda estudada a possibilidade de utilizar uma meta-heurística para conduzir o processo de pesquisa sobre as sequências de formas irregulares, que veio a revelar-se pouco adequada devido à reduzida relação entre duas sequências vizinhas e os respectivos padrões de corte. Foram também desenvolvidas e estudadas abordagens a problemas de Posicionamento de Formas Irregulares baseadas em algoritmos híbridos de pesquisa local, que operam directamente sobre os padrões de corte. Estas abordagens baseiam-se numa estrutura de vizinhança, “LocalCompact”, que utiliza modelos matemáticos para realizar operações de compactação de padrões de corte e de remoção de situações de não admissibilidade. Os algoritmos híbridos combinam a meta-heurística pesquisa por arrefecimento simulado com os modelos matemáticos embebidos na estrutura de vizinhança. Foi ainda proposta uma abordagem em várias fases, N-Fases, que decompõe o problema de posicionamento em grupos de formas irregulares de tamanho semelhante e no posterior posicionamento de cada grupo em fases “quase independentes”. O processo inicia-se pelo grupo com as formas irregulares maiores e em cada uma das fases de posicionamento é necessário ter em consideração as formas irregulares posicionadas em fases anteriores, designadamente pela tentativa de preencher espaços vazios deixados entre as formas irregulares maiores. Testes e experiências computacionais, com instâncias reais de problemas de Posicionamento de Formas Irregulares, demonstraram as potencialidades das abordagens apresentadas neste trabalho, em particular dos algoritmos híbridos e da abordagem em N-Fases propostos.

Abstract (EN): This thesis deals with the Irregular Strip Packing problem, also known as the Nesting problem, with a special emphasis put on the resolution of real world instances. A classification for Cutting and Packing problems is presented and the Irregular Strip Packing problem is characterised. Several geometric tools needed to tackle Irregular Strip Packing problems are presented and discussed. A mathematical model for the global Irregular Strip Packing problem is presented, along with several simplifications introduced to this model that allow the resolution of two packing subproblems: the layout compaction and the layout separation problems. Computational experiments have shown the global model limitations and the potentialities of the compaction and the separation models. A new constructive heuristic for positioning irregular shapes is presented, based on ordered sequences of irregular shapes and the successive positioning of the next irregular shape ruled by a greedy bottom-left heuristic. Several ranking criteria were studied. A new local search algorithm for the Irregular Strip Packing problem, the 2-exchange, is presented. This algorithm uses sequences of irregular shapes to represent layouts and performs a search over the sequences by exchanging positions in the sequence. The possibility of using a metaheuristic to drive the search was also investigated, which came to be not so adequate due to the low relationship between two neighbour sequences and the respective layouts. Irregular Strip Packing approaches based on hybrid local search algorithms were also studied and developed. These approaches rely on the LocalCompact neighbourhood structure to perform the search directly over the layouts. The LocalCompact neighbourhood structure is based on the compaction and separation mathematical models to compact layouts and to remove any unfeasibility from the layouts. The hybrid local search algorithms combine the simulated annealing metaheuristic with the mathematical models embedded in the neighbourhood structure. A multi-stage approach to tackle Irregular Strip Packing problems is also proposed. This approach divides the available irregular shapes in groups, accordingly to their relative sizes. At each stage, a different group is packed, starting by the groups with the bigger pieces. For the second and later stages it is necessary to take into account the previously placed irregular shapes, trying to fill the gaps among the bigger pieces. Computational tests and experiments with real instances have shown the potentialities of the approaches presented in this thesis, specially of the proposed hybrid algorithms and multi-stage approaches.

Language: Portuguese

Type (Professor's evaluation): Scientific

No. of pages: 228