Average case analysis of Blocks Relocation heuristics

We consider the Blocks Relocation Problem (BRP) where some blocks stored in stacks have to be removed and where the order in which the blocks are to be removed is given in advance. We are only allowed to remove a block on top of a stack or to relocate a block from the top of a stack to the top of another stack. The objective is to remove the blocks using a minimum number of relocations. We present a simple BRP heuristic similar to a heuristic presented by Caserta and Voß. Under certain assumptions on the stack capacity and the initial stack height, we formally show that the heuristic produces high quality solutions with high probability for large BRP instances. For any positive numbers Ε1 and Ε2 we show how the heuristic – under the assumptions mentioned above – can be used to construct a polynomial time algorithm that for any n solves a fraction of 1−Ε1 of all BRP instances of size n using no more than 1 +Ε2 times the optimal number of relocations. © 2014 Springer International Publishing Switzerland.