New Bounds for Office Space Allocation using Tabu Search
Pages 869 - 876
Abstract
The Office Space Allocation problem is a combinatorial optimization problem which focuses into determining the way to assign spaces to entities in order to optimize the use of available space in an organization. This allocation process considers a set of preferences, constraints and requirements. In this paper we propose a metaheuristic approach that includes a construction step and an improvement step, based on Greedy and Tabu Search techniques respectively. Here, we propose a construction method specially designed to deal with the misused space and hard/soft constraints of the problem. Then, Tabu Search performs a fast analysis that allows it to find good quality neighborhoods to analyze. We used an automated tuning method to determine the best parameter values for the entire set of benchmarks. Results show that our approach was able to obtain new lower bounds for seven problem instances.
References
[1]
E. Aarts and J. K. Lenstra, editors. Local Search in Combinatorial Optimization. John Wiley & Sons, Inc., New York, NY, USA, 1st edition, 1997.
[2]
C. O. Benjamin, I. C. Ehie, and Y. Omurtag. Planning Facilities at the University of Missouri-Rolla. Interfaces, 22(4):95--105, 1992.E. Burke, P. Cowling, and J. Landa Silva. Hybrid population-based metaheuristic approaches for the space allocation problem. In 2001 Congress on Evolutionary Computation, pages 232--239, 2001.
[3]
E. Burke and D. Varley. Space allocation: An analysis of higher education requirements. In E. Burke and M. Carter, editors, Practice and Theory of Automated Timetabling II, volume 1408 of LNCS, pages 20--33. Springer Berlin Heidelberg, 1998.
[4]
E. K. Burke, P. I. Cowling, J. D. L. Silva, and B. McCollum. Three Methods to Automate the Space Allocation Process in UK Universities. In Selected papers from the Third International Conference on Practice and Theory of Automated Timetabling III, pages 254--276, London, UK, 2001. Springer-Verlag.
[5]
I. Giannikos, E. El-darzi, and P. Lees. An Integer Goal Programming Model to Allocate Offices to Staff in an Academic Institution. Journal of The Operational Research Society, 46:713--720, 1995.
[6]
D. Landa-Silva and E. K. Burke. Asynchronous Cooperative Local Search for the Office Space Allocation Problem. INFORMS Journal on Computing, 19(4):575--587, 2007.
[7]
J. D. Landa-Silva. Metaheuristics and Multiobjective Approaches for the Space Allocation Problem. phd, School of Computer Science and Information Technology, University of Nottingham, November 2003.
[8]
R. Lopes and D. Girimonte. The Office Space Allocation Problem in Strongly Hierarchized Organizations. In P. Cowling and P. Merz, editors, Evolutionary Computation in Combinatorial Optimization, volume 6022 of LNCS, pages 143--153. Springer Berlin Heidelberg, 2010.
[9]
R. Pereira, K. Cummiskey, and R. Kincaid. Office Space Allocation Optimization. In IEEE Systems and Information Engineering Design Symposium (SIEDS), pages 112--117, 2010.
[10]
M.-C. Riff and E. Montero. A new algorithm for reducing metaheuristic design effort. In 2013 IEEE Congress on Evolutionary Computation (CEC), pages 3283--3290, 2013.
[11]
L. Ritzman, J. Bradford, and R. Jacobs. A Multiple Objective Approach to Space Planning for Academic Facilities. Management Science, 25(9):895--906, 1979.
[12]
O. Ülker and D. Landa-Silva. A 0/1 integer programming model for the office space allocation problem. Electronic Notes in Discrete Mathematics, 36:575--582, 2010.
[13]
O. Ülker and D. Landa-Silva. Designing difficult Office Space Allocation problem instances with Mathematical Programming. In Proceedings of the 10th international conference on Experimental algorithms, pages 280--291, Berlin, Heidelberg, 2011. Springer-Verlag.
[14]
O. Ülker and D. Landa-Silva. Evolutionary localsearch for solving the Office Space Allocation problem. In IEEE Congress on Evolutionary Computation (CEC 2012), pages 1--8, 2012.
Index Terms
- New Bounds for Office Space Allocation using Tabu Search
Recommendations
Improved Tabu search heuristics for the dynamic space allocation problem
The dynamic space allocation problem (DSAP) presented in this paper considers the task of assigning items (resources) to locations during a multi-period planning horizon such that the cost of rearranging the items is minimized. Three tabu search ...
A Tabu-Search Hyperheuristic for Timetabling and Rostering
Hyperheuristics can be defined to be heuristics which choose between heuristics in order to solve a given optimisation problem. The main motivation behind the development of such approaches is the goal of developing automated scheduling methods which ...
An efficient tabu search for solving the uncapacitated single allocation hub location problem
Given an efficient tabu search the uncapacitated single allocation hub location problem.Given some new tabu rules.Given some new theoretical results for computing the changes in the objective function's value for three types of moves.Improved the best ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2016
1196 pages
ISBN:9781450342063
DOI:10.1145/2908812
- Editor:
- Tobias Friedrich,
- General Chair:
- Frank Neumann,
- Program Chair:
- Andrew M. Sutton
Copyright © 2016 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 20 July 2016
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
GECCO '16
Sponsor:
Acceptance Rates
GECCO '16 Paper Acceptance Rate 137 of 381 submissions, 36%;
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 151Total Downloads
- Downloads (Last 12 months)12
- Downloads (Last 6 weeks)0
Reflects downloads up to 08 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in