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

被引:19
作者
Bozer, YA [1 ]
Rim, SC [1 ]
机构
[1] AJOU UNIV, DEPT IND ENGN, SUWON, SOUTH KOREA
基金
美国国家科学基金会;
关键词
facility layout; circular layout problem; generalized linear ordering problem; manufacturing systems; quadratic assignment problem;
D O I
10.1016/0307-904X(95)00124-3
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
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.
引用
收藏
页码:342 / 351
页数:10
相关论文
共 17 条
[1]   OPTIMAL LINEAR ORDERING [J].
ADOLPHSON, D ;
HU, TC .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1973, 25 (03) :403-423
[2]  
AFENTAKIS P, 1989, INT J FLEX MANUF SYS, V1, P175, DOI DOI 10.1007/BF00223021
[3]   DECENTRALIZED CONTROL OF AUTOMATED GUIDED VEHICLES ON A SIMPLE LOOP [J].
BARTHOLDI, JJ ;
PLATZMAN, LK .
IIE TRANSACTIONS, 1989, 21 (01) :76-81
[4]   TANDEM AGV SYSTEMS - A PARTITIONING ALGORITHM AND PERFORMANCE COMPARISON WITH CONVENTIONAL AGV SYSTEMS [J].
BOZER, YA ;
SRINIVASAN, MM .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1992, 63 (02) :173-191
[5]   TANDEM CONFIGURATIONS FOR AUTOMATED GUIDED VEHICLE SYSTEMS AND THE ANALYSIS OF SINGLE VEHICLE LOOPS [J].
BOZER, YA ;
SRINIVASAN, MM .
IIE TRANSACTIONS, 1991, 23 (01) :72-82
[6]  
BOZER YA, 8933 U MICH DEP IND
[7]  
BURKARD RE, 1980, LECT NOTES EC MATH S, V184
[8]  
Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1
[9]   MACHINE LAYOUT PROBLEM IN FLEXIBLE MANUFACTURING SYSTEMS [J].
HERAGU, SS ;
KUSIAK, A .
OPERATIONS RESEARCH, 1988, 36 (02) :258-268
[10]  
KIRAN AS, 8911 U SO CAL DEP IS