Quadratic assignment algorithms for the dynamic layout problem

Abstract

In a dynamic facilities layout problem, the objective is to minimize total costs: the flow costs over a series of discrete time periods plus the rearrangement costs of changing layouts between time periods. By assuming unit department sizes, the problem is modelled as a modified quadratic assignment problem. Five algorithms are modified to include the dynamic aspects. A cutting plane algorithm found the best solutions to a series of realistic test problems, outperforming exchange, branch and bound, dynamic programming and cut tree algorithms. It was able to solve a 30-location 5-time-period problem in 200 CPU seconds.