A branch and bound method for solving the bidirectional circular layout problem

In this paper we study a special discrete layout problem, namely the Bidirectional circular layout problem (Bi-CLP) where the 'facilities' are arranged around a simple closed-loop path (with no shortcuts) and flows between facilities occur either in the clockwise or in the counterclockwise direction whichever is shorter along the closed-loop path. The Bi-CLP is to assign each facility to one of the predetermined sites such that the total flow times the distance over which the flows occur is minimized The Bi-CLP is NP-hard and a special case of the quadratic assignment problem (QAP). As described in this paper, numerous existing and potential applications of the Bi-CLP can be found in modern manufacturing systems. We present an exact solution procedure for the Bi-CLP based on a new bounding scheme we used within a 'traditional' branching algorithm. Computational results indicate that the Bi-CLP algorithm outperforms the best algorithm available for general QAPs as the problem size increases and/or as the maximum distance between two adjacent sites increases.