META-HEURÍSTICA LNS APLICADA AO PROBLEMA DO EMPACOTAMENTO QUADRÁTICO

O QMC-VSBPP (Quadratic Multiple Constraint Variable Sized Bin-Packing Problem) é
uma variante do problema de empacotamento que emerge sempre que itens com múltiplas dimen-
sões de peso precisam ser alocados em diferentes tipos de caixas de modo a minimizar tanto os
custos fixos de utilização dessas caixas quanto os custos conjuntos (de comunicação) entre itens se-
parados. Com aplicações diretas no contexto de implantação de serviços em ambientes de nuvem, o
QMC-VSBPP foi recentemente introduzido na literatura. Este trabalho propõe estruturas de dados
especializadas e um algoritmo de Busca em Vizinhança Ampla para o QMC-VSBPP. Experimentos
computacionais mostram que a solução proposta supera a solução estado da arte, encontrando novas
melhores soluções para 83 instâncias da literatura.