Jochen Rethmann, Hochschule Niederrhein, FB Elektrotechnik und Informatik, Reinarzstraße 49, 47805 Krefeld
Stack-up algorithms for palletizing at delivery industry
EJOR 128(1): 74-97, 2001
Abstract
| We study the multi-objective combinatorial stack-up problem originally arising in delivery industry. Given a sequence q of labeled bins and two positive integers s and p. The goal is to stack-up the bins by iteratively removing one of the first s bins of the sequence and put it to one of the p stack-up places. Each of these places has to contain bins of only one label, bins of different labels have to be placed on different places. If all bins of a label are removed from q, the corresponding place becomes available for bins of another label. |
| On-line algorithms do not see the whole sequence but at each intermediate step only the first s bins. Moreover, they also know whether any bin they see is the last one for its destination. The Most-Frequently algorithm removes the first bin of some label for which there are the most bins on the first s positions. We show that the Most-Frequently algorithm is (2,2)-competitive and has optimal worst-case on-line performance. |
| Key words: on-line algorithms, competitive analysis, lower bounds, complexity, approximation, control |