Condição |
Titulares - Professores Doutores |
Unidade/Instituição |
Orientador/Presidente |
Eduardo Candido Xavier |
IC/UNICAMP |
Externo à Unidade |
Luidi Gelabert Simonetti |
Coppe/UFRJ |
Interno à Unidade |
Cid Carvalho de Souza |
IC/UNICAMP |
Condição |
Suplentes - Professores Doutores |
Unidade/Instituição |
Interno à Unidade |
Mário César San Felice |
IME/USP |
Externo à Unidade |
Kelly Cristina Poldi |
IMECC/UNICAMP |
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.