A tabu search heuristic for the dynamic space allocation problem. (English) Zbl 1114.90160

Summary: The dynamic space allocation problem (DSAP) presented here is a relatively new problem in the literature. It looks at the optimization of space/resource assignments during the implementation of project activities. More specifically, the DSAP assigns project activities and their required resources to workspaces and idle resources to storage spaces with respect to minimizing the sum of the distances the resources travel. In this paper, construction algorithms and a tabu search heuristic are presented for the DSAP, and a set of test problems taken from the literature is used to test the performances of the heuristics. The results show that the proposed tabu search heuristic clearly outperforms the techniques (i.e., simulated annealing heuristics) presented in the literature with respect to solution quality and computation time.


90C59 Approximation methods and heuristics in mathematical programming
90B80 Discrete location and assignment
Full Text: DOI


[1] McKendall, A.R.; Noble, J.S.; Klein, C.M., Simulated annealing heuristics for managing resources during planned outages at electric power plants, Computers & operations research, 32, 1, 107-125, (2005) · Zbl 1076.90029
[2] Gharbi, A.; Pellerin, R.; Villeneuve, L., A new constraint-based approach for overhaul project scheduling with work space constraints, International journal of industrial engineering, 6, 2, 123-131, (1999)
[3] Zouein, P.P.; Tommelein, I.D., Dynamic layout planning using a hybrid incremental solution method, Journal of construction engineering & management, 125, 6, 400-408, (1999)
[4] Rosenblatt, M.J., The dynamics of plant layout, Management science, 32, 1, 76-86, (1986) · Zbl 0589.90024
[5] Koopmans, T.; Beckmann, M., Assignment problems and the location of economic activities, Econometrica, 25, 53-76, (1957) · Zbl 0098.12203
[6] Balakrishnan, J.; Cheng, C.H., Genetic search and the dynamic layout problem, Computers & operations research, 27, 6, 587-593, (2000) · Zbl 0955.90052
[7] Sahni, S.; Gonzalez, T., P-complete approximation problems, Journal of the association of computer machinery, 23, 555-565, (1976) · Zbl 0348.90152
[8] Glover, F., Future paths for integer programming and links to artificial intelligence, Computers & operations research, 1, 3, 533-549, (1986) · Zbl 0615.90083
[9] Skorin-Kapov, J., Tabu search applied to the quadratic assignment problem, ORSA J on computing, 2, 33-45, (1990) · Zbl 0752.90054
[10] Skorin-Kapov, J., Extensions of a tabu search adaptation to the quadratic assignment problem, Computers & operations research, 21, 8, 855-865, (1994) · Zbl 0812.90098
[11] Chiang, W.-C.; Kouvelis, P., An improved tabu search heuristic for solving facility layout design problems, International journal of production research, 34, 9, 2565-2585, (1996) · Zbl 0929.90019
[12] Chiang, W.-C.; Chiang, C., Intelligent local search strategies for solving facility layout problems with the quadratic assignment problem formulation, European journal of operations research, 106, 457-488, (1998) · Zbl 0991.90127
[13] Kaku, B.K.; Mazzola, J.B., A tabu-search heuristic for the dynamic plant layout problem, INFORMS journal on computing, 9, 4, 374-384, (1997) · Zbl 0901.90150
[14] Chan, H.M.; Milner, D.A., Direct clustering algorithm for group formation in cellular manufacture, Journal of manufacturing systems, 1, 65-75, (1982)
[15] Tompkins JA, White JA, Bozer YA, Frazelle EH, Tanchoco JMA, Trevino J. Facilities planning. New York: Wiley, 1996. p. 418-34.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.