On the One-Dimensional Space Allocation Problem

Jean-Claude Picard and Maurice Queyranne
Additional contact information
Jean-Claude Picard: Ecole Polytechnique, Thiès, Sénégal
Maurice Queyranne: University of Houston, Houston, Texas

Operations Research, 1981, vol. 29, issue 2, 371-391

Abstract: 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.

Date: 1981
References: Add references at CitEc
Citations: View citations in EconPapers (30)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.29.2.371 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:29:y:1981:i:2:p:371-391

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().