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

Landa-Silva, Dario; Burke, Dmund K.

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. © 2007 INFORMS.

Citation

Landa-Silva, D., & Burke, D. K. (2007). Asynchronous cooperative local search for the office-space-allocation problem. INFORMS Journal on Computing, 19(4), 575-587. https://doi.org/10.1287/ijoc.1060.0200

• Journal Article Type: Article
• Acceptance Date: Jul 1, 2006
• Online Publication Date: Nov 1, 2007
• Publication Date: Oct 1, 2007
• Deposit Date: Feb 10, 2020
• Journal: INFORMS Journal on Computing
• Print ISSN: 1091-9856
• Electronic ISSN: 1526-5528
• Publisher: INFORMS
• Peer Reviewed: Peer Reviewed
• Volume: 19
• Issue: 4
• Pages: 575-587
• DOI: https://doi.org/10.1287/ijoc.1060.0200
• Public URL: https://nottingham-repository.worktribe.com/output/3088181
• Publisher URL: https://pubsonline.informs.org/doi/10.1287/ijoc.1060.0200