Graph theoretic heuristics for the plant layout problem
作者:
L. R. FOULDS,
D. F. ROBINSON,
期刊:
International Journal of Production Research
(Taylor Available online 1978)
卷期:
Volume 16,
issue 1
页码: 27-37
ISSN:0020-7543
年代: 1978
DOI:10.1080/00207547808929997
出版商: Taylor & Francis Group
数据来源: Taylor
摘要:
The plant layout problem is an important industrial problem that remains unsolved. Seppanen and Moore considered an important subproblem: that of the optimal specification of which facilities are to be adjacent in the final layout without regard to the area or shape of the individual facilities. They present a string processing heuristic which relies on using a test for graph planarity. This paper further develops their graph theoretic formulation of the problem. This development is used to present two procedures which usually yield near-optimal solutions. The procedures circumvent the considerable difficulty of graph planarity testing by working entirely within a family of graphs known to be planar and also to contain the solution. Ways of improving suboptimal solutions are discussed. Computational experience in using the methods on a variety of problems suggests that the methods are efficient.
点击下载:
PDF (375KB)
返 回