On the One-Dimensional Space Allocation Problem

The One-Dimensional Space Allocation Problem (ODSAP) arises when locating rooms along a corridor, when setting books on a shelf, when allocating information items among the “cylinders” of a magnetic disk, or when storing products in certain warehouses. The rooms (objects) to be located have a known length (or width) and, for each pair of rooms, there is a given number of “trips” between them; the problem is to find a sequencing of the rooms which minimizes the total traveled distance. This paper deals first with two particular cases. In the rooted tree case, previous results obtained by Adolphson and T. C. Hu for the Linear Ordering Problem are extended and provide efficient solution methods. In addition, it is shown that most of the assumptions made by Adolphson and Hu are necessary, since relaxing any of them leads to an NP-complete problem. In the case of independent destinations (solved by Bergmans and Pratt when all lengths are equal), a unimodality property is shown for an optimum solution, but this is not sufficient to lead to a “good” algorithm and the problem is shown to be NP-complete. For the general problem, an exact algorithm using dynamic programming is described and computationally tested.