Improved tabu search heuristics for the dynamic space allocation problem. (English) Zbl 1278.90474

Summary: 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 heuristics are presented for this problem. The first heuristic is a simple basic tabu search heuristic. The second heuristic adds diversification and intensification strategies to the first, and the third heuristic is a probabilistic tabu search heuristic. To test the performances of the heuristics, a set of test problems from the literature is used in the analysis. The results show that the tabu search heuristics are efficient techniques for solving the DSAP. More importantly, the proposed tabu search heuristic with diversification/intensification strategies found new best solutions using less computation time for one-half of all the test problems.


90C59 Approximation methods and heuristics in mathematical programming


Tabu search
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] McKendall, A. R.; Jaramillo, J. R., A tabu search heuristic for the dynamic space allocation problem, Computers & Operations Research, 33, 3, 768-789 (2006) · Zbl 1114.90160
[3] Patterson, J. H.; Huber, W. D., A horizon-varying zero-one approach to project scheduling, Management Science, 20, 6, 990-998 (1974) · Zbl 0303.90026
[4] Koopmans, T.; Beckmann, M., Assignment problems and the location of economic activities, Econometrica, 25, 53-76 (1957) · Zbl 0098.12203
[5] Rosenblatt, M. J., The dynamics of plant layout, Management Science, 32, 1, 76-86 (1986) · Zbl 0589.90024
[7] 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)
[8] Zouein, P. P.; Tommelein, I. D., Dynamic layout planning using a hybrid incremental solution method, Journal of Construction Engineering and Management, 125, 6, 400-408 (1999)
[9] Glover, F., Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, 1, 3, 533-549 (1986) · Zbl 0615.90083
[10] Skorin-Kapov, J., Tabu search applied to the quadratic assignment problem, ORSA Journal on Computing, 2, 33-45 (1990) · Zbl 0752.90054
[11] Taillard, E., Robust taboo search for the quadratic assignment problem, Parallel Computing, 17, 443-455 (1991)
[12] Battiti, R.; Tecchiolli, G., The reactive tabu search, ORSA Journal on Computing, 6, 126-140 (1994) · Zbl 0807.90094
[13] 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
[14] 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
[15] Chiang, W-C.; Chiang, C., Intelligent local search strategies for solving facility layout problems with the quadratic assignment problem formulation, European Journal of Operational Research, 106, 457-488 (1998) · Zbl 0991.90127
[16] 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
[17] Osman, I. H., Heuristics for the generalized assignment problem: simulated annealing and tabu search approaches, OR Spektrum, 17, 211-225 (1995) · Zbl 0841.90098
[18] Laguna, M.; Kelly, J. P.; Gonzalez-Velarde, J. L.; Glover, F., Tabu search for the multilevel generalized assignment problem, European Journal of Operational Research, 82, 176-189 (1995) · Zbl 0905.90122
[19] Diaz, J. A.; Fernandez, E., A tabu search heuristic for the generalized assignment problem, European Journal of Operational Research, 132, 22-38 (2001) · Zbl 0980.90045
[20] Higgins, A. J., A dynamic tabu search for large-scale generalized assignment problems, Computers & Operations Research, 28, 1039-1048 (2001) · Zbl 1017.90089
[21] Lim, A.; Rodrigues, B.; Xiao, F.; Zhu, Y., Crane scheduling with spatial constraints, Naval Research Logistics, 51, 386-406 (2004) · Zbl 1054.90036
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.