Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/332028
Type: DISSERTAÇÃO DIGITAL
Degree Level: Mestrado
Title: An exact algorithm for the blocks relocation problem with new lower bounds : Um algoritmo exato para o problema de realocação de blocos usando novos limitantes inferiores
Title Alternative: Um algoritmo exato para o problema de realocação de blocos usando novos limitantes inferiores
Author: Yucra Quispe, Kent Emershon, 1992-
Advisor: Xavier, Eduardo Candido, 1979-
Abstract: 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 é identicado por um número que representa sua prioridade de recuperação e todas as pilhas têm um mesmo limite de altura. Apenas blocos no topo de uma pilha podem ser movidos, com dois tipos de movimentos: ou um bloco é recuperado, o que ocorre quando ele tem a mais alta prioridade de recuperação entre os blocos empilhados, ou um bloco é realocado do topo de uma pilha para o topo de outra pilha. O objetivo é recuperar todos os blocos, respeitando sua prioridade de recuperação e executando o menor número de realocações. Resolver este problema é crítico em sistemas de armazenamento, pois economiza tempo e recursos operacionais. Apresentamos dois novos limitantes inferiores para o número de realocações em uma solução ótima. Implementamos um algoritmo de deepening A* usando esses limites inferiores propostos 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 instâncias otimamente do que quando usando outros limites inferiores na mesma quantidade de tempo

Abstract: The Blocks Relocation Problem is an important problem in storage systems. An input instance for this problem consists of a set of blocks distributed in stacks where each block is identified by a retrieval priority number and each stack has the same maximum height limit. Only blocks at the top of a stack can be moved: either a block is retrieved, if it has the highest retrieval priority among the stacked blocks, or it is relocated to the top of another stack. The objective is to retrieve all the blocks, respecting their retrieval priority while performing the minimum number of relocations. Solving this problem is critical in storage systems because it saves operational time and resources. We present two new lower bounds for the number of relocations of an optimal solution. We implemented an iterative deepening A* algorithm using these new proposed lower bounds and other well- known lower bounds from the literature. We performed an extensive set of computational experiments showing that the new lower bounds improve the performance of the exact algorithm, solving to optimality more instances than when using other lower bounds in the same amount of time
Subject: Otimização combinatória
Heurística (Computação)
Problema de realocação de blocos
Language: Inglês
Editor: [s.n.]
Citation: YUCRA QUISPE, Kent Emershon. An exact algorithm for the blocks relocation problem with new lower bounds: Um algoritmo exato para o problema de realocação de blocos usando novos limitantes inferiores. 2018. 1 recurso online (47 p.). Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP.
Date Issue: 2018
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Quispe_KentEmershonYucra_M.pdf979.88 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.