A BRANCH-AND-BOUND METHOD FOR SOLVING THE BIDIRECTIONAL CIRCULAR LAYOUT PROBLEM

In this paper we study a special discrete layout problem, namely the B idirectional circular layout problem (Bi-CLP) where the 'facilities' a re arranged around a simple closed-loop path (with no shortcuts) and f lows between facilities occur either in the clockwise or in the counte rclockwise direction whichever is shorter along the closed-loop path. The Bi-CLP is to assign each facility to one of the predetermined site s such that the total flow times the distance over which the flows occ ur is minimized The Bi-CLP is NP-hard and a special case of the quadra tic assignment problem (QAP). As described in this paper, numerous exi sting 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' b ranching algorithm. Computational results indicate that the Bi-CLP alg orithm outperforms the best algorithm available for general QAPs as th e problem size increases and/or as the maximum distance between two ad jacent sites increases.