Problemas de corte e empacotamento de itens irregulares e quasi-poliominós

Resumo

Um poliominó consiste em um conjunto de quadrados de mesma dimensão conexos pela junção de uma de suas arestas. Um quasi-poliominó é uma generalização do conceito de poliominó, uma vez que representa um subconjunto de quadrados não necessariamente conexos de uma malha quadriculada equidistante. Problemas de corte e empacotamento de quasi-poliominós possuem diversas aplicações reais, por exemplo, o corte de peças de couro, a estamparia de chapas metálicas, o desenho de placas de circuito impresso e a diagramação de páginas de revistas e jornais. Neste projeto, serão estudadas variantes destes problemas, como os problemas de ladrilhamento, mochila, empacotamento em faixas e e empacotamento em mochilas de quasi-poliominós. Serão propostos modelos matemáticos, métodos exatos e heurísticos que serão comparados com modelos e métodos da literatura.