A note on "An exact algorithm for the blocks relocation problem with new lower bounds". (December 2020)

• Record Type: Journal Article
• Authors: Jin, Bo
• Is Part Of: Computers & operations research. Volume 124(2020)
• Publication Date: 2020-12
• Subjects: Combinatorial optimization -- Blocks relocation problem -- Lower bound; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.105082
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A lower bound called LB-LIS for the blocks relocation problem is discussed. The algorithm description of the LB-LIS lower bound is amended. A faster algorithm for computing the LB-LIS lower bound is proposed. The proposed algorithm takes 44.48% less computational time than the original algorithm for the instances tested. Abstract: This paper is a note on [Quispe, K. E. Y., Lintzmayer, C. N., & Xavier, E. C. (2018). An exact algorithm for the blocks relocation problem with new lower bounds. Computers & Operations Research, 99, 206–217]. Quispe et al. (2018) presented a new lower bound called LB-LIS for the blocks relocation problem. In this note, we show that the algorithm description of LB-LIS in the referred paper is incomplete. In addition, we propose a faster algorithm for computing this lower bound more efficiently. Computational experiments on a commonly used dataset reveal that the proposed algorithm uses on average 44.48% less time than the original LB-LIS implementation for the instances tested.