27 jan 2025
14:00 Defesa de Doutorado Auditório do IC3
Tema
Problemas de Empacotamento com Número Fixo de Recipientes
Aluno
Mauro Roberto Costa da Silva
Orientador / Docente
Rafael Crivellari Saliba Schouery - Coorientador: Lehilton Lelis Chaves Pedrosa
Breve resumo
Problemas de empacotamento possuem diversas aplicações práticas, principalmente na logística dos setores de industrias e serviços. A logística é responsável por uma parcela considerável do custo dos serviços e dos produtos, e uma otimização nesses processos podem reduzir custos, tornando os produtos mais baratos e competitivos. 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, empacotar 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 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. O objetivo principal deste trabalho é desenvolver novos algoritmos de aproximação e exatos para problemas de empacotamento com número fixo de recipientes, mais especificamente os problemas Maxspace, Positional Knapsack Problem e Extensible Bin Packing, levando em consideração variantes encontradas na prática para esses problemas.
Banca examinadora
Titulares:
| Rafael Crivellari Saliba Schouery | IC/UNICAMP |
| Anand Subramanian | UFPB |
| Edna Ayako Hoshino | UFMS |
| Santiago Valdés Ravelo | IC/UNICAMP |
| Andre Luís Vignatti | UFPR |
Suplentes:
| Ruben Interian Kovaliova | IC/UNICAMP |
| Carla Negri Lintzmayer | CMCC/UFABC |
| Teobaldo Leite Bulhões Júnior | UFPB |