Asynchronous cooperative local search for the office-space-allocation problem

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.