Two new heuristic algorithms for the maximal planar layout problem

被引：3

作者：

Merker J. ^{[1
]}

Wäscher G. ^{[2
]}

机构：

[1] Institut für Wirtschaftswissenschaften, Technische Universität Braunschweig

[2] Wirtschaftswissenschaftliche Fakultät, Betriebswirtschaftslehre - Produktion und Logistik, Martin-Luther-Universität Halle-Wittenberg

来源：

Operations-Research-Spektrum | 1997年 / 19卷 / 2期

关键词：

Facility layout planning; Heuristics; Numerical experiments; Planar graphs;

D O I：

10.1007/BF01545513

中图分类号：

学科分类号：

摘要：

The adjacency problem is an important sub-problem in facility layout planning. It is known to be NP-complete, so heuristics are required to solve "large" problem instances. In this paper two new heuristics for the adjacency problem are introduced which belong to a special class of constructive methods called Triangulation Expansion Heuristics. Extensive numerical experiments have been carried out in order to evaluate the proposed methods in terms of computing times and solution quality. It has been found that at least one method is clearly superior to the best methods proposed in the literature so far (Eades et al. 1982, Leung 1992). © Springer-Verlag 1997.

引用

页码：131 / 137

页数：6

共 20 条

[1]

Al-Hakim L.A., Two Graph-Theoretic Procedures for an Improved Solution to the Facilities Layout Problem, International Journal of Production Research, 29, pp. 1701-1718, (1991)

[2]

Boswell S.G., TESSA - A New Greedy Heuristic for the Facility Layout Planning, International Journal of Production Research, 30, pp. 1957-1968, (1992)

[3]

Domschke W., Drexl A., Location and Layout Planning: An International Bibliography, (1985)

[4]

Domschke W., Drexl A., Logistik: Standorte. 4th Ed., (1996)

[5]

Eades P., Foulds L.R., Giffin J.W., An Efficient Heuristic of Identifying a Maximum Weight Planar Subgraph, Combinatorial Mathematics IX, pp. 239-251, (1982)

[6]

Foulds L.R., Gibbons P.B., Giffin J.W., Facilities Layout Adjacency Determination: An Experimental Comparison of Three Graph Theoretic Heuristics, Operations Research, 33, pp. 1091-1106, (1985)

[7]

Foulds L.R., Robinson D.F., Graph Theoretic Heuristics for the Plant Location Problem, International Journal of Production Research, 16, pp. 27-37, (1978)

[8]

Giffin J.W., Graph Theoretic Techniques for Facilities Layout, (1984)

[9]

Giffin J.W., Foulds L.R., Cameron D.C., Drawing a Block Plan from a REL-Chart with Graph Theory and a Microcomputer, Computers and Industrial Engineering, 10, pp. 109-115, (1986)

[10]

Glover F., Pesch E., Efficient Facility Layout Planning, Working Paper, (1994)

← 1 2 →