Previous Issues
Volume :11 Issue : 2 2004
Add To Cart
Download
Facility Design Problem: A Graph Theoretical Approach
Auther : Merza H. Hasan
The facility layout problem is formulated in terms of a graph theoretical approach. The solution attempts to find a sub-graph from a given weighted complete graph such that the sub-graph is planar and can be embedded on the plane without any arc intersecting. It is weighted maximal, no additional arc can be added to the sub-graph without destroying its planarity and it has the highest sum of arc weights. In this paper a new 0-1 integer programming formulation will be introduced and its variants discussed for the facility design problem using structural graph-theoretic properties. Bounding procedures, based on Linear Programming (LP) relaxation, will be presented. Moreover, a branch-and-bound heuristic algorithm will be implemented using the LP bound and a tree search method based on a set of three branching rules. The effects of the different branching rules on the quality of the LP bounds will be investigated after which the best tree-search implementation will be identified. Computational results show that optimal or near optimal solutions can be obtained for practical size problems.