Graph theoretic facility layout design and evaluation : theoretical and practical considerations : a thesis presented in partial fulfilment of the requirements for the degree of Ph.D. in Operations Research at Massey University
Loading...
Date
1996
DOI
Open Access Location
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Massey University
Rights
The Author
Abstract
In this thesis we examine the Graph Theoretic Facility Layout Problem (GTFLP). The GTFLP is concerned with designing a building layout, with a specified number of facilities, with data relating to the facilities' areas, and proximity desirability ratings or material flows between the facilities. The objective is to design an efficient layout which incorporates these issues, by attempting to minimise the transportation cost of material flow between facilities, or maximise the desirability ratings, and designing regularly shaped facilities which allow effectiveness of the layout. The GTFLP proceeds as a two phase process; the first generates a highly weighted (maximal) planar graph, called an adjacency graph, which specifies the relative spatial location of each facility, with respect to its adjacent facilities. This phase has been extensively studied, and although not a focus of this thesis, we address adjacency graph generation and provide a worst case analysis of the so-called TESSA method. The main thrust of this thesis addresses the second phase of the GTFLP, where we examine the construction of the layout in light of the information given by the first phase. We review previous literature in this area, and extend this work by a series of enhancements to existing methods, and introduction of new techniques including: introducing the Vertex Splitting Algorithm, the Tiling Algorithm, and the SIMPLE Algorithm; analysis of previous methods, by completing the theory of the Deltahedron and Contraction Layout Algorithms for instance. Initial steps in characterising adjacency graphs, which by their structure allow the easy construction of a corresponding layout, is introduced, by providing a series of template layouts; furthermore we compare and contrast algorithms which force an overlying grid structure against those more generic methods, which do not impose this rigidity; and introduce some simple procedures for improving the regularity of a layout. We formally define the concept of regularity, by presenting a series of quantifiable measures, which can be calculated to give an evaluation of the effectiveness of a layout. Thereby we attempt to quantifiably compare and rank the layout generation methods, by evaluating the regularity measures over a set of test problems. The effects of the various layout improvements, and initialisation processes will be shown within this computational process. We also examine the incorporation of a Material Handling System (MHS) within a layout. The calculation of the transportation costs involved in the implementation of each layout, via the Material Handling System, provides another mechanism for ranking the layout algorithms. Directions for future work are provided in the area of the Material Handling System. Indeed our work in this area only highlighted the importance of modelling this concept. The final contribution of this thesis is the generation of a framework which attempts to look beyond the more theoretical GTFLP model. By invoking a three phase process, which allows the decomposition of the adjacency graph, interaction with a decision planner, and the ability to perturb the problem constraints, we can produce a range of alternative layout scenarios, since there is no right answer to this second phase, and indeed an infinite number of different layouts satisfy the problem constraints. This allows the design process to be directed in a more meaningful way, by exploiting structure within the adjacency graph and the working knowledge of a decision planner, providing a basis whereby the GTFLP can be effectively used within any building design process. We conclude that the GTFLP model is an important concept within the more general Facility Layout Problem. We provide evidence that the standard Graph Theoretic model is perhaps overly restrictive. Indeed we shall see that the generation of a good adjacency graph does not in general correspond to obtaining a practical layout. With this in mind, we have identified the strengths and weaknesses of the various concepts and ideas used within Graph Theoretic Facility Layout Design, and consequently have created an integration of the adjacency graph and layout phases of this problem. This has provided a unification of the GTFLP into a more malleable form, which provides enough flexibility to accurately model the mechanics behind the design process.
Description
Keywords
Building layout design, Facility layout, Algorithms, Graph Theoretic Facility Layout Design