Jochen Rethmann, Hochschule Niederrhein, FB Elektrotechnik und Informatik, Reinarzstraße 49, 47805 Krefeld
An approximation algorithm for stacking up bins from a conveyer onto pallets
WADS 1997 (LNCS 1272, pp. 440-449)
Abstract
| Given a sequence of bins q=(b1, …, bn) and a positive integer p. Each bin is destined for a pallet. We consider the problem to remove step by step all bins from q such that the positions of the bins removed from q are as less as possible and after each removal there are at most p open pallets. (A pallet t is called open if the first bin for t is already removed from q but the last bin for t is still contained in q. If a bin b is removed from q then all bins to the right of b are shifted one position to the left.) |
| The maximal position of the removed bins and the maximal number of open pallets are called the storage capacity and the number of stack-up places, respectively. We introduce an O(n · log(p)) time approximation algorithm that processes each sequence q with a storage capacity of at most smin(q,p) · log2(p+1) bins and p+1 stack-up places, where smin(q,p) is the minimum storage capacity necessary to process q with p stack-up places. |