Defesa de Mestrado de Kent Emershon Yucra Quispe

O Problema de Realocação de Blocos é um problema importante em sistemas de armazenamento. Um exemplo de entrada para este problema consiste em um conjunto de blocos distribuídos em pilhas, onde cada bloco é identificado por um número que representa a prioridade de recuperação do bloco e onde cada pilha tem um mesmo limite de altura máxima. O objetivo é recuperar todos os blocos, respeitando sua prioridade de recuperação executando o menor número de realocações. Só blocos no topo de uma pilha podem ser movidos, com dois tipos de movimentos: ou um bloco é recuperado, quando ele tem a mais alta prioridade de recuperação entre os blocos empilhados, ou o bloco é realocado do topo de uma pilha para o topo de outra pilha. Resolver este problema é crítico em sistemas de armazenamento, pois economiza tempo e recursos operacionais. Apresentamos dois novos limitantes inferiores para o numero de realocações em uma solução ótima. Implementamos um algoritmo de deepening branch-and-bound usando essas novas propostas de limites inferiores e outros limites inferiores bem conhecidos da literatura. Foi realizado um extenso conjunto de experimentos computacionais mostrando que os novos limites inferiores melhoram o desempenho do algoritmo exato, resolvendo mais instancias otimamente do que quando usando outros limites inferiores na mesma quantidade de tempo.