Problema de corte bidimensional. Aplicação a um caso real

O problema de corte guilhotina e empacotamento bidimensional rectangular consiste em alocar múltiplas peças pequenas ? itens ? numa ou mais placas de tamanho maior ? objectos ? num padrão que minimize o desperdício de matéria-prima. A motivação para a realização deste projecto é resolver um problema real de uma empresa portuguesa tentando, ao mesmo tempo, propor algo novo. Para isso, desenvolvem-se e apresentam-se duas novas heurísticas, a Guillotinable Bottom-Left First Fit Decreasing Height (BLFFDHG) e a Bottom-Left First Fit Decreasing Height (BLFFDH), baseadas na First Fit Decreasing Height (FFDH) e Bottom-up left-justified (BL), em que, após um nível ter sido preenchido com a abordagem da FFDH, e antes de se abrir um novo nível para o próximo rectângulo, o nível actual é exaustivamente examinado, usando a heurística BL, de modo a tentar alocar itens no espaço que sobra entre dois níveis consecutivos. A diferença entre as novas heurísticas reside no facto de uma impor o corte guilhotina. Em ambas nenhuma das peças pode ser rodada ou sobreposta. Só depois de explorado o nível actual é aberto um novo. Os resultados são comparados com heurísticas da literatura, num conjunto de instâncias reais, em corte de roupeiros, e da literatura. As heurísticas propostas são comparadas entre si em termos de tempos de execução e é determinada a complexidade empírica da programação. Os resultados obtidos indicam que os são bastante competitivos em relação às outras heurísticas usadas nos testes. A complexidade empírica da programação é, para ambas, O(n^3).