A tabu-search heuristic for the dynamic plant layout problem

We consider the dynamic plant layout problem (DPLP) in which the layout of a facility must be determined in each period of a finite planning horizon. We begin by reviewing the literature on DPLP, discussing various formulations of the problem which have appeared in the literature, as well as a number of exact and heuristic solution procedures which have been proposed for DPLP. We then define a tabu-search heuristic (TSH) for DPLP. The TSH employs short-term and longer-term memory features such as the use of an aspiration criterion, dynamic tabu list strategies, and other strategies for search intensification and diversification. Computational experience with the heuristic on a set of test problems appearing in the literature is reported. The TSH is seen to be extremely effective in obtaining high-quality solutions to the test problems. The TSH procedure produces new best-known solutions for over one-third of the test problems.