A branch and bound algorithm for locating input and output points of departments on the block layout |
| |
Authors: | J-G Kim Y-D Kim |
| |
Affiliation: | 1.Korea Advanced Institute of Science and Technology,Korea |
| |
Abstract: | We consider the problem of locating input and output (I/O) points of each department for a given layout. The objective of the problem is to minimise the total distance of material flows between the I/O points. Here, distances between the I/O points are computed as the lengths of the shortest path (not the rectilinear distances) between the I/O points. We developed a procedure to eliminate dominated candidate positions of I/O points that do not need to be considered. With this procedure, a large number of dominated candidate positions can be eliminated. A linear programming (LP) model for minimising the total rectilinear distance of flows is used to obtain a lower bound. Using the elimination procedure and the LP model, a branch and bound algorithm is developed to find an optimal location of the I/O points. Results from computational experiments show that the suggested algorithm finds optimal solutions in a very short time even for large-sized problems. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|