Problemas de empacotamento com número fixo de recipientes

Autor(es)

Mauro Roberto Costa da Silva

• Tipo de documento: Tese de Doutorado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 2025-01-27

Membros da banca

Rafael Crivellari Saliba Schouery; Santiago Valdés Ravelo; Anand Subramanian; Edna Ayako Hoshino; André Luís Vignatti

• Orientador: Rafael Crivellari Saliba Schouery; Lehilton Lelis Chaves Pedrosa

Resumo

Problemas de empacotamento com número fixo de recipientes consistem em, dado um conjunto de itens e um número de recipientes de uma determinada capacidade, empaco tar um subconjunto dos itens nos recipientes, maximizando ou minimizando uma certa função objetivo, tal como a soma dos valores dos itens empacotados. O Binary Knapsack Problem (KP), o Generalized Assignment Problem (GAP), o Multiple Knapsack Problem (MKP) e o Bin Packing Problem (BPP) são exemplos clássicos de problemas de empacotamento, mas apenas o KP, o GAP e o MKP possuem número fixo de recipientes, já que o BPP permite que novos recipientes sejam criados. Outros problemas com essa característica são o Maxspace, o Positional Knapsack Problem e o Extensible Bin Packing. O Maxspace é um problema de disposição de propagandas, no qual desejamos exibir propagandas em um banner, maximizando a área ocupada pelas propagandas exibidas. O Positional Knapsack Problem é uma variante do Binary Knapsack Problem em que desejamos colocar itens em um recipiente e o valor do item pode variar de acordo com a posição que é empacotado. Já o Extensible Bin Packing (EBP) é um problema de empacotamento em que desejamos adicionar uma quantidade de itens em um número fixo de recipientes de mesmo tamanho, mas, diferentemente dos Maxspace e do PKP, o EBP exige que todos os itens sejam empacotados e permite que os recipientes sejam estendidos, aumentando o custo da solução proporcionalmente ao valor total de extensão. Neste trabalho, apresentamos um Polynomial-Time Approximation Scheme (PTAS) para uma variante do Maxspace, um Fully Polynomial-Time Approximation Scheme (FPTAS) para uma função de variação específica do PKP e um PTAS para o PKP com um conjunto de funções mais geral. Além disso, apresentamos algoritmos utilizando a formulação arc-flow e a técnica de branch-and-cut-and-price para o EBP (AU)

• Processo FAPESP: 20/13162-2 - Problemas de empacotamento com número fixo de recipientes
• Beneficiário: Mauro Roberto Costa da Silva
• Modalidade de apoio: Bolsas no Brasil - Doutorado