Jochen Rethmann, Hochschule Niederrhein, FB Elektrotechnik und Informatik, Reinarzstraße 49, 47805 Krefeld


Competitive Analysis of on-line Stack-Up Algorithms
ESA 1997 (LNCS 1284, pp. 402-415)

J. Rethmann
E. Wanke

Abstract

Let q=(b1, …, bn) be a sequence of bins. Each bin is destined for some pallet t. For two given integers s and p, the stack-up problem is to move step by step all bins from q onto their pallets such that the position of the bin moved from q is always not greater than s and after each step there are at most p pallets for which the first bin is already stacked up but the last bin is still missing. If a bin b is moved from q then all bins to the right of b are shifted one position to the left.
We determine the performance of four simple on-line algorithms called First-In, First-Done, Most-Frequently, and Greedy with respect to an optimal off-line solution for the stack-up problem.

postscript pdf