Asynchronous Cooperative Local Search for the Office-Space-Allocation Problem

INFORMS Journal on Computing · 2007 · Volume 19 · Issue 4

Abstract

We investigate cooperative local search to improve upon known results of the office-space-allocation problem in universities and other organizations. A number of entities (e.g., research students, staff, etc.) must be allocated into a set of rooms so that the physical space is utilized as efficiently as possible while satisfying a number of hard and soft constraints. We develop an asynchronous cooperative local search approach in which a population of local search threads cooperate asynchronously to find better solutions. The approach incorporates a cooperation mechanism in which a pool of genes (parts of solutions) is shared to improve the global search strategy. Our implementation is single-processor and we show that asynchronous cooperative search is also advantageous in this case. We illustrate this by extending four single-solution metaheuristics (hill-climbing, simulated annealing, tabu search, and a hybrid metaheuristic) to population-based variants using our asynchronous cooperative mechanism. In each case, the population-based approach performs better than the single-solution one using comparable computation time. The asynchronous cooperative metaheuristics developed here improve upon known results for a number of test instances.

Keywords

artificial intelligence, heuristics, approximation algorithms, office-space-allocation

Enable JavaScript for citation tools and additional paper interactions.