Defesa de Mestrado de Kent Emershon Yucra Quispe

Título do Trabalho
An Exact Algorithm for the Blocks Relocation Problem with New Lower Bounds
Candidato(a)
Kent Emershon Yucra Quispe
Nível
Mestrado
Data
Add to Calender 2018-04-20 00:00:00 2018-04-20 00:00:00 Defesa de Mestrado de Kent Emershon Yucra Quispe An Exact Algorithm for the Blocks Relocation Problem with New Lower Bounds Sala 85 IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
09:00h
Local
Sala 85 IC 2
Orientador(a)
Eduardo Candido Xavier
Banca Examinadora

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

Resumo

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.