Graph theoretic techniques for facilities layout. (1984)
Type of ContentElectronic Thesis or Dissertation
Thesis DisciplineOperations Research
Degree NameDoctor of Philosophy
PublisherUniversity of Canterbury
AuthorsGiffin, J.W.show all
In this thesis we consider a two-phase graph theoretic approach to designing the layout of a system of physical facilities. Heuristic techniques are required because the complexity of the problem gives little hope for optimization. The initial phase involves determining the relative spatial adjacency of facilities in the plane. Several new formulations are developed. The basic method of maximizing the sum of pairwise adjacency scores is extended to account for near adjacency. Facility areas are then included using the more realistic objective of minimizing total transportation cost in the layout under an approximation to rectilinear travel. Considerable computational experience is given.
The ultimate aim of facilities design is the production of a scale block plan - the second phase. We present a method for systematically producing such a plan for a restricted class of adjacency graphs that is concise enough to be implemented on a microcomputer. Proposed modifications to this rationale are then outlined in the context of multifloor layout.
Efficiency is an important criterion throughout the work. Our methods use a constructional, rather than the more common improvement, rationale, and hence advantage may be taken of this updating nature. We introduce several updating schemes in order to make promising techniques tractible on problems of practical size. Included is a modified methodology for general graph planarity testing in an updating framework.
Graph theory offers a flexible modelling base within which we may readily encapsulate many formulation alternatives. We feel that this thesis contains an important contribution in providing methods which give high quality solutions to problems unsolvable by other means in reasonable computing time. Also, out of this work are spawned several suggestions for worthwhile further development and implementation.