Problemas de empacotamento em faixa de itens irregulares e quasi-poliominós

Autor(es)

Marcos Okamura Rodrigues

• Tipo de documento: Tese de Doutorado
• Imprenta: São Carlos.
• Instituição: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Data de defesa: 2020-04-06

Membros da banca

Franklina Maria Bragion de Toledo; Marina Andretta; Pedro Augusto Munari Junior; Adriana Cristina Cherri Nicola

• Orientador: Franklina Maria Bragion de Toledo

Resumo

O problema de empacotamento em faixa de itens irregulares consiste em cortar um conjunto de itens bidimensionais a partir de um objeto com largura fixa usando o menor comprimento possível. Apesar de sua importância econômica para várias indústrias, devido a sua dificuldade de resolução poucos métodos exatos foram direcionados para o problema. Recentemente, um modelo de progamação inteira mista no qual os itens são posicionados sobre uma grelha foi proposto. Embora o modelo tenha provado a otimalidade para algumas instâncias de grande porte, ele possui um grande número de restrições de não-sobreposição, que cresce rapidamente de acordo com a resolução da discretização e o número de itens distintos. Nesta tese, é proposto um modelo de cobertura por cliques para reduzir o número de restrições e melhorar a relaxação linear. As coberturas são obtidas através de uma heurística desenvolvida pelo próprio autor. O modelo obtido superou a performance do modelo anterior para a maioria das instâncias avaliadas e obteve uma solução ótima para instância com até 25 itens (22 itens distintos) sujeito à discretização da grelha. Recentemente, outro modelo de programação inteira mista foi proposto para o problema, mas ele permite um grande número de soluções simétricas. Nesta tese, novas restrições de quebra de simetria são propostas para melhorar o modelo. Experimentos computacionais foram realizados para instâncias com itens convexos. Os resultados indicaram que a formulação proposta é melhor que a anterior para a maioria das instâncias, uma vez que melhora os limitantes inferiores e reduz o tempo de execução e o número de nós explorados para provar a otimalidade. Um caso particular de item irregular é um poliominó. 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 itens 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. Nesta tese, estudamos o problema de empacotamento em faixa de quasi-poliominós. São propostos dois modelos de programação inteira para o problema e realizados testes computacionais para avaliá-los. Os modelos foram avaliados utilizando instâncias da literatura e apresentaram bons resultados, obtendo uma solução ótima para uma instância com 320 itens (20 itens distintos) em um recipiente de dimensões 44x50. Como esperado, foram encontradas mais soluções ótimas quando não há rotações e reflexões e quando as dimensões dos itens são pequenas. (AU)

• Processo FAPESP: 14/23900-0 - Problemas de corte e empacotamento de itens irregulares e quasi-poliominós
• Beneficiário: Marcos Okamura Rodrigues
• Modalidade de apoio: Bolsas no Brasil - Doutorado