The classical storage assignment problem assumes that each item located in the storage cannot be moved to another location until it is retrieved. Recently a model was proposed that the item can be moved to another location in the storage in order to minimize seek time, server path, etc. This kind of allocation method is called storage rearrangement problem.
In this thesis, we present the stack rearrangement problem.This problem is a kind of storage rearrangement problem which uses stack as the storage. Items are represented by stored time, retrieved time, and weight. A feasible algorithm pushes each item into stack at its stored time, and pops the items out on a pallet at its retrieved time. The goal is to minimize the total weight of items that is pushed/popped.
We state several properties of stack rearrangement problem. For a given stack, we give an algorithm which pops the entire stack properly with the minimum cost. Then we present an O(log n)-competitive online algorithm for this problem.
