One-Dimensional Space Allocation: An Ordering Algorithm

The space-allocation problem arises when an architect tries to arrange rooms of fixed area but unspecified shape on a floor plan in such a way as to minimize a given linear combination of the distances between all pairs of rooms. In one dimension, this is the problem of ordering line segments along a simple axis or rooms along one side of a corridor. This paper devises an efficient branch-and-bound algorithm for finding the optimal ordering, and shows that the algorithm can solve one special type of facilities-to-locations assignment problem. Space allocation in two dimensions is also discussed briefly.