MODIFICATIONS TO THE SYSTEMATIC LAYOUT PLANNING PROCEDURE TO ALLOW DEPARTMENTAL DIVISION AND IRREGULARLY SHAPED SUBDEPARTMENTS
A thesis presented to
the faculty of the Fritz J. and Dolores H. Russ College of Engineering and Technology of Ohio University
in partial fulfillment of the requirements for the degree Master of Science
Stephen E. Martin August 2004
This thesis entitled MODIFICATIONS TO THE SYSTEMATIC LAYOUT PLANNING PROCEDURE TO ALLOW DEPARTMENTAL DIVISION AND IRREGULARLY SHAPED SUBDEPARTMENTS
BY STEPHEN E. MARTIN
has been approved for the Department of Industrial and Manufacturing Systems Engineering and the Russ College of Engineering and Technology
Trevor S. Hale Assistant Professor of Industrial and Manufacturing Systems Engineering
Dennis Irwin Dean, Fritz J. and Dolores H. Russ College of Engineering and Technology
MARTIN, STEPHEN E. M.S. August 2004. Industrial Engineering Modifications to the Systematic Layout Planning Procedure to Allow Departmental Division and Irregularly Shaped Subdepartments (133 pp.) Director of Thesis: Trevor S. Hale
The purpose of this research is to develop extensions and enhancements to Systematic Layout Planning (SLP) that allow more complex problems to be addressed during new facility layout construction. Specifically, the modified SLP technique allows for departments to be separated into subdepartments that may or may not necessitate placement beside other subdepartments of the same department. This scenario was previously unable to be addressed by traditional SLP. Also, the alternate subdepartment unit shapes of triangles and hexagons are tested against squares for their effect on the quality of the layout. Finally, new relationship variables, “viscosity” and “affinity” are defined to describe the intradepartmental and interdepartmental attraction, respectively. Layouts produced using the modified SLP technique are compared to those produced using traditional SLP on the basis of lowest cost and are computed using a tool created in Microsoft Excel. The modified SLP procedure produces layouts of statistically equal or lower cost than traditional SLP for the experimental data set.
Approved: Trevor S. Hale Assistant Professor of Industrial and Manufacturing Systems Engineering
4 TABLE OF CONTENTS Abstract ............................................................................................................................... 3 List of Tables ...................................................................................................................... 5 List of Figures ..................................................................................................................... 6 1
Introduction................................................................................................................. 7 1.1 Background ......................................................................................................... 7 1.2 Research Purpose ................................................................................................ 8 1.3 Specific Aims of Research.................................................................................. 9 1.4 Thesis Organization .......................................................................................... 10
2
Literature Review...................................................................................................... 11 2.1 Classification of the Facility Layout Problem .................................................. 11 2.2 Solution Algorithms.......................................................................................... 13 2.3 Graph Theoretic Approaches ............................................................................ 20
3
Formulation............................................................................................................... 23 3.1 Introduction....................................................................................................... 23 3.2 Problem Definition............................................................................................ 25 3.3 Assigning Viscosity and Affinity Values ......................................................... 26 3.4 Objective Function............................................................................................ 27 3.5 Experimental Details......................................................................................... 35 3.6 A Note on Layout Development from Results ................................................. 40
4
Results....................................................................................................................... 43 4.1 Implementation ................................................................................................. 43 4.2 Layout Generation ............................................................................................ 43 4.3 Experimental Results and Analysis .................................................................. 45 4.4 Problem Size ..................................................................................................... 54
5
Conclusions............................................................................................................... 58 5.1 Review of Results ............................................................................................. 58 5.2 Application........................................................................................................ 59 5.3 Future Work ...................................................................................................... 60
References......................................................................................................................... 61 Appendix A: Step by Step Layout Generation Using Modified SLP ............................... 64 Appendix B: Experimental Data..................................................................................... 129
5 LIST OF TABLES Table 3.1: Differences between SLP and Modified SLP.................................................. 25 Table 3.2: Insertion Method Example Data...................................................................... 28 Table 4.1: Layout Cost Results......................................................................................... 46 Table 4.2: Calculated T and P Values for Shapes and Insertion Methods........................ 52 Table 4.3: Calculated T and P Values for Shape/Insertion Method Combinations .......... 53 Table 4.4: Cost Results for Each Problem Size ................................................................ 55 Table 4.5: T and P values for Problems of Different Sizes .............................................. 55
6 LIST OF FIGURES Figure 2.1: Facility Layout Problem Hierarchy................................................................ 12 Figure 2.2: The Steps of SLP............................................................................................ 14 Figure 3.1: Blank Facility Grid......................................................................................... 29 Figure 3.2: Placement of First Subdepartment ................................................................. 30 Figure 3.3: Four-way Tie .................................................................................................. 31 Figure 3.4: Placement of Third Subdepartment................................................................ 32 Figure 3.5: Placement of Next Department ...................................................................... 32 Figure 3.6: Calculations for Placement of Final Department ........................................... 33 Figure 3.7: Addition of a New Column to the Facility Grid............................................. 34 Figure 3.8: Space Relationship Diagram Developed by Modified SLP ........................... 34 Figure 3.9: Triangular Tessellation (Weisstein [23])........................................................ 36 Figure 3.10: Hexagonal Tessellation (Weisstein [22]) ..................................................... 36 Figure 3.11: Example Layout Generated Using Modified SLP........................................ 41 Figure 3.12: Resultant Facility Grid After Manipulation ................................................. 42 Figure 4.1: Traditional SLP Layout .................................................................................. 44 Figure 4.2: Modified SLP Layout..................................................................................... 44 Figure 4.3: Viscosity Ranked Cost Chart ......................................................................... 47 Figure 4.4: Affinity Ranked Cost Chart............................................................................ 48 Figure 4.5: Sum Ranked and SLP Cost Chart .................................................................. 49 Figure 4.6: Average Costs of Shape/Insertion Method..................................................... 50 Figure 4.7: Average Number of Departmental Separations per Problem......................... 56
7 1
INTRODUCTION
1.1 Background The facility layout problem (FLP) has historically had many different applications varying greatly in approach, scale, and type. The vast nature of the FLP has prompted much research on solution algorithms, heuristics, and measures aimed to find good layouts. FLP solution methods are generally categorized according to the type of problem being solved and their approach to the solution: improvement techniques for existing (brown-field) problems and construction techniques for new facility (green-field) problems. Construction layout techniques offer analysis for new facilities while improvement techniques analyze an existing facility. Also, methods generally take either a qualitative or quantitative approach where either intuition or mathematical analysis, respectively, is applied to produce a good layout. Although the currently available algorithms are very different, all methods rely on human decision making to generate good layouts. A particular cornerstone in the facility layout research is the Systematic Layout Planning (SLP) procedure created by Muther [18]. SLP is a comprehensive technique to address the facility layout problem from conception to completion while delineating all necessary steps in between. The fundamental purpose of SLP is to utilize interdepartmental relationships (or flow weights) to generate a two-dimensional unit square block layout. The value of SLP is seen in the simplicity of both the data to be collected and the algorithm itself. The drawbacks of SLP also involve its simplicity, as it typically is only able to address non-complex problems. Also, layouts generated by SLP are
8 sometimes over simplified and require user manipulation to produce application-specific layouts. For these reasons, SLP is often the starting point when generating solutions to the FLP, but not the ending point of final layout generation.
1.2 Research Purpose SLP considers all departments to have an adjacency constraint and sometimes shape constraints that require an entire department to be contained within a rectangular border in only one location of a facility. In specific cases where these constraints do not apply, SLP produces a layout which may be more costly then necessary. For instance, a facility may exist where there are several individual process stations. Some processes because of similar flow weights and relationships may have been grouped together into departments. Since these processes do not necessarily require placement near each other and are considered to have no binding shape constraints, they could be evaluated as individual departments. However, since they do share similar properties, it is less complex to evaluate them as individual units of the same department instead of computing the layout for each process as an individual department. SLP generally suggests the use of unit squares as subdepartment shapes due to the fact that they produce simple and feasible department shapes that can fit within a rectangular facility. However, since the above scenario denotes that there are no departmental shape or adjacency constraints, other shapes can therefore be tested for their effect on the quality of the layout. Specifically, regular (used in the strict mathematical sense meaning both equilateral and equiangular) triangles and hexagons may produce
9 different results due to their different number of sides and subsequently different number of possible adjacent subdepartments. The purpose of this research is to develop extensions and enhancements to SLP that will allow more complex problems to be addressed during new facility layout construction. Specifically, the modified SLP technique will allow for departments to be separated into subdepartments that may or may not necessitate placement beside other subdepartments of the same department. While the separation into subdepartments has been addressed before by Kusiak and Heragu [13] and Liao [14], research by Bozer and Meller [4] suggests that segregation into subdepartments creates a resultant quadratic assignment problem that is too complex to solve. However, the algorithm proposed herein allows a relaxed adherence the adjacency constraint and departmental shape factors that are traditionally mandatory during FLP calculations, therefore simplifying the problem.
1.3 Specific Aims of Research In order to create a modified SLP procedure that can be applied to a new problem set, research must be done to test the proposed steps of the algorithm for their effectiveness. The specific aims of the research are as follows. 1. To test the effect of incremental department placement while using an attraction factor in place of adjacency constraints on the quality of the layout. 2. To evaluate alternate subdepartment unit shapes such as triangles and hexagons based upon the performance objective.
10 3. To test separate insertion algorithms for their sensitivity to the incremental departmental placement and their effect on the quality of layout. 4. To combine the subdepartmental shape and attraction factors into a modified version of the graph based layout portion of SLP that will allow for greater flexibility in solving the FLP.
1.4 Thesis Organization This thesis is organized as follows: Chapter 2 presents a review of the literature in the field of facility layout and a hierarchical structure showing the relevance of the modified SLP procedure to the facility layout problem. Chapter 3 presents the formulation of the modified SLP procedure and explains the calculations behind the algorithm. The experimental details and variables are also defined in Chapter 3. An explanation of the tool used for experimental data collection is included in Chapter 4 along with the experimental results and their statistical significance. Chapter 5 summarizes the conclusions and implications of the results from the previous chapters and presents areas where future research may occur.
11 2 2.1
LITERATURE REVIEW Classification of the Facility Layout Problem The Facility Layout Problem (FLP) has historically been defined as determining
the best placement, shape, and orientation for departments within a facility. Originally, the FLP was dubbed the “plant layout problem” by Apple [1] due to the fact that most research was done in the area of manufacturing plants. However, as shown by Francis et al. [9], the layout procedure developed for the manufacturing plant can and has been applied to a wide variety of other types of facilities and therefore has been renamed to generalize the field. Due to the numerous applications of the FLP, a hierarchical structure shown in Figure 2.1 is proposed in order to classify both the specific type of problem that can be solved and the algorithm and method by which it is approached. The hierarchy was developed by combining and extending existing definitions of the FLP hierarchy created by Francis et al. [9] and Meller [17]. The relationship of each level of the classification is explained below and more detailed discussions regarding actual methods are included in the sections that follow. The bold sections of the hierarchy indicate the types of problems and/or methods utilized by the modified SLP technique proposed in this research.
12 FACILITY LAYOUT PROBLEM
Facility Optimization
Facility Construction
Dynamic
Static
Multiple Floor
Single Floor
One Dimensional
Three Dimensional
Two Dimensional
Quantitative Analysis
Qualitative Analysis
Adjacency Based
Flexible
Centroids
I/O points
Graph Theory
Multicriteria
Manual
Material Flow
Distance
Deltahedron Wheel Exp. Tessa
Heuristic
Metaheuristic
MIP BIP QAP
AI NN TS
CAD
Modified SLP Figure 2.1: Facility Layout Problem Hierarchy
13 The FLP can be immediately separated into two main problems: designing the layout for the construction of a new facility versus improving an existing facility. They differ primarily by their constraints; existing facility layouts may have many location constraints such as utility lines, other departments, and structural dimensions whereas new facility construction generally allows the designer to define all of these conditions. From here, the FLP can be further divided into three subcategories defined as static, dynamic, or flexible layouts. These categories refer to how often and at what relative cost the layout can be changed to account for process variation. The next two levels of categorization involve the geometry of the facility in question. Floors, designated as single or multiple, indicate the number of floors within the facility. The number of dimensions refers to the type of block layout desired from layout generation. One dimensional layouts can represent an assembly line, two dimensional layouts can represent the floor space of separate departments and three dimensional layouts take into account the vertical space of the facility.
2.2
Solution Algorithms Algorithms for solving the FLP were initially broken into two main categories
that describe the objective function. Qualitative analysis methods are those that are measured by department adjacency or some other user-defined metrics. Quantitative analysis methods involve material handling costs and/or inter-departmental distances as an objective measurement. Since the definition of these two categories, extensive work
14 has been done combining the two methods into multicriteria analysis to incorporate both costs and adjacency objectives into the same algorithm. The method used to solve the problem presented in this thesis begins with the seminal work in the facility layout field known as Systematic Layout Planning (SLP) by Muther [18]. SLP is extremely well known and is considered to be a benchmark in the facility layout field. The tangible results of the steps of SLP are shown in Figure 2.2.
Facility Data
From-to Chart
Departmental Relationships
Department Sizes
Facility Size
Relationship Diagram
Space Relationship Diagram Safety, Limitations, & Modifications Layout Alternatives
Evaluation/Selection of Final Layout Figure 2.2: The Results of Each Step of SLP
15 The bold titles in Figure 2.2 indicate the portions of SLP that are modified by this research. The path from top to bottom indicates the prerequisites of each of the tangibles (i.e., facility data is used to produce a from-to chart). The SLP consists of three main steps: analysis, search, and selection. The analysis phase involves all of the data collection required to produce a good layout. Within the analysis phase, the facility data is utilized to define the departmental relationships. Muther [18] utilized closeness ratings [A, E, I, O, U, X, in order from strongest attracted to strongest repelled] instead of cost ratings to indicate departmental relationships. The search phase of SLP involves the actual layout generation. The analysis phase produces data from which a relationship diagram can be developed; the relationship diagram shows the relative location of each department with no space considerations. The space relationship diagram is then developed to show the location of each department with the space considerations. The technique proposed herein generates a space relationship diagram directly from the facility data without first generating a relationship diagram. Some modifications must then be performed on the space relationship diagram before it can be considered a feasible layout; the user may move departments in order to properly fit them into the facility or if any other limitations have not been previously considered. After layouts have been generated, the selection phase of SLP is executed. Each layout is evaluated based upon the solver’s predefined metrics (cost, closeness, etc.). The best layout is then selected based upon best performance with respect to the metric. Muther further explains each step of SLP indicating proper data collection techniques
16 along with extensive details regarding developing the data analysis that eventually yields the departmental relationships. 2.2.1
Quantitative Analysis The information gathering step of SLP involves collecting enough data to produce
a departmental relationship diagram. The actual data to be collected depends upon the approach to the solution. Departmental relationships have historically been addressed in three main ways: desired distances between departments, material flow weights that eventually determine material handling costs, and an adjacency factor assessed by the designer. The distance based and material flow based methods have, until recently, been approached by quantitative analysis because of the nature of the data and the relative ease in which it can be mathematically modeled. The FLP can be modeled in this manner and addressed as a Quadratic Assignment Problem (QAP) as shown by Muther [18]. The QAP has been shown to address and solve the FLP well for small problems. However, as the problem size increases, the number variables and constraints in the QAP become too large to effectively produce a layout. The FLP has also been solved as a Binary Integer Programming (BIP) problem by Houshyar and White [11] with favorable results. The BIP model was able to find nearoptimal layouts quickly for highly specialized problems with sixteen departments or less. However, since this problem has been shown to be NP-Complete by Sahni and Gonzalez [19], Houshyar and White [11] state that only very small problems can be addressed through heuristics and often don’t yield feasible solutions. To overcome the limitations of heuristic algorithms, the FLP has been researched using metaheuristic algorithms. Metaheuristic algorithms involve a general algorithmic framework that
17 utilizes lower level heuristics and that can be applied to a wide variety of problems. Some examples of metaheuristics applied to the facility layout problem include genetic algorithms, simulated annealing, tabu search, artificial neural networks, and artificial intelligence. A genetic algorithm model was tested against a simulated annealing model in research by Balakrishnan et al. [2]. The research shows that the genetic algorithm model performed better than the simulated annealing model and also found the known optimal solution with high frequency. A simulated annealing model and tabu search model by de Alvarenga et al. [6], both produced the known optimal solution for a facility layout problem set with high frequency and low computation time. The research shows that these models are “promising,” although they’ve only been tested on a small dataset. A model by Liao [14] integrates artificial neural networks with integer programming to solve the FLP. However, the research gives no results or comparisons to other models. Artificial intelligence is applied to the FLP in a model by Lin et al. [15] to solve the scenario of failure-to-fit solutions. This occurs when no feasible layouts are generated. The model produces good, “practical” solutions where other methods fall short of creating feasible layouts. According to research done by Malakooti [16], heuristic and metaheuristic algorithms that sort weights to find sub-optimal or near optimal solutions have generally been successful on some problems but not on a universal level. However, these weights often do not have an effect on a good solution and are dependant upon decision assumptions made by the problem solver Also, the time required to compute solutions
18 via heuristic or metaheuristic algorithms can be extremely lengthy and subsequently has become a performance factor in itself for determining good layouts as shown by Wascher and Merker [21]. There have been attempts to circumvent the lengthy computation time through development sorting algorithms by Yaman et al.[25]. The technique sorts the from-to department cost matrix or possible layouts until a near optimal layout is reached based upon the performance factors. This algorithm was applied to a very specific cellular manufacturing problem in which one product moves through each department only once and in a predefined order and produced better results than several mathematical models solved with heuristic algorithms. The advantage of the sorting algorithm is that computation time is minimal because it does not iterate through all possible solutions. However, the authors also concede that the sorting method needs to be extended before it can be applied to other problems or other performance factors. Yaman and Balibek [24] have shown that the decision making process required in various FLP solving algorithms is addressed as an extremely important part of the layout problem. The research utilizes modular layouts of decision making to better explain the system. Results show that at least some consideration must be given to the decision making process when completing the FLP, as it has previously been highly unstructured or unaddressed. Research also suggests that ensuring that the individual completing the problem has a high level of experience or implementing an expert system significantly increases the probability of achieving a near optimal result. 2.2.2
Qualitative Analysis FLP solving algorithms that utilize qualitative analysis replace the weights in the
19 from–to chart with a closeness rating. Houshyar and White [11] state that the six ratings [A, E, I, O, U, X] provide a very high probability that feasible solutions will be found on the first attempt unlike binary weighting. Strong knowledge of the system to be designed is an important prerequisite to any qualitative analysis. In new facility construction, these ratings are not always known to an accurate degree. For this reason, there have been several hybrid or multicriteria methods developed to mathematically estimate the standard FLP performance measures: closeness ratings, material flows and or interdepartmental distances. Urban [20] combined the two approaches in order to overcome the strong knowledge base limitations of qualitative analysis and the lack of an expert decision making step in quantitative analysis into one model. The model is a QAP-based algorithm that takes into account the closeness rating in addition to the work flow typically handled. The model finds good solutions with respect to quantitative measures while still separating departments with poor closeness ratings. Meller and Gau [17] presented a “robust layout” model that combines all three of the aforementioned performance measures into one objective function. Since the majority of facility layout problems rely on weighted department relationships as input data, the weight assignment technique is examined as to its effects on solutions. The solutions generated using the proposed objective function, or “robust solutions,” appear to be of a higher quality than those found with other existing methods. The research also shows that the assumption of improper weights produces better layouts than ignoring weighting altogether.
20 2.3
Graph Theoretic Approaches Graph theory has been applied to the facility layout for a number of years due to
the advantage that it provides: graph theory methods do not ever consider infeasible solutions. Although it is not explicitly included in the modified SLP method, graph theoretic approaches define insertion algorithms for departmental placement. Research in this area has shown some insertion methods to more successful than others for certain problems. The modified SLP technique implements the successful insertion methods when deciding the order of departmental placement. Information located in this review of the literature regarding graph theory that is not otherwise credited has been retrieved from research and a survey by Caccetta and Kusumah [5]. Since all layout diagrams that are generated using graph theory by definition must be planar, they therefore are feasible solutions. Graph theory layouts involve the use of vertices as the departments of the facility and the departmental relationships are modeled as non-intersecting, connecting edges. These edges are weighted according to the strength of the departmental relationships. The best solution can be found using graph theory by solving for the maximum planar subgraph based upon the weights that represent cost or benefit. The problem is mathematically defined by Caccetta and Kusumah [5] as: max B (G ) = ∑ wij xij
where: i, j ∈ E ′ G = feasible planar subgraph B (G ) = max planar subgraph of G
Subject to:
(1)
xij = 0,1 ∀ i, j
21 (2)
and G’ = (V, E’) where E’ = {(i,j): xij = 1} is a planar graph. Caccetta and Kusumah [5] produced a survey that tests various graph theoretic heuristics on the same problems and ranks them according to their maximum benefit and computation time. The benefits are useful in accurately comparing the methods. However, not all of the results documented include planar (and therefore feasible) graphs. To wit, the first method that utilized graph theory to construct a layout is known as the deltahedron method created by Foulds and Robinson [8]. The deltahedron method involves starting with a fixed number of departments and placing them one at a time based upon their benefit to the total layout. Benefit is calculated at each step for each of the unplaced vertices. The method begins by placing the four highest weighted vertices and then placing the remaining vertices based upon their calculated benefit. Caccetta and Kusumah [5] showed that the deltahedron method produced good results with good computational times. However, the method could only handle small problems. Tessa, an algorithm created by Boswell [3], finds the maximal planar graph of a facility by selecting “faces” based upon benefit. An edge or a vertex with two corresponding edges is added during each step to create a new triangular face with already existing departments. Tessa was shown by Caccetta and Kusumah [5] to be the most inefficient in computation time and produced the smallest average benefits for the test cases. The Wheel Expansion Algorithm created by Eades et al. [7] defines the initial departments to be placed as those that share the edge with the maximum weight. These
22 two vertices are defined as part of the “rim” of the wheel. One of the remaining vertices is chosen based upon maximum benefit to be the “hub” of the wheel while keeping the previous two vertices as the rim. This process continues with each new placed vertex to be chosen as the new hub based upon its benefit to all previous hubs now defined as the rim. This method tested very well for a small number of vertices (less than 15) in Caccetta and Kusumah’s analysis [5]. Caccetta and Kusumah [5] have also created a new heuristic to find the maximum planar graph of a given facility. The method involves removing edges of a graph layout and adding vertices at a location determined to be that of maximum benefit. The process continues until all vertices have been placed. This algorithm produced higher benefit than all other graph theoretic methods tested due to the fact that low weighted edges are removed at each step in the process whereas all of the other methods allowed poor weights to remain. The computational time was significantly higher than the deltahedron method yet lower than the wheel expansion algorithm. Therefore, this method is useful in large problems deemed too complex to be properly modeled by the deltahedron method.
23 3 3.1
FORMULATION Introduction As previously stated, the proposed method is a set of modifications to the SLP
procedure. These modifications are intended to implement several factors included in other facility layout methods that have proven to be effective. The first steps of SLP involving information gathering exist as Muther [18] defined them. However the information needed for the proposed method is slightly different. Because departments are segregated into subdepartments and the departmental adjacency constraint is relaxed, new relationship factors are created. Departments not only have an attraction to each other as defined by closeness ratings and material handling flow weights (a hybrid measure similar to Urban’s [20] QAP model), but individual subdepartments within the same department also have an attraction to each other. This level of attraction determines how important it is for two subdepartments to be located near each other and what cost penalty exists for having them far away. The attraction between two subdepartments within the same department is referred to as the department’s “viscosity” due to the fact that it models the degree in which a department adheres to itself. Subdepartments also have an attraction to those in different departments. This attraction is referred to as a department’s “affinity” to another department because it models the degree of attraction between two departments. Although viscosity and affinity are conceptually different, they are mathematically utilized in the same manner as a closeness rating and cost penalty assessment. Therefore, αii represents viscosity (the
24 attraction between subdepartments within department i) and αij represents affinity (attraction between a subdepartment of department i and a subdepartment of department j). It is important to note that when determining the values of viscosity and affinity, consideration must be given to Yaman and Balibek’s [24] concept that these decisions must be made by an expert of the actual system in order to generate a proper layout. In addition to the information gathering steps of SLP, the layout evaluation and selection steps are also modified in the proposed method. When determining departmental placement in the modified SLP, the insertion algorithms include the fundamental idea present in the deltahedron graph theory insertion algorithm created by Foulds and Robinson [8]. That is, the insertion methods are designed to model the idea that each subdepartment is placed based upon its maximum benefit to the total layout at that iteration. The insertion methods were tested against each other to show which had the highest maximum benefit. The second proposed extension to SLP is the redefinition of the subdepartment unit shape. Squares and rectangles have been the most commonly used shapes when defining departments or subdepartment units. This allows future subdepartments to be placed at four possible locations while bordering the first subdepartment. Proposed shapes include the triangle or hexagon in order to allow bordering subdepartments to be placed at three or six possible locations, respectively, to the first subdepartment. The differences between SLP and modified SLP are summarized in Table 3.1.
25 Table 3.1: Differences between SLP and Modified SLP SLP
Modified SLP
Grid Unit
Squares
Squares, Hexagons, or Triangles
Relationship Variable
Closeness Rating
Viscosity and Affinity
Insertion Algorithm
User Defined
Maximum Benefit to Layout (Viscosity Ranked, Affinity Ranked, Sum Ranked)
Department Placement
Single Placement
Incremental Placement
Adjacency and Shape Constraints
Mandatory
Relaxed
Layout Quality Measure
User Defined
Total Cost
3.2
Problem Definition The modified SLP technique is intended to be used on a specific subset of facility
layout problems that meet certain requirements. First, feasible solutions are defined such that department shape is not a constraint. Also, intradepartmental adjacency for one or more departments can be considered; however, having an adjacency constraint for every department will not necessarily yield a feasible solution. If shape and adjacency constraints need to be considered, the traditional SLP will produce a feasible layout for
26 the problem. A feasible solution of the modified SLP technique is any layout generated that accounts for the total required departmental areas. Secondly, the modified SLP technique requires that departments be able to be broken down into subdepartments of equivalent size. In the proposed method, one subdepartment size is defined for all departments. The subdepartment size is calculated by determining an appropriate area multiple required by each process. For example, if Process A requires 4,000 square feet and Process B requires 2,000 square feet, subdepartment size can be normalized to 2,000 square feet. Since Process A would then require two subdepartments that are adjacent, the subdepartments are given a viscosity value of 1.0 to ensure that they are placed together.
3.3
Assigning Viscosity and Affinity Values Due to the nature of the calculations within the modified SLP technique,
assigning appropriate viscosity and affinity is an important part of the procedure. The viscosity, αii, is defined as a factor reflects the closeness ratings, material flows, and material handling costs of intra-departmental movements. A high viscosity value for a particular department indicates that there is a strong need for intra-departmental adjacency or that the department results in a contiguous shape. More specifically, the rankings of the viscosities are just as important as their overall value since the relative rank plays a role in the order of placement. Due to the nature of the modified SLP technique, a department with a viscosity of 0.99 has a much greater chance for intradepartmental adjacency than one with a viscosity of 0.98. For the experimental
27 calculations, the viscosities of each department are randomly distributed between 0.5 and 1.0. The viscosity values are defined in this range because in this scenario a department is always more attracted to itself than it is to another department. The affinity values, αij are defined to be between 0.0 and 0.5 because the intradepartmental flows in this scenario always exceed interdepartmental flows. For the experimental calculations, the affinities of each department are randomly distributed in this range. Proper assignment of affinity in a real world scenario is determined by the material handling costs. The affinity between two departments is estimated as the cost per unit distance of material movement between two departments. An important note to mention is the two-way equality of the affinity of departments. That is, the affinity from department A to department B is equal to the affinity from department B to department A (αij = αji for all α). The bi-directional flows are included in the affinity assignment.
3.4
Objective Function The objective of the modified SLP is to generate a layout while minimizing total
cost. The total cost of the layout is calculated after each step of the procedure and is evaluated upon complete generation of the layout. The total cost of the layout is defined as the sum of the cost of adding each subdepartment to the layout at the lowest cost location shown in equation 3. t
s
1
1
∑ min ∑ ( Dn × α ij ) for all n available locations, departments i and j
(3)
28 where: s = the number of subdepartments that have already been placed t = the total number of subdepartments D n= distance between subdepartments. To better explain the cost calculation, the procedure is discussed at length in the sections that follow. 3.4.1 Distance The term distance used throughout this paper and in the calculations is the Euclidean distance between the centroids of subdepartments. This distance is calculated by the Pythagorean Theorem shown in equation 4. D = ( x A − xO ) 2 + ( y A − y O ) 2
(4)
Where x and y are the centroid coordinates and A and O refer to the subdepartment location as available or occupied, respectively. 3.4.2 Procedure To demonstrate the procedure, an example has been created and is shown below in Table 3.2. Table 3.2: Insertion Method Example Data
Department A B C
A 0.95 0.20 0.10
B 0.20 0.55 0.45
C 0.10 0.45 0.75
The values listed in Table 3.2 are the viscosities and affinities of each department. The viscosities, listed on the diagonal, are shaded and signify the intradepartmental attraction (A to A, B to B, and C to C). The affinities are the other values in the table and
29 represent the inter-departmental attraction (A to B, B to C, and A to C). For this example, consider the size of each department to be 2 units. The modified SLP begins with a blank facility grid made up of regular polygons. The facility grid for this example is made up of squares with an area of one unit which therefore have a side length of one. The facility grid is shown below in Figure 3.1.
Figure 3.1: Blank Facility Grid
The department placement order is dependent upon which insertion method is chosen. In this example, the department placement order is predetermined to be A, B, C (additional insertion methods will be discussed in Section 3.5.2). The first subdepartment is placed in the empty grid space nearest to the center of the facility grid as shown in Figure 3.2.
30
A
Figure 3.2: Placement of First Subdepartment
The location of the next subdepartment is determined as the location with the lowest cost addition to the existing layout. That location is found by finding the minimum Euclidean distance from each of the empty grid locations to the occupied location times the viscosity factor given to the department. Mathematically, the lowest cost after one department is:
min ( Dn × α ii )
(5)
∀ n available locations and where: i = department being placed. Since there is a four-way tie for the lowest cost position illustrated by Figure 3.3, the subdepartment is arbitrarily placed at the lowest cost grid location having the lowest row number then lowest column number.
31 2.69
2.12
1.90
2.12
2.69
2.12
1.34
0.95
1.34
2.12
1.90
0.95
A
0.95
1.90
2.12
1.34
0.95
1.34
2.12
2.69
2.12
1.90
2.12
2.69
Figure 3.3: Four-way Tie
When all subdepartments of a particular department have been placed, the insertion algorithm defines the next department to be placed. In this case, department B will be placed next. The lowest cost location is determined by finding the minimum sum of the distance between an available location and the occupied locations times the affinity between the two departments as shown below in Equation 6. s
min ∑ ( Dn × α ij )
(6)
1
∀ n available locations and department i where: i = department being placed j = department of subdepartment to which distance is being measured s = the number of subdepartments that have been placed The first subdepartment of department B is placed at the lowest cost location. The calculated costs of placing a subdepartment of B at each space are shown in Figure 3.4.
32
1.01
0.73
0.60
0.73
1.01
0.85
0.48
A
0.48
0.85
0.85
0.48
A
0.48
0.85
1.01
0.73
0.60
0.73
1.01
1.29
1.08
1.00
1.08
1.29
Figure 3.4: Placement of Third Subdepartment
The next subdepartment is placed at the lowest cost location relative to the previously placed subdepartments as calculated by Equation 6. The example calculations are shown in Figure 3.5.
1.79
1.28
1.38
1.96
2.75
1.40
B
A
1.58
2.50
1.63
1.03
A
1.71
2.59
2.24
1.83
1.83
2.29
3.00
3.03
2.73
2.74
3.06
3.62
Figure 3.5: Placement of Next Department
33 Subdepartments from department C are placed in the lowest cost locations exactly as those from departments A and B. The calculations for the placement of the first subdepartments of C are shown in Figures 3.6.
2.15
1.72
1.94
2.64
3.55
1.51
B
A
2.15
3.20
1.51
B
A
2.15
3.20
2.15
1.72
1.94
2.64
3.55
3.07
2.79
2.93
3.44
4.18
Figure 3.6: Calculations for Placement of Final Department
The lowest cost location of the placement of the first subdepartment of C is up against the facility “wall”. Therefore, if a subdepartment of C were placed at the lowest cost location, the subsequent calculations may be off because they do not include adjacent locations constrained by the wall. In order for this to be modeled as a green-field problem, walls must not be considered. Therefore, modifying the facility grid is necessary. A new column of empty spaces must be added to the left of the facility grid. The addition of a new column, the addition of the first subdepartment of C and the calculations of the lowest cost location are shown below in Figure 3.7.
34
4.02
2.90
2.78
3.62
5.02
6.64
3.27
C
B
A
4.40
6.20
3.58
2.26
B
A
4.52
6.29
4.63
3.65
3.39
4.06
5.35
6.91
6.05
5.32
5.16
5.63
6.62
7.93
Figure 3.7: Addition of a New Column to the Facility Grid
The last subdepartment of C is placed at the location with the lowest cost shown in bold in Figure 3.7. The space relationship diagram developed by the modified SLP technique is shown in Figure 3.8 below.
C
B
A
C
B
A
Figure 3.8: Space Relationship Diagram Developed by Modified SLP
As previously stated, the layout is evaluated based upon its total cost. The total cost of the layout is the sum of the costs of adding each subdepartment to the layout in the lowest cost location. The costs at each step of the example are shown in the figures in bold (.95+.48+1.03+1.51+2.26); the total cost is 6.23 units
35 3.5
Experimental Details
3.5.1 Subdepartment Shape In the explanatory example, the facility grid is comprised of squares. When a subdepartment is placed in a grid location, there are four surrounding locations that are considered to be adjacent. A grid location is adjacent if it shares a side with another location. Because the purpose of the algorithm is to place a subdepartment at the lowest cost location dependent upon Euclidean distance, the subdepartments are always placed in adjacent locations to already placed subdepartments. Because of this fact, varying the number of adjacent locations may have an effect on the total quality of the layout. To vary the number of adjacent locations, the facility grid shape is modified. The square grid works well because it is comprised of regular polygons that are tiled, meaning they are adjacent without gaps and repeating in pattern. Also, each vertex point within the grid has the same arrangement of congruent angles. This 2-dimensional structure is called a tessellation. According to Ghyka [10], only three regular tessellations exist for two dimensional polygons: triangles, squares, and hexagons. Other shapes such as pentagons can be fit into a grid, however the orientation of the shape then becomes a factor and the grid pattern does not repeat only in one dimension. For this experiment, the effect of using each of the three tessellations as the facility grid is tested. A triangular tessellation is shown in Figure 3.9 and a hexagonal tessellation is shown in Figure 3.10.
36
Figure 3.9: Triangular Tessellation (Weisstein [23])
Figure 3.10: Hexagonal Tessellation (Weisstein [22])
In order for the squares, hexagons, and triangles to be accurately compared, they must be normalized to have the same area. For this experiment, an area of one unit was chosen as the normalization value.
37 3.5.2 Insertion Methods As previously stated, the subdepartments will be placed incrementally depending upon which department is defined as the next to be placed. Three department insertion methods are addressed in this research and compared by their effect on the quality of layout measured by the total cost. The insertion methods utilize the viscosity and affinity for the problem to determine the order of placement. The previous example shown in Table 3.2 will be referenced for demonstrative purposes. The first insertion method is dubbed “Viscosity Ranked.” This method calls for the departments to be ranked in order from highest to lowest viscosity and placed into the facility grid as such. In the example the Viscosity Ranked method orders the departments as A (viscosity of 0.95), C (viscosity of 0.75), then B (viscosity of 0.55). The second method, “Affinity Ranked,” calls for the department with the highest viscosity to be placed first. Then, the department with the highest affinity to the previously placed department is placed. Departments have been placed in this manner until all have been placed. The order of department placement in the example using Affinity Ranked insertion would begin with A (viscosity of 0.95), B (affinity with A of 0.20), then C. The final insertion method, “Sum Ranked,” ranks the departments by the sum of their viscosity and affinities. The department with the highest sum is placed first and the subsequent departments are placed in order of decreasing sums. In the example, the placement order is C (sum of 1.30), A (sum of 1.25), then B (sum of 1.20).
38 3.5.3 Department / Problem Size The facility grid size utilized in this research is a 15 X 15 unit polygon grid. Therefore, there are 225 available placement locations for subdepartments. In order to make this a true green-field problem, the number of subdepartments is significantly less than the number of available locations so that walls of the facility do not play a role in the lowest cost location for subdepartmental placement. The problem is easily converted to a brown-field situation by increasing the number of subdepartments and therefore including the walls as a facility constraint. While the viscosities and affinities of each problem were randomly distributed in their appropriate ranges, the department sizes were held constant. Also, while testing the insertion algorithms and the subdepartment unit shapes, the number of departments was held constant at ten. This is done in order to reduce the variation in the answer and eliminate the possibility that department size or problem size may have an effect on the quality of the layout. 3.5.4 Testing Against Traditional SLP It is difficult to accurately compare the modified SLP technique to traditional SLP for many reasons. First, SLP does not necessarily generate layouts on the basis of cost whereas the modified SLP technique does. Also, the modified SLP procedure was intended to handle a different subset of problems that capable of being addressed by SLP. Finally, viscosities and affinities are not a part of traditional SLP. However, in order appraise the relative success or failure of the modified SLP to produce a good layout, a proper frame of reference is necessary. Therefore, traditional SLP was also tested utilizing a few rules and concepts. The layouts derived using
39 traditional SLP had the adjacency constraint and departmental shape factors implemented. That is, every subdepartment must have at least one adjacent side with another from the same department. Also, when placing subdepartments, some effort was put into making the departments rectangular shaped or “L” shaped as often seen in SLP layout generation. Finally, traditional SLP layout generation was performed only on the facility grid using square subdepartment shapes and by definition of SLP, Sum Ranked insertion. 3.5.5 Summary of Experimental Details Three problems are computed using the modified SLP procedure. Each problem consists of ten departments labeled A through J. Each of the departments has an assigned number of subdepartments between nine and sixteen and these values are held constant for all three problems. The total number of subdepartments in each problem is 115, which is small enough to not induce wall interference in the 225 unit facility and therefore be considered a green-field problem. Each problem is tested using each of the three insertion methods on each of the three subdepartment shapes. Therefore, there are nine total combinations of subdepartment shape and insertion methods that are tested with three replications each. Also, the three problems were tested using traditional SLP constraints of preferred departmental shape and adjacency in order to compare its quality of layout to the modified SLP procedure. Since department size may also have an impact on the quality of solution, six other problems were tested. The total number of subdepartments was held constant at 115; however the number of departments was increased to fifteen and twenty. This
40 means that the average number of subdepartments per department decreases. One problem with fifteen departments and one problem with twenty departments were analyzed for each of the nine shape/insertion combinations. The experimental problem data is listed in Appendix B.
3.6
A Note on Layout Development from Results
When the procedure is complete, the result is a grid layout of the departments comprised by unit polygons. From this grid layout, some amount of user manipulation may be required to convert the grid layout into a usable facility layout depending upon the particulars of the application. Subdepartments may need to be moved, especially in the cases of triangles and hexagons, in order to insure that the resulting layout is rectangular. The methods defined by the modified SLP technique to turn a space relationship diagram (facility grid) into an actual layout are equal to those of the traditional SLP: user defined goals combined with expertise of the system are required to generate an actual layout. For example, the facility grid generated by the modified SLP in problem shown in Appendix A is also shown below in Figure 3.11.
41
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2
B B B B B B D
3
4
5
6
7
8
9 10 11 12 13 14 15
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
C C C F F F F G A A E D
C C C F F F F A A A D H
C C C F F F A A A D H
H B J J A A A A A H
H D J J J J J H H
H H J J H H H
H H H H
Figure 3.11: Example Layout Generated Using Modified SLP
This layout was generated using square shaped subdepartments. The last two departments placed were D and H, respectively. Subdepartments from these two can be moved to locations that make this layout more rectangular if so desired. The new layout cost is calculated by subtracting the previous cost of placing each one of these in the layout and adding the cost of placing them at the new location. One alternative that better fits into a rectangular facility is shown below in Figure 3.12.
42 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2
B B B B B B D
3
4
5
6
7
8
9 10 11 12 13 14 15
B I I I E E E E D D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E
C C C F F F F G A A E
C C C F F F F A A A D
H C C C F F F A A A D
H H B J J A A A A A H
H H H D J J J J J H H
H H H H J J H H H
Figure 3.12: Resultant Facility Grid After Manipulation
The resultant facility grid is more rectangular in shape and only incurred a net 125 unit cost penalty for moving the H and D subdepartments. This results in a total cost of 8597, which is less than a 1.5% cost increase over the previous layout.
43 4 4.1
RESULTS Implementation
The experiment was computed using a tool created in Microsoft Excel. The tool computes the modified SLP algorithm as detailed in the Formulation section of this thesis. The calculations are performed iteratively, that is each lowest cost location is calculated after the previous subdepartment has been placed. The subdepartments are placed manually and the sum of the total cost is calculated manually as well. Other tools were considered because of their computation time, however Excel was chosen due to its visual interface and therefore the iterative process could be viewed during department placement. Mainly, the iterative visual tool allows department separation and layout shapes to be noticed. Screenshots of the Excel tool computing the layout of the ten department Viscosity Ranked insertion method on a unit square facility grid are shown in Appendix A.
4.2
Layout Generation
Due to the relaxed departmental adjacency and shape constraints, the layouts generated by the modified SLP technique are much different than those produced by traditional SLP. While traditional SLP departments are placed iteratively in rectangular or L-shaped blocks, the modified SLP often creates intricately shaped and sometimes non-adjacent departments. A layout generated using traditional SLP and a layout generated using modified SLP are shown below in Figures 4.1 and 4.2 for contrast.
44
1
2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3
4
5
6
7
8
9
10
11
12
E E E E E E E E E B B B
H H C C D D D D E B B B
H H C C D D D D J J J B
H C C C F F F F A A J B
H C C C F F F F A A J B
H H C C F F F F A A J B
H H I I I I I I A A J B
H H I I I I I I A A J
H H G G I I A A A A J
H H G G G G G G G
13
14
15
15
Figure 4.1: Traditional SLP Layout
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2
3
J J J J J
4
5
6
7
8
9
10
11
12
13
14
B J J A A A A A A
B B J A A A A A A A
B B J H H G I I G G A
B B B H H F F F I I I G
B B H H C C C F F I I G
B H C C C C C F F I G
H H D D C C C F I I G
H H D D D C F F I I G
H D D D F F I I G
H H E E E E E E
H H E E E E
Figure 4.2: Modified SLP Layout
The first difference to note between the generated layouts is the overall shape. The traditional SLP layout is generally rectangular while the modified SLP layout is somewhat elliptical. This occurs because the subdepartments placed using modified SLP
45 techniques are at a location that maximizes their benefit to the overall layout. Therefore, the location of a subdepartment to the entire layout is more often more important than the location relative to other subdepartments of the same department. This is true especially for the placement of the later departments. Often times, the first two subdepartments of a later department would be placed on opposite sides of a layout and then subsequent subdepartments would be placed at available locations between the two. Departmental separation occurs when there are not enough subdepartments to completely fill the adjacent locations between the initially placed subdepartments. Department G in the modified SLP layout shows this.
4.3
Experimental Results and Analysis
The total layout costs were calculated for each of the thirty problems. The results of the costs are shown in Table 4.1.
46 Table 4.1: Layout Cost Results
Viscosity Ranked Affinity Ranked Sum Ranked
SLP
Problem No. 1 2 3 1 2 3 1 2 3 1 2 3
Squares
8472 8814 10712 8500 8319 10324 8482 9558 9942 8497 9472 10051
Triangles Hexagons
8930 8671 10631 9159 8232 10425 9414 8268 10052
8450 8730 10481 8428 8454 10333 8266 8337 10030
The results are also shown graphically in Figures 4.3 – 4.6 below for visual comparison of the data.
47 12000
10000
8000
Cost
Squares 6000
Triangles Hexagons
4000
2000
0 1
2
3
Problem
Figure 4.3: Viscosity Ranked Cost Chart
The cost comparison of the three problems shows that the cost ranges are problem dependent. The costs of layouts generated using data from problem three are a fair amount higher than one and two. For all three problems, using hexagons with Viscosity Ranked insertion produced lower costs layouts than layouts generating using squares as subdepartments.
48 12000
10000
Cost
8000 Squares 6000
Triangles Hexagons
4000
2000
0 1
2
3
Problem
Figure 4.4: Affinity Ranked Cost Chart
Figure 4.4 above reiterates that problem three costs are higher than problems one and two. Also, for Affinity Ranked insertion no shape consistently produced the lowest cost. The lowest cost shape appears to be somewhat problem dependent when using this insertion method.
49 12000
10000
8000
Cost
Squares Triangles
6000
Hexagons SLP
4000
2000
0 1
2
3
Problem
Figure 4.5: Sum Ranked and SLP Cost Chart
While squares and triangle shaped subdepartments produced lower cost layouts than SLP on two out of the three problems, hexagons produced lower cost layouts on all three problems.
50 9500 9400 9300 9200 Total Cost
Squares Triangles
9100
Hexagons SLP
9000 8900 8800 8700 8600 Viscosity Ranked
Affinity Ranked Insertion Method
Sum Ranked
Figure 4.6: Average Costs of Shape/Insertion Method
While SLP was not the worst performing algorithm, the average costs were consistently higher than all but layouts generated using Viscosity Ranked triangles. Sum Ranked hexagons produced layouts with the lowest average cost for the three problems tested. In order to properly compare the results for each subdepartment shape and for each insertion method, the experimental results must be tested to for a statistical difference between each treatment. Since the problem three results are much higher than that of the other two, all problem costs are not considered to be normally distributed for all viscosity assignments. Therefore, instead of testing the mean total cost for each treatment, the mean of the percent difference between the total costs of problems one,
51 two, and three are tested to accurately compare the treatments. The mean percent difference between two treatments is calculated using equation 7. n
D=
∑ 2( x p =1
pi
− x pj ) ( x pi + x pj ) n
∀ treatments i, j; i ≠ j
(7)
where: p = problem number n = total number of problems. The Student-t distribution was utilized to test the differences in the means for each shape due to the fact that the population standard deviation is not known and needs to be estimated by using the sample standard deviation. The null hypothesis for each normal test was that the mean percent difference between the total costs of two treatments equals zero while the alternate hypothesis is that the mean percent difference is not equal to zero, shown in equation 8. H0: µD = 0; H1: µD ≠ 0
(8)
The T test statistic used for comparison of each insertion/shape combination is shown in equation 9.
T=
D − µD SD
n
(9)
For the Student-t test, the T statistic denotes the relative significance of the factor being tested. When testing the shapes for statistical difference, the two-tailed 95% confidence interval with eight degrees of freedom for the t distribution is: − 2.306 < t < 2.306 .
(10)
52 Therefore, if the calculated T for the comparison of two treatments falls within this range, the null hypothesis is accepted. If T falls outside of this range, the null hypothesis is rejected and the two treatments are considered to have statistically different means. Table 4.2 lists the T statistic for the comparison of each shape along with the P value below.
Table 4.2: Calculated T and P Values for Shapes and Insertion Methods T P -0.343 0.741 Squares vs. Triangles 1.642 0.139 Triangles vs. Hexagons 1.305 0.228 Squares vs. Hexagons Viscosity vs. Affinity Ranked 2.309 0.050 -0.188 0.855 Affinity vs. Sum Ranked 0.984 0.354 Viscosity vs. Sum Ranked
The P value represents the degree of certainty that the mean percent difference of the two treatments is zero, meaning the two datasets are statistically equivalent. For example, in the case of triangles vs. hexagons, the P value is .139; this means that there is 13.9% statistical certainty that the mean percent difference of layout cost is zero. While not low enough to be statistically significant, this P value may be low enough to merit further investigation in future research. Although none of the calculated T statistics for shape comparison falls outside of the 95% confidence interval with the current data, the Viscosity vs. Affinity Ranked comparison does. With a calculated P value of .05, this means that the costs from the two treatments fall within the same population 5.0% of the time and therefore are statistically different with Affinity Ranked insertion performing better than Viscosity Ranked.
53 Each shape/insertion method combination was tested to examine the possibility that the interaction of the two may have statistical significance. Since there are only three problems each in the population of each treatment, the degrees of freedom drops to two and the 95% confidence interval for t is: − 4.303 < t < 4.303 .
(11)
The results for the calculated T statistics and P values for the comparison of each shape/insertion method are shown below in Table 4.3.
Table 4.3: Calculated T and P Values for Shape/Insertion Method Combinations Sq/ Vs Visc Sq/ T 1.70 Sq/ Affin P 0.231 Affin Sq/ T -0.06 -0.61 Sq/ Sum P 0.961 0.603 Sum Tri/ T -0.44 -6.90 -0.13 Tri/ Visc P 0.702 0.020 0.905 Visc Tri/ T 0.13 -0.96 0.12 0.69 Tr/ Affin P 0.905 0.439 0.918 0.563 Affin Tri/ T 0.13 -0.58 0.14 0.48 0.08 Tri/ Sum P 0.907 0.622 0.904 0.676 0.941 Sum Hex/ T 2.02 -1.22 0.33 1.15 0.13 0.07 Hex/ Visc P 0.181 0.348 0.772 0.370 0.905 0.947 Visc Hex/ T 2.45 -0.39 0.63 3.59 0.67 0.45 1.91 Hex/ Affin P 0.134 0.732 0.595 0.069 0.570 0.698 0.197 Affin Hex/ T 3.94 1.78 1.17 5.31 1.28 0.93 4.87 4.50 Hex/ Sum P 0.059 0.216 0.363 0.034 0.328 0.451 0.040 0.046 Sum T -0.09 -0.71 -0.21 0.12 -0.14 -0.16 -0.42 -0.74 -1.37 SLP P 0.933 0.553 0.852 0.913 0.899 0.887 0.716 0.537 0.304
Statistical difference is present in four pairs of shape/insertion methods. Triangles/Viscosity Ranked insertion statistically produces layouts with higher costs than both squares/Affinity Ranked and hexagons/Sum Ranked combinations. Also,
54 Hexagons/Sum Ranked insertion statistically produces lower cost layouts than hexagons/Viscosity Ranked and hexagons/Affinity Ranked. Other P values that were very near the threshold and may merit further experimentation include the difference between hexagons/Sum Ranked and squares/Affinity Ranked as well as hexagons/Affinity Ranked and triangles/Viscosity Ranked. Overall, hexagons/Sum Ranked produced the lowest average costs for the three problems, the most significant differences between other combinations, and the lowest overall P values. The null hypothesis is accepted for the comparison of any of the methods to traditional SLP. This means that with 95% certainty, every shape/insertion combination of the modified SLP performed as well as traditional SLP. Although not statistically different, hexagons with Sum Ranked insertion produced layouts with lower costs than those generated by traditional SLP on all three problems. The statistical significance may be affected by the relatively low number of problems and therefore degrees of freedom.
4.4
Problem Size
The cost results from the three problems of different sizes are listed in Table 4.4
55 Table 4.4: Cost Results for Each Problem Size
Viscosity Ranked Affinity Ranked Sum Ranked
Problem Size. 10 15 20 10 15 20 10 15 20
Squares Triangles Hexagons
8472 8019 8882 8500 7815 8793 8482 7756 9232
8930 8075 9008 9159 7848 8813 9414 7678 8602
8450 8091 8938 8428 7904 8815 8266 7919 8595
4.4.1 Layout Cost Using the analysis method defined in the previous section, the costs of layouts generated different shape and insertion method on problems of different sizes were analyzed. The calculated T statistics and P values are shown in Table 4.5.
Table 4.5: T and P values for Problems of Different Sizes T P -1.157 0.280 Squares vs. Triangles 1.515 0.168 Triangles vs. Hexagons 0.705 0.501 Squares vs. Hexagons 2.263 0.054 Viscosity vs. Affinity Ranked 0.297 0.774 Affinity vs. Sum Ranked 1.084 0.310 Viscosity vs. Sum Ranked
Although no calculated T statistic fell outside of the 95% confidence interval, the Viscosity vs. Affinity Ranked statistic was very close. With a low P value of 0.054, this value does fall outside of the 94% confidence interval. This is consistent with the results presented in the previous section.
56 4.4.2 Departmental Separation Departmental separation refers to a department that after layout generation has at least one group of subdepartments that are not adjacent to others within that department. Three different problem sizes were tested for their impact on departmental separation: ten departments, fifteen departments, and twenty departments. As previously stated, the number of subdepartments was held constant at 115. The average numbers of separations per problem as related to problem size are shown in Figure 4.7.
Mean Separations Per Problem
7 6 5 4 3 2 1 0 10
15
20
Number of Departments
Figure 4.7: Average Number of Departmental Separations per Problem
57 The number of departmental separation occurrences increased with the number of departments. In these problems, the number of subdepartments per department was decreased in order to keep the total sum of subdepartments at 115. Generally speaking, as the layouts are generated, the subdepartments are initially placed according to their benefit to the existing layout determined by distance. However, as more subdepartments for a given department are placed, their maximum benefit to the layout is determined as the location that is closest to others within that department. Departmental separation typically occurs during later department placement within departments of small size (approximately 4-6 units) because their attraction to each other is not as beneficial as their location relative to the entire layout. Also, once one department is fully placed and a separation exists, the subsequent departments are more likely to result in separation. Therefore, department size has an affect on the number of departmental separations and in some circumstances the quality of layout.
58 5 5.1
CONCLUSIONS Review of Results
The purpose of this research was to develop a modified version of SLP that allows departmental division and irregular shaped subdepartments during layout generation with some success. This subset of problems has not previously been addressed by traditional SLP. Within this task, separate insertion methods were tested for their effect on the quality of layout determined by total cost. The modified SLP technique was shown with 95% confidence to produce layouts comparable to those created by SLP. Within the modified SLP technique, utilizing hexagons as subdepartment unit shapes and the Sum Ranked insertion method produces the layouts with the lowest average costs. This is attributed to the increased number of adjacent locations held by hexagons and therefore the increased number of locations that subdepartments can be placed. Since departmental adjacency is relaxed in this method, appropriate assignment of viscosity and affinity is important. Departmental separation is more likely to occur at departments placed late in the algorithm due to the fact that the benefit to the overall layout is stronger than the benefit to be placed near others of the same department. Therefore, viscosities should be assigned to not only accurately reflect flow weights, but a closeness rating as well. In all three insertion methods, viscosity assignment helps determine placement order. Viscosity should be assigned to a department relative to other departments in order to appropriately determine order of placement and the degree of relaxation of the adjacency constraint.
59 One unique contribution of this research is the addition of viscosity to SLP data collection. Viscosity establishes a weight from a department to itself in the case that departmental adjacency can be relaxed instead of mandatory. This viscosity factor also allows departmental adjacency rule to be adhered to in the case that viscosity is given a value of one. The other unique contribution of this research is the determination that hexagonal tessellations in some cases produce lower cost than adjacency-based squares when used as a facility grid. Admittedly, some work must then be done to the hexagonal layout in order to properly “fit” the resultant layout into a real-world facility.
5.2
Application
Like traditional SLP, the simplicity of the modified SLP is important so that it can be applied with ease in both the classroom and industrial settings. The modified SLP technique further enhances SLP by allowing application to a specific subset of problems previously unable to be addressed by SLP. Specifically, modified SLP allows the user to examine departmental and subdepartmental relationships when adjacency constraints are ignored. One specific application where the modified SLP technique could be used is for facility where there are several individual process stations. The process stations can now be grouped together because of similar flow weights and material handling costs to reduce problem complexity. However, process adjacency in this scenario while being possibly preferred is not mandatory. Therefore, the modified SLP can be applied and produce results as good as or better than traditional SLP.
60 The modified SLP technique is to be used after initial data collection to generate layouts as a starting point to solving the FLP. The space relationship diagram produced by the modified SLP may be beneficial when an expert knowledge is applied to produce a final facility layout.
5.3
Future Work
First, other insertion methods may be tested within the modified SLP technique for their effect on the quality of layout. Also, more information on the potential relationship between department size and departmental separation may be explored. The histogram shows that there is a correlation, however no other conclusions can be drawn from that particular set of data. Finally, this method was tested with an iterative algorithm developed in Excel to allow the user to view the departmental placement pattern. Therefore, the testing process was extremely time consuming and user dependent. Now that the placement pattern has been exposed, more data could be tested on a software tool that is capable of solving many problems in a short time period. This could be done to expose any other relationships not determined in this research or verify the relationships for a larger problem set and therefore more degrees of freedom.
61 6
REFERENCES
[1]
Apple, J. M. Plant Layout and Material Handling. Wiley and Sons, New York. 1977.
[2]
Balakrishnan, Jaydeep, Chun-Hung Cheng, and Kam-Fai Wong. "FACOPT: A user friendly FACility layout OPTimization system." Computers and Operations Research. 2003, Vol. 30, pp. 1625-1641.
[3]
Boswell, S.G. “Tessa – A new greedy heuristic for facilities layout planning.” International Journal of Production Research. 1992, Vol. 30, pp. 1957-1968.
[4]
Bozer, Y. and R. Meller. “A reexamination of the distance-based facility layout problem.” IIE Transactions. Vol. 27, pp. 549-560.
[5]
Caccetta, Louis and Yaya S. Kusumah. "Computational Aspects of the Facility Layout Design Problem." Nonlinear Analysis. 2001, Vol. 47, pp. 5599-5610.
[6]
De Alvarenga, A, F. J. Negreiros-Gomes, and M. Mestria. “Metaheuristic methods for a class of the facility layout problem.” Journal of Intelligent Manufacturing. 2000, Vol. 11, pp. 421-430.
[7]
Eades, P., L. R. Foulds, and J. W. Griffin. “An efficient heuristic for identifying a maximum Weight Planar Subgraph.” Lecture Notes in Mathematics No. 952. (Combinatorial Mathematics IX). Springer-Verlag. Berlin. 1982.
[8]
Foulds, L.R. and D.F. Robinson. “Graph theoretic heuristic for the plant layout problem.” International Journal of Production Research. 1978, Vol. 16, pp. 27-37.
[9]
Francis, R. L., L. F. McGinnis and J.A. White. Facility Layout and Location: An Analytical Approach. Prentice-Hall, Englewood Cliffs, New Jersey. 1992.
[10] Ghyka, M. The Geometry of Art and Life. Dover, New York. 1977. [11] Houshyar, Azim and Bob White. "Comparison of Solution Procedures to the Facility Location Problem." Computers in Industrial Engineering. 1997, Vol. 32, No. 1, pp. 77-87. [12] Kim, Jae-Gon and Yeong-Dae Kim. "Layout planning for facilities with fixed shapes and input and output points." International Journal of Production Research. 2000, Vol. 38, No. 18, pp. 4635-4653.
62 [13] Kusiak, A. and S. S. Heragu. “The facility layout problem.” European Journal of Operational Research. 1987, Vol. 29, pp. 229-251. [14] Liao, T. Warren. “Design of line-type cellular manufacturing systems for minimum operating and material-handling costs.” International Journal of Production Research. 1994, Vol. 32, No. 2, pp. 387-397. [15] Lin, Jin-Lang, Bobbie Foote, Simin Pulat, Chir-Ho Chang, and John Y. Cheung. “Solving the failure-to-fit problem for plant layout: By changing department shapes and sizes.” European Journal of Operational Research. 1996, Vol. 89, pp. 135-146. [16] Malakooti, B. "Multiple objective facility layout: a heuristic to generate efficient alternatives." International Journal of Production Research. 1989, Vol. 27, No. 7, pp. 1225-1238. [17] Meller, R. D. and K.-Y. Gau. “Facility layout objective functions and robust layouts.” International Journal of Production Research. 1996, Vol. 34, No. 10, pp. 2727-2742. [18] Muther, R. Systematic Layout Planning. Cahers Books, Boston. 1973. [19] Sahni, S. and T. Gonzalez. “P-complete approximation problem”, Journal of the Association for Computing Machinery. 1976, Vol. 23, pp. 55-565. [20] Urban, Timothy L. “A multiple criteria model for the facilities layout problem.” International Journal of Production Research. 1987, Vol. 25, No. 12, pp. 1805-1812. [21] Wascher, G. and J. Merker. "A comparative evaluation of heuristics for the adjacency problem in facility layout planning." International Journal of Production Research. 1997, Vol. 35, No. 2, pp. 447-466. [22] Weisstein, Eric W. “Hexagonal Grid.” From Mathworld – A Wolfram Web Resource. http://mathworld.wolfram.com/HexagonalGrid.html. [23] Weisstein, Eric W. “Triangular Grid.” From Mathworld – A Wolfram Web Resource. http://mathworld.wolfram.com/TriangularGrid.html. [24] Yaman, R. and E. Balibek. "Decision Making for Facility Layout Problem Solutions." Computers and Industrial Engineering. 1999, Vol. 37, pp. 319322.
63 [25] Yaman, R., D.T. Gethin and M.J. Clarke. "An effective sorting method for facility layout construction." International Journal of Production Research. 1993, Vol. 31, No. 2, pp. 413-42.
64 APPENDIX A Step by Step Layout Generation Using Modified SLP The graphic user interface of the Excel tool that generates a layout by using the modified SLP technique is shown below.
1
Next Location (Row , Col) Max Visc. Dept. 2 3 4 5 6
1 F 7
15 8
9
COST:
0.00
10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Figure A. 1: Subdepartmental Placement
The “Next Location” cells give the relative row and column within the facility grid of the minimum cost location of the next subdepartment to be placed. The “Max Visc. Dept.” cell refers to the remaining department with the highest viscosity. Because this example shows the Viscosity Ranked insertion method, this cell is also the current department being placed. The “Cost” cell shows the cost of adding the next subdepartment to the layout at the location given in the “Next Location” cell. The experimental performance
65 measure is the total cost and is defined as the sum of the cost of adding each subdepartment to the layout. Since the facility grid is blank, the first department can be placed at any location. The grid location closest to the center makes the most sense in order to avoid the facility walls. However, lowest cost location ties are broken by choosing the lowest cost grid location in the rows above and columns to the left of the layout. Therefore, the layout typically grows up and to the left; therefore a good starting location is in the lower right quadrant of the facility grid. For this example, the starting location is chosen as row eight, column nine. This example is a Viscosity Ranked, ten department problem utilizing a facility grid with square subdepartments. The viscosities (shaded on the diagonal), affinities, and sizes of each department are listed below. Table A.1: Problem Data A B C D E F G H I J
A
B
C
D
E
F
G
H
I
J
SIZE
0.783
0.043
0.005
0.498
0.420
0.464
0.424
0.308
0.005
0.437
14
0.043
0.663
0.357
0.248
0.343
0.452
0.381
0.213
0.302
0.162
11
0.005
0.357
0.774
0.343
0.019
0.313
0.226
0.303
0.291
0.266
12
0.498
0.248
0.343
0.641
0.289
0.147
0.285
0.356
0.438
0.194
8
0.420
0.343
0.019
0.289
0.679
0.017
0.170
0.447
0.447
0.364
10
0.464
0.452
0.313
0.147
0.017
0.927
0.156
0.455
0.048
0.008
12
0.424
0.381
0.226
0.285
0.170
0.156
0.875
0.422
0.197
0.413
9
0.308
0.213
0.303
0.356
0.447
0.455
0.422
0.608
0.350
0.399
16
0.005
0.302
0.291
0.438
0.447
0.048
0.197
0.350
0.897
0.096
14
0.437
0.162
0.266
0.194
0.364
0.008
0.413
0.399
0.096
0.693
9
Since department F has the highest viscosity, all of its subdepartments are placed first.
66 Next Location Max Visc. Dept. 1 2 3 4 5 6
7 F 7 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
9 9
COST:
0.93
10 11 12 13 14 15
F
Figure A. 2: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
7 F 7 8
8 9
COST:
2.24
10 11 12 13 14 15
F F
Figure A. 3: Subdepartmental Placement
67 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
8 F 7 8
F
8 9
COST:
3.16
10 11 12 13 14 15
F F
Figure A. 4: Subdepartmental Placement
68 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
6 F 7 8
9 9
F F
F F
COST:
6.16
10 11 12 13 14 15
Figure A. 5: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
6 F 7 8
8 9
F F
F F F
COST:
7.09
10 11 12 13 14 15
Figure A. 6: Subdepartmental Placement
69 Next Location Max Visc. Dept. 1 2 3 4 5 6
7 F 7 8
9
F F F
F F F
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
7
COST:
9.54
10 11 12 13 14 15
Figure A. 7: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
6 F 7 8
9
F F F
F F F
F
7
COST:
11.78
10 11 12 13 14 15
Figure A. 8: Subdepartmental Placement
70 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
8 F 7 8
F F
F F F
7 9
COST:
13.63
10 11 12 13 14 15
F F F
Figure A. 9: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
5 F 7 8
9
F F F
F F F
F F F
8
COST:
18.18
10 11 12 13 14 15
Figure A. 10: Subdepartmental Placement
71 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
7 F 7 8
9
F F F F
F F F
F F F
6
COST:
20.81
10 11 12 13 14 15
Figure A. 11: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
F
5 F 7 8
9
F F F F
F F F
F F F
7
COST:
22.90
10 11 12 13 14 15
Figure A. 12: Subdepartmental Placement
72 After all of the subdepartments of department F have been placed, the Excel tool automatically updates the “Max Visc. Dept.” cell to show the remaining department with the highest viscosity. In this example, the next highest viscosity department is I; all of its subdepartments are placed next. The cost of placement at each location is now determined by the sum of the distances times the affinity between departments I and A. After one subdepartment of department I has been placed, the viscosity of department I is included in the cost calculations as well.
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
F
6 I
6
7
8
9
F F F F
F F F F
F F F
COST:
1.25
10 11 12 13 14 15
Figure A. 13: Subdepartmental Placement
73 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I F
5 I
6
7
8
9
F F F F
F F F F
F F F
COST:
2.40
10 11 12 13 14 15
Figure A. 14: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I F
6 I
5
7
8
9
F F F F
F F F F
F F F
COST:
3.90
10 11 12 13 14 15
Figure A. 15: Subdepartmental Placement
74 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I
I I F
5 I
5
7
8
9
F F F F
F F F F
F F F
COST:
5.00
10 11 12 13 14 15
Figure A. 16: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I
I I F
7 I
5
7
8
9
F F F F
F F F F
F F F
COST:
7.66
10 11 12 13 14 15
Figure A. 17: Subdepartmental Placement
75 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I F
6 I
4
7
8
9
F F F F
F F F F
F F F
COST:
9.50
10 11 12 13 14 15
Figure A. 18: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I
I I I
I I F
5 I
4
7
8
9
F F F F
F F F F
F F F
COST:
11.29
10 11 12 13 14 15
Figure A. 19: Subdepartmental Placement
76 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I
I I I
I I F
7 I
4
7
8
9
F F F F
F F F F
F F F
COST:
13.64
10 11 12 13 14 15
Figure A. 20: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I
I I F
4 I
5
7
8
9
F F F F
F F F F
F F F
COST:
17.03
10 11 12 13 14 15
Figure A. 21: Subdepartmental Placement
77 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I
I I F
4 I
6
7
8
9
F F F F
F F F F
F F F
COST:
19.38
10 11 12 13 14 15
Figure A. 22: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I
I I I F
4 I
4
7
8
9
F F F F
F F F F
F F F
COST:
21.42
10 11 12 13 14 15
Figure A. 23: Subdepartmental Placement
78 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I I
I I I I
I I I F
5 I
3
7
8
9
F F F F
F F F F
F F F
COST:
25.09
10 11 12 13 14 15
Figure A. 24: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I
I I I I
I I I I
I I I F
6 I
3
7
8
9
F F F F
F F F F
F F F
COST:
26.25
10 11 12 13 14 15
Figure A. 25: Subdepartmental Placement
79 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I
I I I I
I I I I
I I I F
4 I
3
7
8
9
F F F F
F F F F
F F F
COST:
31.20
10 11 12 13 14 15
Figure A. 26: Subdepartmental Placement
The next department to be placed is G. The cost of each location is now the sum of the distances to each occupied I location times the affinity between G and I plus the sum of the distances between each F location times the affinity between G and F. After one subdepartment of G has been placed, the cost calculation also includes the sum of the distance to each G location times the viscosity of G.
80 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I
I I I I
I I I F
8 G 7 8
9
F F F F
F F F
F F F F
6
COST:
13.59
10 11 12 13 14 15
Figure A. 27: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I
I I I I
I I I F G
8 G 7 8
9
F F F F
F F F
F F F F
5
COST:
15.04
10 11 12 13 14 15
Figure A. 28: Subdepartmental Placement
81 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I
I I I I G
I I I F G
8 G 7 8
9
F F F F
F F F
F F F F
4
COST:
18.44
10 11 12 13 14 15
Figure A. 29: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G
I I I I G
I I I F G
9 G 7 8
9
F F F F
F F F
F F F F
5
COST:
21.07
10 11 12 13 14 15
Figure A. 30: Subdepartmental Placement
82 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G
I I I I G G
I I I F G
9 G 7 8
9
F F F F
F F F
F F F F
6
COST:
22.13
10 11 12 13 14 15
Figure A. 31: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G
I I I I G G
I I I F G G
9 G 7 8
9
F F F F
F F F
F F F F
4
COST:
25.88
10 11 12 13 14 15
Figure A. 32: Subdepartmental Placement
83 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G
I I I F G G
9 G 7 8
9
F F F F
F F F
F F F F
7
COST:
28.85
10 11 12 13 14 15
Figure A. 33: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G
I I I F G G
10 G 7 8
F F F F G
F F F F
5 9
COST:
32.63
10 11 12 13 14 15
F F F
Figure A. 34: Subdepartmental Placement
84 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G
10 G 7 8
F F F F G
F F F F
6 9
COST:
33.58
10 11 12 13 14 15
F F F
Figure A. 35: Subdepartmental Placement
Department A and all subsequent departments are placed in the same manner as F, I, and G.
85 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G
9 A 7 8
F F F F G
F F F F
8 9
COST:
25.09
10 11 12 13 14 15
F F F
Figure A. 36: Subdepartmental Placement
The next figure shows that the lowest cost location for the next A subdepartment is at a location that is considered nonadjacent to the previously placed A subdepartment. In the following figures, the lowest cost location are those that fill in the gaps between the two nonadjacent A subdepartments.
86 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G
10 A 7 8
F F F F G
F F F F A
7 9
COST:
29.53
10 11 12 13 14 15
F F F
Figure A. 37: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G
10 A 7 8
F F F F G A
F F F F A
8 9
COST:
32.71
10 11 12 13 14 15
F F F
Figure A. 38: Subdepartmental Placement
87 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G
9 A 7 8
F F F F G A
F F F F A A
9 9
COST:
33.93
10 11 12 13 14 15
F F F
Figure A. 39: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G
10 A 7 8
F F F F G A
F F F F A A
9 9
COST:
40.03
10 11 12 13 14 15
F F F A
Figure A. 40: Subdepartmental Placement
88 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G
11 A 7 8
9
F F F F G A
F F F A A
F F F F A A
7
COST:
43.85
10 11 12 13 14 15
Figure A. 41: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G
11 A 7 8
F F F F G A A
F F F F A A
8 9
COST:
45.60
10 11 12 13 14 15
F F F A A
Figure A. 42: Subdepartmental Placement
89 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G
11 A 7 8
F F F F G A A
F F F F A A A
6 9
COST:
48.83
10 11 12 13 14 15
F F F A A
Figure A. 43: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G A
9 A 7 8
F F F F G A A
F F F F A A A
10 9
COST:
53.46
10 11 12 13 14 15
F F F A A
Figure A. 44: Subdepartmental Placement
90 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G A
8 A 7 8
F F F F G A A
F F F F A A A
10 9
F F F A A
COST:
54.79
10 11 12 13 14 15
A
Figure A. 45: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G A
11 A 7 8
F F F F G A A
F F F F A A A
9 9
F F F A A
COST:
58.40
10 11 12 13 14 15
A A
Figure A. 46: Subdepartmental Placement
91 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G A
10 A 7 8
F F F F G A A
F F F F A A A
10
COST:
60.42
9
10 11 12 13 14 15
F F F A A A
A A
Figure A. 47: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G A
7 A 7 8
F F F F G A A
F F F F A A A
10 9
F F F A A A
COST:
66.16
10 11 12 13 14 15
A A A
Figure A. 48: Subdepartmental Placement
92 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G A
11 A 7 8
F F F F G A A
F F F F A A A
10
COST:
72.89
9
10 11 12 13 14 15
F F F A A A
A A A A
Figure A. 49: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G A
4 C 7 8
9
10 11 12 13 14 15
F F F F G A A
F F F A A A
A A A A A
F F F F A A A
7
COST:
Figure A. 50: Subdepartmental Placement
34.31
93 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G A
4 C 7 8
8 9
10 11 12 13 14 15
C F F F F G A A
F F F A A A
A A A A A
F F F F A A A
39.13
COST:
Figure A. 51: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
5 C 6 7
8
9
10 11 12 13 14 15
I I I F G G G A
C F F F F A A A
F F F A A A
A A A A A
C F F F F G A A
9
COST:
41.88
Figure A. 52: Subdepartmental Placement
94 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
I I I F G G G A
3 C 7 8
9
10 11 12 13 14 15
C F F F F G A A
C F F F A A A
A A A A A
C F F F F A A A
6
COST:
45.98
Figure A. 53: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
C I I I F G G G A
3 C 7 8
9
10 11 12 13 14 15
C F F F F G A A
C F F F A A A
A A A A A
C F F F F A A A
7
COST:
Figure A. 54: Subdepartmental Placement
46.85
95 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
I I I I G G G
C I I I F G G G A
3 C 7 8
9
10 11 12 13 14 15
C C F F F F G A A
C F F F A A A
A A A A A
C F F F F A A A
5
COST:
50.86
Figure A. 55: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
C I I I I G G G
C I I I F G G G A
3 C 7 8
9
10 11 12 13 14 15
C C F F F F G A A
C F F F A A A
A A A A A
C F F F F A A A
8
COST:
Figure A. 56: Subdepartmental Placement
53.82
96 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
C I I I I G G G
C I I I F G G G A
4 C 7 8
9
10 11 12 13 14 15
C C F F F F G A A
C F F F A A A
A A A A A
C C F F F F A A A
9
COST:
55.78
Figure A. 57: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
C I I I I G G G
C I I I F G G G A
2 C 7 8
9
10 11 12 13 14 15
C C F F F F G A A
C C F F F A A A
A A A A A
C C F F F F A A A
7
COST:
Figure A. 58: Subdepartmental Placement
63.53
97 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
C I I I I G G G
C I I I F G G G A
2 C 7 8
9
10 11 12 13 14 15
C C C F F F F G A A
C C F F F A A A
A A A A A
C C F F F F A A A
6
COST:
64.67
Figure A. 59: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
C I I I I G G G
C C I I I F G G G A
3 C 7 8
9
10 11 12 13 14 15
C C C F F F F G A A
C C F F F A A A
A A A A A
C C F F F F A A A
9
COST:
Figure A. 60: Subdepartmental Placement
67.80
98 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
C I I I I G G G
C C I I I F G G G A
2 C 7 8
9
10 11 12 13 14 15
C C C F F F F G A A
C C C F F F A A A
A A A A A
C C F F F F A A A
8
COST:
70.56
Figure A. 61: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
C I I I I G G G
C C I I I F G G G A
6 J 7 8 C C C F F F F G A A
C C C F F F F A A A
10
COST:
66.34
9
10 11 12 13 14 15
C C C F F F A A A
A A A A A
Figure A. 62: Subdepartmental Placement
99 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
C I I I I G G G
C C I I I F G G G A
8 J 7 8 C C C F F F F G A A
C C C F F F F A A A
11
COST:
71.64
9
10 11 12 13 14 15
C C C F F F A A A
J A A A A A
Figure A. 63: Subdepartmental Placement
The above figure illustrates that the lowest cost location of the placement of later departments is more dependent upon its benefit to the overall layout as opposed to other subdepartments within the same department. The first two subdepartments of J are assigned to two locations that are not adjacent and that do not share a vertex.
100 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
C I I I I G G G
C C I I I F G G G A
7 J 7 8 C C C F F F F G A A
C C C F F F F A A A
11
COST:
73.49
9
10 11 12 13 14 15
C C C F F F A A A
J A A A A A
J
Figure A. 64: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
C I I I I G G G
C C I I I F G G G A
9 J 7 8 C C C F F F F G A A
C C C F F F F A A A
11
COST:
75.14
9
10 11 12 13 14 15
C C C F F F A A A
J A A A A A
J J
Figure A. 65: Subdepartmental Placement
101 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
C I I I I G G G
C C I I I F G G G A
5 J 7 8 C C C F F F F G A A
C C C F F F F A A A
10
COST:
79.46
9
10 11 12 13 14 15
C C C F F F A A A
J A A A A A
J J J
Figure A. 66: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
C I I I I G G G
C C I I I F G G G A
6 J 7 8 C C C F F F F G A A
C C C F F F F A A A
11
COST:
81.49
9
10 11 12 13 14 15
C C C F F F A A A
J J A A A A A
J J J
Figure A. 67: Subdepartmental Placement
102 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
C I I I I G G G
C C I I I F G G G A
10 J 7 8 C C C F F F F G A A
C C C F F F F A A A
11
COST:
87.75
9
10 11 12 13 14 15
C C C F F F A A A
J J A A A A A
J J J J
Figure A. 68: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
C I I I I G G G
C C I I I F G G G A
8 J 7 8 C C C F F F F G A A
C C C F F F F A A A
12
COST:
92.19
9
10 11 12 13 14 15
C C C F F F A A A
J J A A A A A
J J J J J
Figure A. 69: Subdepartmental Placement
103 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
C I I I I G G G
C C I I I F G G G A
7 J 7 8 C C C F F F F G A A
12
C C C F F F F A A A
93.88
COST:
9
10 11 12 13 14 15
C C C F F F A A A
J J A A A A A
J J J J J
J
Figure A. 70: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I
I I I I G G
C I I I I G G G
7 E 6 7
8
9
10 11 12 13 14 15
C C I I I F G G G A
C C C F F F F A A A
C C C F F F A A A
J J A A A A A
C C C F F F F G A A
3
87.67
COST:
J J J J J
J J
Figure A. 71: Subdepartmental Placement
104 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I E
I I I I G G
C I I I I G G G
C C I I I F G G G A
8 E 7 8
9
10 11 12 13 14 15
C C C F F F F G A A
C C C F F F A A A
J J A A A A A
C C C F F F F A A A
3
COST:
J J J J J
90.29
J J
Figure A. 72: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I E E
I I I I G G
C I I I I G G G
C C I I I F G G G A
10 E 7 8
9
10 11 12 13 14 15
C C C F F F F G A A
C C C F F F A A A
J J A A A A A
C C C F F F F A A A
4
COST:
J J J J J
J J
Figure A. 73: Subdepartmental Placement
93.11
105 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I E E
I I I I G G E
C I I I I G G G
C C I I I F G G G A
11 E 7 8
9
10 11 12 13 14 15
C C C F F F F G A A
C C C F F F A A A
J J A A A A A
C C C F F F F A A A
5
COST:
J J J J J
96.25
J J
Figure A. 74: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I E E
I I I I G G E
C I I I I G G G E
C C I I I F G G G A
9 E 7 8
9
10 11 12 13 14 15
C C C F F F F G A A
C C C F F F A A A
J J A A A A A
C C C F F F F A A A
3
COST:
J J J J J
J J
Figure A. 75: Subdepartmental Placement
99.01
106 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I E E E
I I I I G G E
C I I I I G G G E
C C I I I F G G G A
11 E 7 8
9
10 11 12 13 14 15
C C C F F F F G A A
C C C F F F A A A
J J A A A A A
C C C F F F F A A A
4
COST:
J J J J J
106.72
J J
Figure A. 76: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I E E E
I I I I G G E E
C I I I I G G G E
C C I I I F G G G A
10 E 7 8
9
10 11 12 13 14 15
C C C F F F F G A A
C C C F F F A A A
J J A A A A A
C C C F F F F A A A
3
COST:
J J J J J
108.12
J J
Figure A. 77: Subdepartmental Placement
107 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I E E E E
I I I I G G E E
C I I I I G G G E
C C I I I F G G G A
12 E 7 8
9
10 11 12 13 14 15
C C C F F F F G A A
C C C F F F A A A
J J A A A A A
C C C F F F F A A A
6
COST:
J J J J J
112.76
J J
Figure A. 78: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I E E E E
I I I I G G E E
C I I I I G G G E
C C I I I F G G G A E
12 E 7 8
9
10 11 12 13 14 15
C C C F F F F G A A
C C C F F F A A A
J J A A A A A
C C C F F F F A A A
7
COST:
J J J J J
113.54
J J
Figure A. 79: Subdepartmental Placement
108 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I E E E E
I I I I G G E E
C I I I I G G G E
C C I I I F G G G A E
12 E 7 8 C C C F F F F G A A E
C C C F F F F A A A
5
COST:
118.15
9
10 11 12 13 14 15
C C C F F F A A A
J J A A A A A
J J J J J
J J
Figure A. 80: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I E E E E
I I I I G G E E
C I I I I G G G E E
C C I I I F G G G A E
4 B 7 8 C C C F F F F G A A E
C C C F F F F A A A
10
COST:
118.24
9
10 11 12 13 14 15
C C C F F F A A A
J J A A A A A
J J J J J
J J
Figure A. 81: Subdepartmental Placement
109 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I E E E E
I I I I G G E E
C I I I I G G G E E
C C I I I F G G G A E
3 B 7 8 C C C F F F F G A A E
C C C F F F F A A A
4
COST:
122.30
9
10 11 12 13 14 15
C C C F F F A A A
B J J A A A A A
J J J J J
J J
Figure A. 82: Subdepartmental Placement
The previous figure shows a complete separation of two subdepartments. The first subdepartment of B was assigned to the position at row four and column ten while the second was assigned to the position at row three column four. These locations are at opposite sides of the layout. As more subdepartments of B are placed, it will become increasingly less costly to assign the subdepartments of B to locations close to one another.
110 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I I I E E E E
B I I I I G G E E
C I I I I G G G E E
C C I I I F G G G A E
7 B 7 8 C C C F F F F G A A E
C C C F F F F A A A
2
COST:
127.86
9
10 11 12 13 14 15
C C C F F F A A A
B J J A A A A A
J J J J J
J J
Figure A. 83: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B
I I I E E E E
B I I I I G G E E
C I I I I G G G E E
C C I I I F G G G A E
6 B 7 8 C C C F F F F G A A E
C C C F F F F A A A
2
COST:
129.11
9
10 11 12 13 14 15
C C C F F F A A A
B J J A A A A A
J J J J J
J J
Figure A. 84: Subdepartmental Placement
111 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B
I I I E E E E
B I I I I G G E E
C I I I I G G G E E
C C I I I F G G G A E
8 B 7 8 C C C F F F F G A A E
C C C F F F F A A A
2
COST:
133.14
9
10 11 12 13 14 15
C C C F F F A A A
B J J A A A A A
J J J J J
J J
Figure A. 85: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B
I I I E E E E
B I I I I G G E E
C I I I I G G G E E
C C I I I F G G G A E
5 B 7 8 C C C F F F F G A A E
C C C F F F F A A A
2
COST:
136.84
9
10 11 12 13 14 15
C C C F F F A A A
B J J A A A A A
J J J J J
J J
Figure A. 86: Subdepartmental Placement
112 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B
I I I E E E E
B I I I I G G E E
C I I I I G G G E E
C C I I I F G G G A E
9 B 7 8 C C C F F F F G A A E
C C C F F F F A A A
2
COST:
144.89
9
10 11 12 13 14 15
C C C F F F A A A
B J J A A A A A
J J J J J
J J
Figure A. 87: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B
I I I E E E E
B I I I I G G E E
C I I I I G G G E E
C C I I I F G G G A E
3 B 7 8 C C C F F F F G A A E
C C C F F F F A A A
3
COST:
149.86
9
10 11 12 13 14 15
C C C F F F A A A
B J J A A A A A
J J J J J
J J
Figure A. 88: Subdepartmental Placement
113 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B
B I I I E E E E
B I I I I G G E E
C I I I I G G G E E
C C I I I F G G G A E
2 B 7 8 C C C F F F F G A A E
C C C F F F F A A A
5
COST:
151.82
9
10 11 12 13 14 15
C C C F F F A A A
B J J A A A A A
J J J J J
J J
Figure A. 89: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B
B I I I E E E E
B I I I I G G E E
B C I I I I G G G E E
C C I I I F G G G A E
4 B 7 8 C C C F F F F G A A E
C C C F F F F A A A
2
COST:
154.26
9
10 11 12 13 14 15
C C C F F F A A A
B J J A A A A A
J J J J J
J J
Figure A. 90: Subdepartmental Placement
114 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B
B I I I E E E E
B I I I I G G E E
B C I I I I G G G E E
C C I I I F G G G A E
2 B 7 8 C C C F F F F G A A E
C C C F F F F A A A
4
COST:
161.05
9
10 11 12 13 14 15
C C C F F F A A A
B J J A A A A A
J J J J J
J J
Figure A. 91: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B
B I I I E E E E
B B I I I I G G E E
B C I I I I G G G E E
C C I I I F G G G A E
12 D 7 8 C C C F F F F G A A E
C C C F F F F A A A
8
COST:
169.06
9
10 11 12 13 14 15
C C C F F F A A A
B J J A A A A A
J J J J J
J J
Figure A. 92: Subdepartmental Placement
115 After all of the subdepartments of B have been placed, a departmental separation exists. At least one subdepartment of B is not connected to all of the others through adjacent edges or vertices. Since the ranking of viscosities determines order, it is important that if a department has a need for adjacency, it is given a very high alpha value. The placement of department D in the following figures shows that the probability for another departmental separation increases after the first occurrence. Department D is attracted to B which is located in two separate locations. Therefore, it will be drawn each way.
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B
B I I I E E E E
B B I I I I G G E E
B C I I I I G G G E E
C C I I I F G G G A E
5 D 7 8 C C C F F F F G A A E
C C C F F F F A A A D
11
COST:
175.56
9
10 11 12 13 14 15
C C C F F F A A A
B J J A A A A A
J J J J J
J J
Figure A. 93: Subdepartmental Placement
116 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B
B I I I E E E E
B B I I I I G G E E
B C I I I I G G G E E
C C I I I F G G G A E
12 D 7 8 C C C F F F F G A A E
C C C F F F F A A A D
9
COST:
183.19
9
10 11 12 13 14 15
C C C F F F A A A
B J J A A A A A
D J J J J J
J J
Figure A. 94: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B
B I I I E E E E
B B I I I I G G E E
B C I I I I G G G E E
C C I I I F G G G A E
11 D 7 8
9
10 11 12 13 14 15
C C C F F F F G A A E
C C C F F F A A A D
B J J A A A A A
C C C F F F F A A A D
3
COST:
D J J J J J
188.79
J J
Figure A. 95: Subdepartmental Placement
117 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B
B I I I E E E E D
B B I I I I G G E E
B C I I I I G G G E E
C C I I I F G G G A E
12 D 7 8
9
10 11 12 13 14 15
C C C F F F F G A A E
C C C F F F A A A D
B J J A A A A A
C C C F F F F A A A D
4
COST:
D J J J J J
193.90
J J
Figure A. 96: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E
10 D 7 8
9
10 11 12 13 14 15
C C C F F F F G A A E
C C C F F F A A A D
B J J A A A A A
C C C F F F F A A A D
2
COST:
D J J J J J
196.04
J J
Figure A. 97: Subdepartmental Placement
118 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E
13 D 7 8
9
10 11 12 13 14 15
C C C F F F F G A A E
C C C F F F A A A D
B J J A A A A A
C C C F F F F A A A D
7
COST:
D J J J J J
206.17
J J
Figure A. 98: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E
13 D 7 8 C C C F F F F G A A E D
C C C F F F F A A A D
6
COST:
207.08
9
10 11 12 13 14 15
C C C F F F A A A D
B J J A A A A A
D J J J J J
J J
Figure A. 99: Subdepartmental Placement
119 The placement of department H is shown in the figures below. The subdepartments of H are placed first in nonadjacent locations according to their maximum benefit to the total layout. However, there are enough subdepartments of H due to its size to fill in the gaps such that all subdepartments of H end up sharing a side or a vertex with one another.
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
6 H 7 8 C C C F F F F G A A E D
C C C F F F F A A A D
12
COST:
223.06
9
10 11 12 13 14 15
C C C F F F A A A D
B J J A A A A A
D J J J J J
J J
Figure A. 100: Subdepartmental Placement
120 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
4 H 7 8 C C C F F F F G A A E D
C C C F F F F A A A D
11
COST:
225.17
9
10 11 12 13 14 15
C C C F F F A A A D
B J J A A A A A
D J J J J J
H J J
Figure A. 101: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
3 H 7 8 C C C F F F F G A A E D
C C C F F F F A A A D
10
COST:
227.14
9
10 11 12 13 14 15
C C C F F F A A A D
B J J A A A A A
H D J J J J J
H J J
Figure A. 102: Subdepartmental Placement
121 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
9 H 7 8 C C C F F F F G A A E D
C C C F F F F A A A D
12
COST:
232.29
9
10 11 12 13 14 15
C C C F F F A A A D
H B J J A A A A A
H D J J J J J
H J J
Figure A. 103: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
11 H 7 8 C C C F F F F G A A E D
C C C F F F F A A A D
11
COST:
238.33
9
10 11 12 13 14 15
C C C F F F A A A D
H B J J A A A A A
H D J J J J J
H J J H
Figure A. 104: Subdepartmental Placement
122 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
12 H 7 8 C C C F F F F G A A E D
C C C F F F F A A A D
10
COST:
242.41
9
10 11 12 13 14 15
C C C F F F A A A D
H B J J A A A A A
H D J J J J J H
H J J H
Figure A. 105: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
5 H 7 8 C C C F F F F G A A E D
C C C F F F F A A A D
12
COST:
247.56
9
10 11 12 13 14 15
C C C F F F A A A D
H B J J A A A A A H
H D J J J J J H
H J J H
Figure A. 106: Subdepartmental Placement
123 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
10 H 7 8 C C C F F F F G A A E D
C C C F F F F A A A D
12
COST:
251.26
9
10 11 12 13 14 15
C C C F F F A A A D
H B J J A A A A A H
H D J J J J J H
H H J J H
Figure A. 107: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
13 H 7 8 C C C F F F F G A A E D
C C C F F F F A A A D
8
COST:
257.49
9
10 11 12 13 14 15
C C C F F F A A A D
H B J J A A A A A H
H D J J J J J H
H H J J H H
Figure A. 108: Subdepartmental Placement
124 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
13 H 7 8 C C C F F F F G A A E D
C C C F F F F A A A D H
9
COST:
266.03
9
10 11 12 13 14 15
C C C F F F A A A D
H B J J A A A A A H
H D J J J J J H
H H J J H H
Figure A. 109: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
12 H 7 8 C C C F F F F G A A E D
C C C F F F F A A A D H
11
COST:
271.64
9
10 11 12 13 14 15
C C C F F F A A A D H
H B J J A A A A A H
H D J J J J J H
H H J J H H
Figure A. 110: Subdepartmental Placement
125 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
11 H 7 8 C C C F F F F G A A E D
C C C F F F F A A A D H
12
COST:
275.45
9
10 11 12 13 14 15
C C C F F F A A A D H
H B J J A A A A A H
H D J J J J J H H
H H J J H H
Figure A. 111: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
8 H 7 8 C C C F F F F G A A E D
C C C F F F F A A A D H
13
COST:
278.34
9
10 11 12 13 14 15
C C C F F F A A A D H
H B J J A A A A A H
H D J J J J J H H
H H J J H H H
Figure A. 112: Subdepartmental Placement
126 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
7 H 7 8 C C C F F F F G A A E D
C C C F F F F A A A D H
13
COST:
280.90
9
10 11 12 13 14 15
C C C F F F A A A D H
H B J J A A A A A H
H D J J J J J H H
H H J J H H H
H
Figure A. 113: Subdepartmental Placement
Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
9 H 7 8 C C C F F F F G A A E D
C C C F F F F A A A D H
13
COST:
283.98
9
10 11 12 13 14 15
C C C F F F A A A D H
H B J J A A A A A H
H D J J J J J H H
H H J J H H H
H H
Figure A. 114: Subdepartmental Placement
127 Next Location Max Visc. Dept. 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
6 H 7 8 C C C F F F F G A A E D
C C C F F F F A A A D H
13
COST:
291.64
9
10 11 12 13 14 15
C C C F F F A A A D H
H B J J A A A A A H
H D J J J J J H H
H H J J H H H
H H H
Figure A. 115: Subdepartmental Placement
The algorithm is complete with the placement of the final subdepartment. The resultant layout is shown below in Figure A.115.
128 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2
3
4
5
6
7
8
9
10 11 12 13 14 15
B B B B B B D
B I I I E E E E D
B B I I I I G G E E D
B C I I I I G G G E E
C C I I I F G G G A E D
C C C F F F F G A A E D
C C C F F F F A A A D H
C C C F F F A A A D H
H B J J A A A A A H
H D J J J J J H H
H H J J H H H
H H H H
Figure A. 116: Subdepartmental Placement
129 APPENDIX B Experimental Data Table B.1: Ten Department Problem 1 Data A B C D E F G H I J
A
B
C
D
E
F
G
H
I
J
SIZE
0.654
0.287
0.107
0.189
0.098
0.3
0.204
0.143
0.348
0.46
14
0.287
0.575
0.041
0.358
0.188
0.34
0.07
0.083
0.05
0.241
11
0.107
0.041
0.864
0.465
0.061
0.497
0.137
0.375
0.433
0.279
12
0.189
0.358
0.465
0.921
0.322
0.196
0.152
0.416
0.14
0.147
8
0.098
0.188
0.061
0.322
0.592
0.348
0.273
0.291
0.132
0.143
10
0.3
0.34
0.497
0.196
0.348
0.632
0.437
0.095
0.484
0.052
12
0.204
0.07
0.137
0.152
0.273
0.437
0.538
0.267
0.348
0.237
9
0.143
0.083
0.375
0.416
0.291
0.095
0.267
0.662
0.206
0.106
16
0.348
0.05
0.433
0.14
0.132
0.484
0.348
0.206
0.695
0.048
14
0.46
0.241
0.279
0.147
0.143
0.052
0.237
0.106
0.048
0.836
9
Table B.2: Ten Department Problem 2 Data A B C D E F G H I J
A
B
C
D
E
F
G
H
I
J
SIZE
0.807
0.412
0.304
0.367
0.482
0.352
0.114
0.131
0.32
0.185
14
0.412
0.705
0.291
0.233
0.443
0.029
0.225
0.259
0.154
0.134
11
0.304
0.291
0.72
0.214
0.354
0.326
0.33
0.172
0.31
0.02
12
0.367
0.233
0.214
0.894
0.134
0.341
0.472
0.271
0.055
0.236
8
0.482
0.443
0.354
0.134
0.507
0.43
0.04
0.259
0.367
0.005
10
0.352
0.029
0.326
0.341
0.43
0.981
0.385
0.108
0.093
0.141
12
0.114
0.225
0.33
0.472
0.04
0.385
0.544
0.039
0.202
0.225
9
0.131
0.259
0.172
0.271
0.259
0.108
0.039
0.858
0.071
0.055
16
0.32
0.154
0.31
0.055
0.367
0.093
0.202
0.071
0.859
0.367
14
0.185
0.134
0.02
0.236
0.005
0.141
0.225
0.055
0.367
0.647
9
130 Table B.3: Ten Department Problem 3 Data A B C D E F G H I J
A
B
C
D
E
F
G
H
I
J
SIZE
0.783
0.043
0.005
0.498
0.42
0.464
0.424
0.308
0.005
0.437
14
0.043
0.663
0.357
0.248
0.343
0.452
0.381
0.213
0.302
0.162
11
0.005
0.357
0.774
0.343
0.019
0.313
0.226
0.303
0.291
0.266
12
0.498
0.248
0.343
0.641
0.289
0.147
0.285
0.356
0.438
0.194
8
0.42
0.343
0.019
0.289
0.679
0.017
0.17
0.447
0.447
0.364
10
0.464
0.452
0.313
0.147
0.017
0.927
0.156
0.455
0.048
0.008
12
0.424
0.381
0.226
0.285
0.17
0.156
0.875
0.422
0.197
0.413
9
0.308
0.213
0.303
0.356
0.447
0.455
0.422
0.608
0.35
0.399
16
0.005
0.302
0.291
0.438
0.447
0.048
0.197
0.35
0.897
0.096
14
0.437
0.162
0.266
0.194
0.364
0.008
0.413
0.399
0.096
0.693
9
Table B.4: Fifteen Department Data Part I A
B
C
D
E
F
G
H
A
0.535
0.075
0.473
0.273
0.024
0.055
0.468
0.138
B
0.075
0.651
0.475
0.164
0.338
0.415
0.104
0.498
C
0.473
0.475
0.906
0.062
0.241
0.346
0.068
0.130
D
0.273
0.164
0.062
0.765
0.225
0.142
0.093
0.204
E
0.024
0.338
0.241
0.225
0.560
0.224
0.092
0.186
F
0.055
0.415
0.346
0.142
0.224
0.784
0.394
0.133
G
0.468
0.104
0.068
0.093
0.092
0.394
0.759
0.166
H
0.138
0.498
0.130
0.204
0.186
0.133
0.166
0.882
I
0.267
0.019
0.216
0.042
0.149
0.070
0.298
0.046
J
0.370
0.266
0.398
0.013
0.387
0.202
0.474
0.137
K
0.306
0.038
0.067
0.225
0.187
0.451
0.374
0.072
L
0.038
0.327
0.411
0.170
0.159
0.352
0.423
0.186
M
0.498
0.401
0.020
0.363
0.091
0.273
0.338
0.315
N
0.062
0.152
0.160
0.073
0.011
0.484
0.369
0.215
O
0.182
0.050
0.008
0.212
0.173
0.243
0.178
0.374
131 Table B.5: Fifteen Department Data Part II I
J
K
L
M
N
O
SIZE
A
0.267
0.370
0.306
0.038
0.498
0.062
0.182
6
B
0.019
0.266
0.038
0.327
0.401
0.152
0.050
7
C
0.216
0.398
0.067
0.411
0.020
0.160
0.008
8
D
0.042
0.013
0.225
0.170
0.363
0.073
0.212
4
E
0.149
0.387
0.187
0.159
0.091
0.011
0.173
9
F
0.070
0.202
0.451
0.352
0.273
0.484
0.243
6
G
0.298
0.474
0.374
0.423
0.338
0.369
0.178
5
H
0.046
0.137
0.072
0.186
0.315
0.215
0.374
10
I
0.684
0.195
0.109
0.351
0.486
0.153
0.178
12
J
0.195
0.929
0.358
0.254
0.388
0.236
0.284
8
K
0.109
0.358
0.931
0.269
0.388
0.040
0.119
10
L
0.351
0.254
0.269
0.740
0.371
0.041
0.399
4
M
0.486
0.388
0.388
0.371
0.758
0.480
0.043
9
N
0.153
0.236
0.040
0.041
0.480
0.843
0.455
6
O
0.178
0.284
0.119
0.399
0.043
0.455
0.914
11
132 Table B.6: Twenty Department Data Part I A
B
C
D
E
F
G
H
I
J
A
0.861
0.094
0.267
0.252
0.106
0.165
0.059
0.002
0.231
0.464
B
0.094
0.932
0.285
0.117
0.198
0.486
0.056
0.019
0.006
0.110
C
0.267
0.285
0.632
0.253
0.385
0.345
0.394
0.019
0.408
0.324
D
0.252
0.117
0.253
0.583
0.034
0.134
0.100
0.277
0.091
0.323
E
0.106
0.198
0.385
0.034
0.539
0.385
0.366
0.254
0.350
0.177
F
0.165
0.486
0.345
0.134
0.385
0.726
0.437
0.352
0.104
0.249
G
0.059
0.056
0.394
0.100
0.366
0.437
0.886
0.433
0.124
0.490
H
0.002
0.019
0.019
0.277
0.254
0.352
0.433
0.746
0.392
0.408
I
0.231
0.006
0.408
0.091
0.350
0.104
0.124
0.392
0.596
0.199
J
0.464
0.110
0.324
0.323
0.177
0.249
0.490
0.408
0.199
0.514
K
0.298
0.203
0.169
0.083
0.475
0.486
0.044
0.309
0.217
0.300
L
0.243
0.376
0.491
0.451
0.294
0.225
0.431
0.102
0.335
0.006
M
0.356
0.177
0.415
0.235
0.074
0.415
0.439
0.236
0.330
0.344
N
0.410
0.461
0.096
0.222
0.405
0.296
0.091
0.174
0.453
0.057
O
0.483
0.309
0.154
0.149
0.214
0.029
0.401
0.192
0.330
0.284
P
0.487
0.442
0.415
0.151
0.198
0.269
0.062
0.065
0.213
0.084
Q
0.026
0.220
0.202
0.065
0.178
0.164
0.335
0.141
0.188
0.445
R
0.179
0.386
0.173
0.067
0.098
0.474
0.336
0.440
0.440
0.089
S
0.018
0.384
0.451
0.126
0.138
0.014
0.131
0.387
0.484
0.317
T
0.057
0.027
0.479
0.277
0.094
0.172
0.328
0.489
0.401
0.271
133 Table B.7: Twenty Department Data Part II K
L
M
N
O
P
Q
R
S
T
A
SIZE
0.298
0.243
0.356
0.410
0.483
0.487
0.026
0.179
0.018
0.057
7
B
0.203
0.376
0.177
0.461
0.309
0.442
0.220
0.386
0.384
0.027
7
C
0.169
0.491
0.415
0.096
0.154
0.415
0.202
0.173
0.451
0.479
4
D
0.083
0.451
0.235
0.222
0.149
0.151
0.065
0.067
0.126
0.277
6
E
0.475
0.294
0.074
0.405
0.214
0.198
0.178
0.098
0.138
0.094
4
F
0.486
0.225
0.415
0.296
0.029
0.269
0.164
0.474
0.014
0.172
9
G
0.044
0.431
0.439
0.091
0.401
0.062
0.335
0.336
0.131
0.328
4
H
0.309
0.102
0.236
0.174
0.192
0.065
0.141
0.267
0.387
0.489
5
I
0.217
0.335
0.330
0.453
0.330
0.213
0.188
0.440
0.484
0.401
7
J
0.300
0.006
0.344
0.057
0.284
0.084
0.445
0.089
0.317
0.271
4
K
0.506
0.279
0.397
0.226
0.006
0.253
0.284
0.224
0.255
0.264
5
L
0.279
0.832
0.222
0.151
0.356
0.234
0.499
0.150
0.346
0.296
5
M
0.397
0.222
0.851
0.012
0.121
0.077
0.425
0.250
0.346
0.060
6
N
0.226
0.151
0.012
0.955
0.076
0.410
0.385
0.220
0.025
0.269
4
O
0.006
0.356
0.121
0.076
0.681
0.364
0.132
0.248
0.292
0.431
8
P
0.253
0.234
0.077
0.410
0.364
0.625
0.197
0.331
0.435
0.482
9
Q
0.284
0.499
0.425
0.385
0.132
0.197
0.954
0.230
0.104
0.484
7
R
0.224
0.150
0.250
0.220
0.248
0.331
0.230
0.614
0.254
0.103
6
S
0.255
0.346
0.346
0.025
0.292
0.435
0.104
0.254
0.696
0.036
4
T
0.264
0.296
0.060
0.269
0.431
0.482
0.484
0.103
0.036
0.683
4
