Apresentações
Abordagens baseadas em grafos para problemas de cortes rectangulares bidimensionais
Eduarda Pinto Ferreira
— ISEP
Este apresentação centra-se na área dos chamados problemas de corte e empacotamento rectangulares bidimensionais não guilhotináveis, sendo descrito um conjunto de abordagens baseadas em grafos com vista à resolução destes problemas. Tendo por base o algoritmo exacto proposto por Fekete e Schepers, utilizam-se as propriedades dos grafos de visibilidade, que representam a projecção dos itens de um empacotamento segundo os eixos coordenados, para verificar a admissibilidade e construir o empacotamento, exclusivamente no domínio dos grafos. Em particular, introduzem-se as condições necessárias e suficientes para a existência de uma relação de equivalência entre um empacotamento e um par de grafos de visibilidade.
Dado o algoritmo exacto para a resolução de problemas de corte e empacotamento bidimensionais ser muito pesado do ponto de vista computacional, estando a sua aplicação limitada a problemas com algumas dezenas de elementos, vai-se apresentar uma abordagem multi-nível capaz de resolver problemas com milhares de elementos, de forma eficiente.
Apresenta-se ainda um estudo de estruturas de vizinhança baseadas em grafos de visibilidade, tendo como objectivo a sua aplicação em problemas de corte e empacotamento rectangulares bidimensionais. Finalmente apresentam-se alguns testes exploratórios realizados no sentido de verificar a eficácia da utilização de algumas das estruturas de vizinhança definidas na metaheurística arrefecimento simulado (simulated annealing).
Palavras-chave:
grafos, corte e empacotamento, estruturas de vizinhança, metaheurísticas