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)
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. |