Circular layout problems in manufacturing systems.

Abstract

We present exact solution procedures for a special discrete layout problem; namely, the Circular Layout Problem (CLP) where the "facilities" are arranged around a simple closed loop path and flows between "facilities" occur only along the loop. Given a flow matrix and a distance matrix, the problem is to assign each "facility" to each predetermined site such that the total "cost" (defined by flows times distances) is minimized. Many practical applications of the CLP, such as arranging workstations around an AGV or conveyor loop, can be found in modern manufacturing systems. The CLP is a special case of the Quadratic Assignment Problem and can be divided into the Unidirectional CLP and the Bidirectional CLP based on whether flow is handled in only one direction (e.g., clockwise) or either direction. The Unidirectional CLP can be further divided into four subproblems based on whether the sites are equally spaced around the loop or not, and whether flow is conserved at each "facility" or not. We present an LP relaxation which optimally solves three of the subproblems. For the fourth subproblem where the sites are arbitrarily spaced and flow is not conserved, by taking advantage of the circularity of the distance matrix, we present a lower bound which is shown to be at least as tight as the Gilmore-Lawler bound. For the general Bidirectional CLP, we present a branch and bound algorithm in which we use a new lower bound developed by exploiting a special structure in the distance matrix. Computational results indicate that our algorithm outperforms the Burkard-Derigs' QAP code as the maximum distance between two adjacent sites increases and/or the problem size increases.