Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

An exact algorithm for the Blocks Relocation Problem with new lower bounds

Texto completo
Autor(es):
Yucra Quispe, Kent E. [1] ; Lintzmayer, Carla N. [2] ; Xavier, Eduardo C. [1]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
[2] Fed Univ ABC, Ctr Math Computat & Cognit, Santo Andre, SP - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: Computers & Operations Research; v. 99, p. 206-217, NOV 2018.
Citações Web of Science: 3
Resumo

The Blocks Relocation Problem is an important problem in storage systems. An input instance for it consists of a set of blocks distributed in stacks where each block is identified by a retrieval number and each stack has a same maximum height limit. The objective is to retrieve all the blocks respecting their retrieval order and performing the minimum number of relocations. 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. Solving this problem is critical in storage systems because it saves operational time and resources. In this paper, we present two new lower bounds for the number of relocations of an optimal solution. We implemented an exact iterative deepening A{*} algorithm using these new proposed lower bounds and other well-known lower bounds from the literature. We performed several computational experiments to show that the new lower bounds improve the performance of the exact algorithm, solving to optimality more instances than when using other lower bounds when given the same amount of time. (C) 2018 Elsevier Ltd. All rights reserved. (AU)

Processo FAPESP: 16/23552-7 - Problemas de corte e empacotamento: abordagens práticas e teóricas
Beneficiário:Rafael Crivellari Saliba Schouery
Linha de fomento: Auxílio à Pesquisa - Regular
Processo FAPESP: 16/14132-4 - Empacotamentos uni e bidimensionais com restrições de conflitos e remoções
Beneficiário:Carla Negri Lintzmayer
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
Beneficiário:Flávio Keidi Miyazawa
Linha de fomento: Auxílio à Pesquisa - Temático