Division of Research School of Business Administration LAYOUT DESIGN FOR FLEXIBLE MANUFACIURING SYSTEMS Working Paper #593 Ram Rachamadugu The University of Michigan December 1988 and Bharat K. The University Kaku of Arizona FOR DISCUSSION PURPOSES ONLY None of this material is to be quoted or reproduced without the expressed permission of the Division of Research Copyright 1989 University of Michigan School of Business Administration Ann Arbor, Michigan 48109

Abstract We model the layout design problem for Flexible Manufacturing Systems as a Quadratic Assignment Problem (QAP). Such systems include machines of different dimensions separated by some required clearance between them; this means that distances between predefined locations cannot be used as in the traditional facilities layout problem (FLP). We consider the two most commonly used configurations-loop conveyor and lineartrack conveyor systems-and show how the design problem can be modified to fit the QAP formulation. A heuristic method for the facilities layout problem is specialized to solve these problems. Computational testing compares results obtained by these procedures to optimal solutions where possible, and to results published in the literature for larger problems. The procedures find optimal or near-optimal solutions for smaller problems, and significantly improved solutions, as compared to published results, for larger problems. Manufacturers of discrete parts face increasing demands for small- to mediumsized lots of customized products, requiring a production process which can provide flexibility as well as economies. A Flexible Manufacturing System (FMS) can offer such a blend of advantages. A typical flexible manufacturing system consists of several processing stations (general purpose machining centers and perhaps some specialized machines) connected by an automated material handling system. Parts are loaded at load/unload stations, and once loaded are automatically routed to the workstations needed to complete their processing. The routings, as well as the operations and tooling required at each workstation, will differ for different parts. The job of coordinating and controlling parts movement and processing is done by computer. This combination of direct numerical control machining with automated material handling enables such systems to machine different parts simultaneously, in any sequence, and even use alternate routings in case of breakdown or overloading at any machine. Detailed 1

descriptions and discussions can be found in several sources, e.g. Black (1983), Browne et al. (1984), Buzacott and Shanthikumar (1980), Groover (1980), and Stecke (1985). 1 Layout design for FMS Existing research in FMS focuses on the general goals of maximization of the production rate and minimization of the lead times. A review of the literature on FMS shows that the important issue of facilities layout design has been largely ignored. We are aware of only the following efforts in this area: Afentakis (1986,1987) has developed graph-theoretic based heuristic methods to design layouts (the second paper concentrates on loop-conveyor systems which are described below), while Heragu and Kusiak (1988) have developed constructive heuristics for the problem. In this work, we study the problem of facilities layout design for FMSs using a quadratic assignment problem formulation. 1.1 System Description We consider a system in which parts are processed in some fixed ratio. This situation is typical of a fabrication process that feeds a downstream assembly process. Parts enter and leave the system through a load/unload station, and the sequence of operations to be performed on a part is specified through serial precedence requirements. The objective is to design a layout that will minimize material handling. We consider two commonly used configurations for FMS layout (see Figure 1). The first employs a loop conveyor, with the machines located around this loop. The second uses a linear-track material handling system with machines located either on one side or both sides of it. Both these configurations 2

are flexible with respect to access to any machine from any other, but the former allows movement in only one direction around the loop while the latter moves material in both directions along its linear track. We treat a load/unload station as an additional machine (facility) in this work. In all of these cases, if the process route is fixed for each part (including its entry and exit points) then the problem can be formulated as a Quadratic Assignment Problem (QAP) as explained in the next section. 1.2 Quadratic Assignment Problem Formulation Consider an FMS with n machines (including load/unload station/s) to be assigned to as many locations. We define the following terms and variables: fij = the number of loads moving from machine i to machine j dij = the distance from location i to location j cij = the fixed cost of installing machine i in location j p(i) = the location to which machine i is assigned Then the objective is to find a one-to-one assignment of facilities to location so as to n n n Minimize cip(i) + E E fij dp(i)p(j) (1) it= i=1 j=1 1.3 Handling unequal area requirements for machines The layout problem for flexible manufacturing systems (and other machine layout problems) can be different from the traditional facilities layout problem in one important respect. As pointed out by Heragu and Kusiak (1988), machine sizes are generally not equal, and if the distance between two machines is determined by their respective dimensions and the clearance required between them, 3

I 4 I 5 31 4 3 2 1 LI LIP I 6 I L/UL I 7 1 I L/UL a. Loop conveyor Figure 1: Types of FMS layout b. Linear track 4

then distances between locations are neither equal nor can be predetermined. We show that the interaction and distance data for the two cases we study can be manipulated to fit the QAP formulation given above in two ways. These are summarized below. Loop systems. We begin by looking at loop conveyor systems with one load/unload (L/UL) station and a constant distance C between adjacent machines. Two modifications can be made to the QAP formulation above. First, the distance between any two locations can be defined as follows: d C(q -p) if q>p dpq C(n-p+q) ifq<p This simply means that to go from a higher-numbered location to a lowernumbered location, a part must go past the L/UL station and start a new circuit. Second, if the location of the L/UL station is fixed, we can number it as facility n, and add the constraint: Xnn = 1 Define a part link movement as one part traveling one link (the distance between adjacent machines), while a part circuit is defined as a part completing one circuit of the loop, starting and ending at the L/UL station. Proposition 1. In a loop-conveyor system with one entry and exit point, minimizing part link movement is equivalent to minimizing part circuit movement. Proof. Consider any specific assignment of machines to locations, with the load/unload station at location n. Without loss of generality, reindex the (n- 1) machines such that machine index coincides with location index. As defined earlier, fij is the flow from facility i to facility j. Also, from the description of the system above, it is clear that: fin = number of parts whose last operation is performed on machine i fnj = number of parts whose first operation is performed on machine j 5

Now consider a transformation of the flow data as follows, where the transformed flows will be represented by Fij: Case I: i,j $ n, i < j Fij = fij Case II: i,j $ n, i > j Fij- = 0 Fin = fin + E fi * S J i,jcn, i>j Fnj = fnj + E fi i,jn, i>j In the transformed system, any flow from a higher-numbered location to a lowernumbered location (i to j in Case II above) is converted into two componentsthe first terminates at location n (the L/UL station) and the second equivalent flow originates at n and terminates at j. Since travel distances can be considered additive (for i > j, dij = din + dj), this does not alter the material flow load for the given machine to location assignments. In this transformed system, flow is always from lower-indexed machines to higher-indexed machines, except for the L/UL station. We can think of a part traveling past the L/UL station as two distinct parts, one exiting the system at station n, and another entering the system at the same point. Further, since the number of parts entering the system must equal the number of parts exiting the system in any given time period on the average, flow conservation requires that n-1 n-1 Fin = Fn (2) i=l j=1 6

Each term is simply the total number of parts (including those defined by the above transformation) that travel around the loop for exactly one circuit. Then the material handling cost is given by n-1 Fin x loop length = part circuits x (Cn) (3) i=l Thus for any given assignment, the material handling cost is proportional to the number of part circuits. o Proposition 2. The part-circuit measure for material handling cost is valid even if machines are not equally spaced in a circular layout. Proof. The proof of this proposition follows immediately from the proof for Proposition 1. To see this, simply replace Cn as the expression for loop length in equation 3 by the term: n-1 dnl + dii+ i=l This means that no assumption is made concerning inter-machine distances; we only require distances around the loop to be additive. o Afentakis (1987) proved Proposition 1 using graph theoretic concepts. Our proof is simpler, and through its extension to Proposition 2, we also establish the fact that the part-circuit measure is equally valid for unequal spacing of machines in the circular layout. The objective changes from minimizing part links traveled to minimizing part circuits traveled, which we have shown to be equivalent problems for a loop conveyor. Identical solution methods can be applied to both formulations, but the part-circuit formulation is not dependent on the distances between locations; the cost of a solution depends only on the sequence in which machines are placed around the loop. In other words, it is not necessary that the distances between machines be the same, or even known beforehand. 7

Linear-track systems. A different approach is used for linear-track systems. The orientation of any machine with respect to the travel path of material is known, i.e., whether a length or a width will be parallel to the track. These dimensions can be divided into some convenient module size. The modules of a machine can be kept together in any solution by creating very high artificial flows between them. Locations are all assumed to have dimensions equal to this module size, and now the problem is a standard QAP, though of larger size. It should be stressed here that machines do not have to fit some integer number of modules precisely; a certain amount of expansion or contraction does not affect the solution significantly when the layout is designed to exact dimensions with appropriate clearances added for loading, unloading, safe operation, maintenance, etc., after relative locations have been determined. Kaku, Thompson and Baybars (1988) have discussed in detail the idea of breaking up unequal sized facilities into equal sized modules in the context of layout design of an office building with departments of unequal size. 2 Solution procedures for the layout problem The solution procedures for both loop-conveyor and linear-track systems are based on a heuristic method developed by Kaku, Morton and Thompson (1988) for the general facilities layout problem (FLP) with equal area requirements for all facilities. This method is a combination of a constructive heuristic and exchange improvement, applied to several starting solutions, as explained below. Starting points for the constructive procedure are generated by developing a limited number of nodes at the top levels of a search tree. Facilites are ranked in decreasing order of interactions, and nodes at level one of the tree represent assignments of the first facility in order to locations that minimize the expected value of a completion as computed by the method of Graves and 8

Whinston (1970). Under each node at level one, nodes are saved at level two representing assignments of the second facility in order to free locations, and so on for the number of levels specified. Each node is then a distinct partial solution to the problem, containing as many assignments as the number of levels developed in the tree, and can be used as a starting point for the constructive procedure which builds on this solution by adding assignments with the maximum "regret" or "alternative cost", as computed in the process of calculating the Gilmore-Lawler (1962,1963) lower bound. The completed solutions are subjected to pairwise interchange and the best solutions are saved. These are then subjected to triple-exchange improvement, and the best final solution is saved. The number of nodes saved under each at the next level, the number of levels developed, and the number of solutions saved for application of triple exchange are parameters that can be manipulated to suit the individual application. The tradeoff is better average solution quality against smaller computation times. This procedure has been adapted for use in layout design of Flexible Manufacturing Systems as follows. 2.1 Loop systems Propositions 1 and 2 from the previous section allow us to change the distance matrix and reduce it to a {0,1} matrix with zeros along the diagonal and above it, and ones below the diagonal. The interpretation of this distance matrix is as follows. Movement from the L/UL station to any machine has a cost of one circuit (introduction of a part to the system), but after that the cost of an additional circuit is incurred only if a part goes from a later location in the loop to an earlier one. Two distance matrices for the same loop conveyor FMS are shown in Table 1, one corresponding to the part-link formulation with equal distances of one unit between machines and the other to the part-circuit formulation. 9

To To 0 1 2 3 4 5 6 0 0 0 0 0 0 0 6 0 1 2 3 4 5 1 0 0 0 0 0 0 5 6 0 1 2 3 4 1 1 0 0 0 0 0 From 4 5 6 0 1 2 3 From 11 1 0 0 0 0 3 4 5 6 0 1 2 1111 000 2 3 4 5 6 0 1 1 1 1 0 0 1 2 3 4 5 6 0 1111110 a. Part link b. Part circuit Table 1: Distance matrices for the part link and part circuit formulations The general FLP procedure is used to solve the part-circuit problem, with only one change to the pair-exchange procedure as discussed below. The number of levels developed in the limited search tree is two for smaller problems and three for problems with more than 10 machines; the number of nodes saved under each at the next level is three; and the number of solutions saved for application of triple exchange is one for smaller problems, increasing to three for problems with 20 or more machines. The part circuit formulation lends itself to specialization in the pair-exchange procedure as follows. In the standard version of the pair-exchange procedure used for the QAP, if I is the set of facilities and p(i) is the location to which facility i has been assigned in any given solution, the change in value of the objective function (6) due to the exchange of a pair of facilities i and j is evaluated by the following equation: tij = [(fj k) (dp(i)p(k) - dp(j)p(k) kEZ\{i,J} + (fkj - fki) (dp(k)p(i) -dp(k)p(j)) + (fji - fij) (dp(ip() - d(jp(i) (4) When working with the part circuit formulation, the effect of interchanging i and j can be computed with less effort because we need only consider their 10

interactions with facilities that lie between the two. The cost of interactions with machines that are before or after both i and j in the loop is not affected by the interchange. Let +(k) denote the facility/machine in location k, and assume p(i) < p(j). Then sij = fij - f + Z (fi(k) + fk)j - f+k)i- fj+(k)) (5) p(i)<k<p(j) It should be emphasized here that the new pair-exchange formula does not affect the quality of the solution found; only the computation time is reduced. 2.2 Linear-track systems Two types of linear-track systems are studied: those with machines on only one side of the track, called single-row linear track systems; and those with machines on both sides, called double-row linear track systems. A different kind of manipulation is necessary here to get around the problem of unequal machine sizes and put the problem into the framework of a QAP. First, the procedure for generating starting points for the constructive method has to be changed, because distance data are not available for computing the expected values of completions. Instead, permutations of the first few ordered facilities are used as starting points. The number of machines in each permutation corresponds to the number of levels required in the search tree. For example, if two levels are to be developed, with three nodes saved under each at every level, and if machines are indexed by order of decreasing interactions, then the nine partial solutions generated would be (1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), and (3,4). Each machine is divided into the number of modules corresponding to the dimension (length or width) that is to be parallel to the linear-track material handling system. The size of a module is the greatest common divisor of the set of these dimensions for all machines. The flow (fij) from any module i, 11

belonging to machine ml, to another module j, belonging to machine m2, is calculated by the expression fij = fmlm2//nl n2 where nl and n2 are the number of modules of machines ml and m2, respectively. The flow between modules of a machine is set to some number large enough to keep the modules together in any solution. The size of the QAP to be solved is then the total number of modules created. In the next step, location modules are set up, equal in number and dimension to machine modules. Placing modules of machines in these location modules implies that no clearance is provided between machines at this stage; however, clearances are included when the final solution is constructed. The distances between these location modules can be calculated in a straightforward manner, and they are ordered by increasing total (or equivalently, average) distance to other location modules. A partial solution to the modified problem can now be constructed by matching the modules of machines in the permutation with the first location modules in order. For example, consider the first permutation generated- (1,2). Suppose that the number of modules in machine 1 (indexed by decreasing interactions) is ni and in machine 2 is n2. Then the modules of machine 1 are assigned to the first nl location modules in order, and the modules of machine 2 are assigned to the next n2 location modules. The logic here is to place high-interaction machines in central locations. This partial solution can then be completed by the constructive heuristic, and improved by pairwise interchange. A certain number of the best solutions is stored, and from each of these a solution to the original problem is constructed. The modules of any machine are located in consecutive location modules, and are joined to reconstruct the individual machines. At this stage, the appropriate clearance is added between 12

machines. (Triple exchange is not attempted for linear-track problems.) Thus for each solution saved from the modified problem, we obtain a layout design for the original problem, for which distances between all pairs of machines can be easily calculated. It should be emphasized that these are distances between machines for a given layout, and not distances between clearly defined locations as in the usual FLP. The exact cost of such solutions can be computed and the solution with the least cost is saved. The number of machines in a permutation used to generate a starting point for the constructive heuristic is two for smaller problems and three for problems with eight or more machines; the number of nodes saved under each node at the level just above is three; and the number of solutions saved for reconstruction of solutions to the original problem is equal to the number of machines, subject to a maximum of 10 solutions for larger problems. This method, applied to linear-track, single-row problems will be referred to as procedure LTSR. Certain steps of the procedure outlined above need to be specialized for the double-row linear-track problem, and the modified method will be called procedure LTDR. While solving the modified problem with modules, the distance between the two rows is considered to be equal to the largest dimension of any machine to be placed. This ensures the assignment of modules of a machine to the same row. Also, the distance spanned by the machines (dimensions plus clearances) in each row may be different, leading to the second modification. (The number of machines in each row may also be different but the problem arises from having different lengths of machine arrays, and not the number of machines itself.) This can be overcome by adding dummy machines with zero flows to and from all other machines, and dimension equal to one module. These dummy machines allow solutions where the ends of the two rows are not necessarily aligned, and also solutions where the distance between two adjacent machines in a row may be more than just the clearance. The number of such 13

dummy machines used was equal to the number of modules of the largest machine in the group. One final refinement concerns the clearance provided between a dummy machine and any adjacent machine. It is obvious that any arbitrary value of such a clearance is acceptable, as long as the clearance between two real machines is respected. Procedure LTDR is designed to investigate this choice in the range between zero and the specified clearance, as follows. In constructing a layout from a saved solution, the procedure tries five different values for the clearance next to a dummy module, increasing in equal steps from zero to the maximum value. These minor adjustments did improve the solutions, but the reductions in cost did not justify a search over smaller intervals. The clearance for dummy modules corresponding to the best solution is saved and reported as part of the final solution. 3 Computational results The computational testing for this study is divided into two sections, one for loop layouts and the second for linear-track layouts. In the first section, the layout can be designed by an exact method published by Burkard and Derigs (1980) for problems with as many as 15 facilities, and this has been done to validate the heuristic method for the part-circuit formulation. However, computation time required to obtain exact solutions to problems with more than 15 machines tends to become prohibitive and hence larger problems were solved only by the heuristic method. In the second section, results for smaller single-row linear track problems are compared to optimal solutions obtained by complete enumeration, while solutions to larger single-row problems as well as all double-row problems are compared to those found by Heragu and Kusiak (1988). The solution methods are tested on problems with as many as 20 machines for loop and 14

single-row, linear-track systems; and as many as 30 machines for double-row, linear-track systems. A recent survey by Smith et al. (1986) indicates that these sizes should cover practically all FMS installations. 3.1 Loop systems The tests in this section were conducted on randomly generated problems, obtained as follows. The problem generation program uses two parameters as input-the number of machines including a load/unload (L/UL) facility (n), and the number of parts (m). First, demand and process routes are generated for each part. All process routes begin and end at the L/UL facility. Then these are converted to flows between machines to obtain the interaction matrix. The distance matrix is obtained for the part-circuit formulation as explained in section 2.1 earlier. Finally, a fixed cost matrix is generated with a very high cost for the assignment of the L/UL station to any location but location n, and a very high cost for assigning any other machine to location n. This serves the purpose of fixing the L/UL station in a chosen location. The solution procedure was not tested on the widely used set of problems generated by Nugent, Vollmann and Ruml (1968) because the optimal solution for these problems is trivially obvious for unidirectional-flow loop layouts. Flow data for this set of problems have been accumulated above the diagonal of the flow matrix; in other words, all flows between two machines are represented as one flow from the machine with the lower index to the higher-numbered machine. An optimal solution is obtained by simply placing machines around the loop in the order that they are indexed. A set of 24 problems was generated with the number of facilities (n) equal to 8 through 15, and the number of parts (m) equal to 1, 2, and 3 times the number of machines, respectively. Thus for each size of problem there were 15

three versions based on different numbers of parts. The problems were generated with distance matrices corresponding to the part-circuit formulation, and each problem was solved to optimality as well as by the heuristic method. The results are summarized in part (a) of Table 2. For this set of problems, two versions of the heuristic method were used. The first employed the usual pairwiseinterchange formula (eqn. 4), while the second used the specialized interchange formula (eqn. 5). The specialized pair-exchange procedure was effective in reducing computation times by an average of over 20% as compared to the general procedure. Hence all heuristic results for loop-layout systems reported in Table 2 and later in this paper are those obtained by using the specialized procedure. The heuristic method found optimal solutions in 20 out of 24 cases, with average solutions within one-third of one percent of optimal. Even for the largest problems of size 15, average results are within one percent of optimal. An additional 15 problems were generated with 16 through 20 facilities, with three versions of each as above. These problems were solved using the heuristic method for the part-circuit formulation and results for the second set of problems are presented in part (b) of Table 2 as the number of part circuits required. 3.2 Linear-track systems The test problems for this section are the same as those used by Heragu and Kusiak (1988). They generated flow data for a set of nine problems (labeled HK1 through HK9 in this paper) with 4 facilities each, and specified a clearance of one unit between machines. Dimensions are provided for these machines and range from 2 to 6 unit squares. Flow data for another eight problems (with the number of machines equal to 5, 6, 7, 8, 12, 15, 20 and 30) are taken from the Nugent, Vollmann and Ruml (1968) article, and the clearance between machines for this second set of problems is set at 0.01 unit. These problems will be referred to as the NVR05 through NVR30 problems. Machine dimensions for all these 16

Table 2: Computational results for loop layouts (a) Optimal and heuristic solutions No. of No. of Solution machines parts Optimal" Heuristicb 8 8 27 100.00 16 92 100.00 24 146 100.00 9 9 48 100.00 18 143 100.00 27 194 100.00 10 10 47 100.00 20 185 101.62 30 318 100.00 11 11 39 100.00 22 187 100.00 _33 310 101.61 12 12 39 100.00 24 215 100.00 36 589 100.00 13 13 76 100.00 26 285 100.00 39 578 100.00 14 14 88 100.00 28 249 101.20 42 811 100.00 15 15 92 102.17 30 380 100.00 45 662 100.00 AVERAGE 100.28 (b) Heuristic solutions No. of No. of Part machines parts circuits 16 16 78 32 369 48 762 17 17 94 34 386 51 950 18 18 124 36 455 54 881 19 19 85 38 492 57 1247 20 20 129 40 593 _60 1375 aNumber of part-circuits bAs percentage of optimal 17

problems have also been selected and range from 0.01 to 0.09 unit squares. Since the machines are square in shape, the dimension of interest for the layout problem is the length of a side. Single-row problems The first set of 9 problems with 4 machines each, and the first seven problems from the second set were solved by Heragu and Kusiak (HK) for single-row layouts along linear tracks by their Algorithm 1. This algorithm is a "greedy" constructive heuristic and starts by putting the two machines with the largest interaction cost (computed as if they were adjacent) together. Then on the same basis, the remaining machines are added to the ends of this chain one by one, until all machines have been included in the solution. Thus the algorithm provides a sequence, and the exact layout has to be constructed with the appropriate clearances separately later, much as in the QAP based heuristic described in this paper. These 16 problems were solved by the heuristic procedure called LTSR (for linear-track single-row), described in the previous section. The 4-machine problems and the first four Nugent, Vollmann and Ruml problems were also solved by using complete enumeration to obtain optimal solutions. Costs for heuristic methods are, therefore, compared to these optimal solutions and are presented in Table 3. Solution costs for the NVR12, 15 and 20 problems are compared for the LTSR and HK heuristic procedures in Table 4. It is clear that LTSR provides better solutions and its advantage grows with size. The results found by the HK procedure for the seven NVR problems are worse than those found by LTSR by an average of 23.86%, but for the largest three problems the average performance is worse by 38.25%. The layout designed by LTSR for the NVR problems is presented in Table 5 as the sequence in which machines are placed. 18

Table 3: Single-row layout solutions compared to optimal Heuristic solutions Optimal % deviation Problem LTSR HK solution LTSR HK HK1 225.000 225.000 225.000 0.00 0.00 HK2 440.000 535.000 440.000 0.00 +21.59 HK3 510.000 510.000 510.000 0.00 0.00 HK4 465.000 465.000 465.000 0.00 0.00 HK5 19.680 22.350 19.680 0.00 +13.57 HK6 361.000 359.000 359.000 +0.56 0.00 HK7 320.000 318.000 318.000 +0.63 0.00 HK8 60.000 82.000 60.000 0.00 +36.67 HK9 244.000 244.000 244.000 0.00 0.00 NVR05 1.100 1.165 1.100 0.00 +5.91 NVR06 1.990 2.085 1.990 0.00 +4.77 NVR07 4.730 5.420 4.730 0.00 +14.59 NVR08 6.295 7.995 6.295 0.00 +27.01 Table 4: Comparison of heuristic solutions to single-row layout problems Problem Heuristic solutions H LTS LTSR LTSR HK percent NVR12 23.865 31.525 +32.10 NVR15 45.740 62.624 +36.91 NVR20 122.240 178.149 +45.74 Table 5: Single-row layout designs by LTSR Problem Machine sequence NVR05 45123 NVR06 654123 NVR07 7365421 NVR08 7 6 5 4 8 1 2 3 NVR12 7 3 9 12 11 8 4 1 2 10 5 6 NVR15 6 15 10 3 4 14 5 13 2 12 8 9 11 1 7 NVR20 20 7 17 18 4 19 2 15 8 12 5 14 16 11 1 10 13 6 3 9 19

Double-row problems The heuristic procedure for solving double-row linear-track layout problems, called LTDR, was used to solve the eight Nugent, Vollmann and Ruml (1968) problems, and solution costs are compared with those found by Algorithm 2 of Heragu and Kusiak (1988). Their Algorithm 2 is similar to Algorithm 1 in spirit, in the sense that solutions are constructed one machine at a time based on a limited number of interactions. For Algorithm 1, the selection is made based on interactions between pairs of machines, while Algorithm 2 considers interactions between machine triples (the vertices of triangles). Once again, the algorithm produces sequences from which the actual layouts must subsequently be constructed. Also, Algorithm 2 generates as many sequences as the number of machines, and the solution with the best cost is selected. Heragu and Kusiak (1988) state that "the number of machines in each of the two rows is as equal as possible." We do not feel that any practical considerations justify imposing such a constraint on solutions. In our method, the location of dummy modules determines the relative alignment of rows as well as the distribution of machines between the two rows. Comparative results are presented in Table 6 and show that this policy, combined with the use of a solution method based on the QAP, outperforms the Heragu and Kusiak solution method by a significant margin. The HK results are worse than LTDR results on the average by more than 40%, with results ranging from +25% to +63% of LTDR results. The solutions found by LTDR are presented in Table 7. The sequence of machines is provided for each row, and dummy machines are shown only where necessary to specify the relative alignment of the two rows, starting at the left end. For the purpose of illustration, Figure 2 shows actual layouts for the NVR08 problem in the single-row and double-row configurations, based on the solutions given in Tables 5 and 7. 20

Table 6: Comparison of heuristic solutions to double-row layout problems Problem Heuristic solutions Clearance for LTD LTDR LTDR HK dummy modules percent NVR05 0.700 1.14 0.00 +62.86 NVR06 1.395 2.01 0.50 +44.09 NVR07 2.740 3.98 0.00-1.00 +45.26 NVR08 3.875 4.95 0.00 +27.74 NVR12 13.110 17.91 0.25 +36.61 NVR15 24.850 34.98 0.00 +40.76 NVR20 63.970 91.47 0.00 +42.99 NVR30 183.155 228.30 0.25 +24.65 Table 7: Double-row layout designs by LTDR Problem Row no. Machine sequencea NVR05 1 d d 5 2 3 2 41 NVR06 1 321 2 d654 NVR07 1 1 4 7 2 2563 NVR08 1 d d d 1 4 8 7 2 3256 NVR12 1 dd 1 7 8 4 6 2 3 2 9 12 11 5 10 NVR15 d d d d d 6 4 13 2 9 1 2 10 15 3 14 5 12 8 117 NVR20 1 20 1 5 8 12 17 5 19 10 13 6 2 d d d d 7 11 16 4 2 14 18 3 9 NVR30 1 20 4 30 25 28 16 13 8 10 7 29 19 9 21 2 d d 27 15 14 11 6 17 23 22 12 24 18 1 5 2 3 26 ad denotes a dummy machine 21

Double-row layout 3. 6 Single-row layout 6 2 L f t NV 8 p m Figure 2: Layouts for the NVR08 problem 22

3.3 Computation times All computation times mentioned here are CPU times for a VAX 8650 using FORTRAN programs. Loop layouts. Times for loop layout designs are the average of the three versions for each size of problem. The heuristic method for loop-layout problems requires average computation times ranging from a fraction of one second for small problems to less than 12 seconds for the largest problems with 20 machines. Exact solutions to problems with 15 machines require an average solution time of 118 minutes, while the heuristic procedure needed just over 3 seconds. Linear layouts. The linear-track problems are much larger because the effective size of the problem is defined by the number of modules. This number is 71 for the 20 - machine single-row problem, and solution time is under 7 minutes. The number of modules is as large as 106 (including dummies) for the 30-machine double-row problem, and the computation time is just under 38 minutes. 4 Analysis and conclusions In this paper we have shown how the layout design problem for Flexible Manufacturing Systems can be modeled as a Quadratic Assignment Problem. The two most common cases, loop-conveyor and linear-track conveyor systems, are considered. Computational testing showed that our methods work well when compared to optimal solutions for loop systems, and compared to results published recently in the literature for linear-track systems. A detailed discussion for each case follows. Loop-conveyor systems. A formulation of the layout problem for single-loop conveyor flexible manufacturing systems was developed based on the alternate 23

equivalent objective of minimizing part circuits, and it was shown how the distance matrix of the traditional facilities layout problem can be modified to model this objective. A heuristic method for the facilities layout problem was specialized to take advantage of the characteristics of this formulation, and the resulting procedure was tested against an optimal solution method for problems with as many as 15 machines. Average results were within one-third of one percent of optimal solutions. Linear-track systems. The solution procedures developed for this type of problem require a transformation of the original problem into a larger problem with equal sized modules that can be solved as a QAP, while ignoring clearances. The solution to this modified problem can be translated into a solution to the original problem, with appropriate clearances added. The two procedures developed (LTSR and LTDR) are complete in the sense that they require as input only flow data and the relevant machine dimensions. Subroutines then decide on the appropriate module size, break up machines into modules, make the necessary transformations to the flow data, create a distance matrix for the modified problem, solve this problem, construct the actual layout for the original problem, and compute the exact cost including clearances. It is understood, of course, that the modified problem is a large facilities layout problem, but computation times are reasonable in the context of a design problem for systems that typically cost millions of dollars. The results obtained by LTSR and LTDR are significantly better than those found by Algorithms 1 and 2 of Heragu and Kusiak (1988). The reasons for this are not hard to see. First, their methods gain no advantage over LTSR and LTDR in terms of accuracy in handling clearances. Second, they develop solutions based on a limited number of pairwise interactions, though the cost of the layout does finally have to be calculated for all pairs of machines. The methods presented in this paper, on the other hand, are based on solutions to 24

the QAP underlying the layout problem. This feature probably accounts for most of their superiority. References Afentakis, P. 1986. A Model for Layout Design in Flexible Manufacturing Systems. In Flexible Manufacturing Systems: Methods and Studies, A. Kusiak (ed.). Elsevier Science Publishers (North-Holland). 127-139. Afentakis, P. 1987. The Ring Interconnection Structure for Flexible Manufacturing Systems. Working Paper #87-003, Department of Industrial Engineering and Operations Research, Syracuse University. Black, J.T. 1983. Cellular Manufacturing Systems Reduce Setup Time, Make Small Lot Production Economical. Industrial Engineering. Nov., 36-48. Browne, J., D. Dubois, K. Rathmill, S.P. Sethi and K.E. Stecke. 1984. Classification of Flexible Manufacturing Systems. The FMS Magazine. 2(2), 114-117. Burkard, R.E. and U. Derigs. 1980. Assignment and Matching Problems: Solution Methods with Fortran Programs, volume 184 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, Berlin. Buzacott, J.A. and J.G. Shanthikumar. 1980. Models for Understanding Flexible Manufacturing Systems. AIIE Transactions. 12, 339-350. Gilmore, P.C. 1962. Optimal and Suboptimal Algorithms for the Quadratic Aassignment Problem. Journal of SIAM. 10(2), 305-313 Graves, G.W. and A.B. Whinston. 1970. An Algorithm for the Quadratic Assignment Problem. Management Science. 17(7), 453-471. 25

Groover, M.P. 1980. Automation, Production Systems, and Computer-Aided Manufacturing, Prentice-Hall. Chapter 19. Heragu S.S. and A. Kusiak. 1988. Machine Layout Problem in Flexible Manufacturing Systems. Operations Research. 36(2), 258-268. Kaku, B.K., T.E. Morton and G.L. Thompson. 1988. A Heuristic Algorithm for the Facilities Layout Problem. Working Paper MSRR 544, Graduate School of Industrial Administration, Carnegie Mellon University. Kaku, B.K., G.L. Thompson and I. Baybars. 1988. A Heuristic Method for the Multi-story Facilities Layout Problem. European Journal of Operational Research. 37(3), 384-397. Lawler, E.L. 1963. The Quadratic Assignment Problem. Management Science. 9, 586-599. Nugent, C.E., T.E. Vollmann and J. Ruml. 1968. An Experimental Comparison of Techniques for the Assignment of Facilities to Locations. Operations Research. 16(1), 150-173. Smith, M., R. Ramesh, R. Dudek and E. Blair. 1986. Characteristics of U.S. Flexible Manufacturing Systems-A Survey. In Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, K. Stecke and R. Suri (eds.). 477-486. Stecke, K.E. 1985. Design, Planning, Scheduling and Control Problems of Flexible Manufacturing Systems. Annals of Operations Research. 3, 3-12. 26