EXACT SOLUTION PROCEDURES FOR THE CIRCULAR LAYOUT PROBLEM Yavuz A. Bozer Suk-Chul Rim Technical Report #89-33 December 18, 1989 The University of Michigan Department of Industrial and Operations Engineering 1205 Beal Avenue Ann Arbor, MI48109-2117

Abstract In this paper we present exact solution procedures for a special discrete layout problem; namely, the Circular Layout Problem (CLP) where the "facilities" are arranged around a simple closed loop path and flows between "facilities" occur only in one direction (e.g., clockwise). Given a flow matrix and a distance matrix, the problem is a special case of the Quadratic Assignment Problem where the objective is to assign each "facility" to one of the predetermined sites such that the total "cost" (defined by flows times distances) is minimized. As described in the paper, many practical applications of the CLP, such as arranging workstations around an AGV or conveyor loop, can be found in modem manufacturing systems. The CLP can be divided into four subproblems based on whether the sites are equally spaced around the loop or not, and whether flow is conserved at each "facility" or not. We present an LP relaxation which optimally solves three of the subproblems. For the fourth subproblem where the sites are arbitrarily spaced and flow is not conserved, we present a branch and bound scheme based on a tight lower bound which is obtained by taking advantage of the circularity of the distance matrix.

The problem of determining the optimum locations of a set of facilities, while satisfying certain constraints, is generally known as thefacility layout (orfacility location) problem. It has many applications in the design of manufacturing systems, service facilities, office space, etc. In those cases where only a finite number of predetermined sites are considered, it is called the discrete layout/location problem. Given certain "interactions" between the facilities to be located, the discrete layout problem has often been modeled as the Quadratic Assignment Problem (QAP). Since the QAP has been shown to be NP-complete (see Sahni and Gonzalez 1976), obtaining an optimal solution generally requires excessively high computation times. For example, Finke, Burkard and Rendl (1985) have reported that a QAP with 15 facilities requires about 50 minutes of CPU time on a CDC Cyber 76. Hence, more efficient solution procedures are required to optimally solve discrete layout problems of moderate size. In this paper we will present exact solution procedures for a special discrete layout problem; namely, the Circular Layout Problem (CLP) where the facilities are arranged around a simple closed loop path and flows between "facilities" are handled only in one direction (e.g., clockwise). As motivated in the following paragraphs, such a configuration has many applications in manufacturing. To facilitate problem description we will use a manufacturing system as an example throughout the paper, although all the results would apply in other contexts. 1. PROBLEM DESCRIPTION AND APPLICATIONS Consider a manufacturing system with automated guided vehicles (AGVs) or similar devices serving as the material handling system. Suppose the vehicles (or the devices) operate on a simple closed loop path with no "shortcuts" as shown in Figure 1, and that 1

there are n predetermined sites and n stations to be assigned to each site. Each station represents either an Input/Output (VO) station or a "processor" station. Jobs that arrive from outside the system are received through one of the VO stations. Likewise, jobs that require no further processing are delivered to an VO station through which they exit the system. A processor station, on the other hand, represents a machine (or a group of machines, or a cell) where jobs are processed. At a processor station, jobs are picked up from the input buffer; when processing is completed they are placed on the output buffer (see Figure 1) where they are eventually picked up by a vehicle and delivered to the input buffer of the next station. The example shown in Figure 1 contains one VO station and 11 processor stations. Vehicles are assumed to move the jobs one at a time, and travel unidirectionally around the loop. Throughout the paper, without loss of generality, the vehicles are assumed to travel clockwise. Figure 1 Let F=(fij) denote theflow matrix, where fij2O represents the average number of jobs to be moved from station i to station j over a given length of time, for i=l,-.,n, j=l,...,n, and fii=0 for all i. Also, let R=(ruv) denote the site distance matrix, where ruv>0 is the clockwise distance from site u to site v, for u=l,-*~,n, v=l,.-,n, and ruu=O for all u. The most important characteristic of the CLP is that, for any pair of sites u and v, the distance from site u to site v and the distance from site v to site u sum up to the total loop length, C. That is, ruv+rvu —C for all u and v, uzv. Such a distance matrix is called a circular distance matrix. Lastly, let S=(s(l),s(2),.-.,s(n)) denote a layout of n stations, where s(i) denotes the site occupied by station i. Conceptually, any closed loop path with no shortcuts can be represented as a circle, around which there are n predetermined sites with the same distances as in the original closed loop 2

path. As shown in Figure 2, in general, ruvrvu except for those pairs of sites that are symmetrically located around the circle. Note that those problems that contain shortcuts cannot be modeled as a CLP. Figure 2 We will next define the material handling requirement in a system as the total quantity of material to be moved over a given length of time, multiplied by the corresponding travel n n distance, i.e., A C fijrs(i)sO), for a given flow matrix F, site distance matrix R, and i=l j=l layout S. In the above example based on AGVs, the material handling requirement is equal to the total loaded vehicle travel distance over a given length of time. We want to find the layout S which minimizes the material handling requirement for a given flow matrix F and site distance matrix R for the following reasons: if the required throughput is high and the number of vehicles is fixed, then only the optimal layout S may meet the throughput, while other layouts may not. If required throughput is not so high, then several alternative layouts may meet the throughput. However, S would still be the preferred layout because it will lower the average vehicle utilization so that (1) a higher throughput requirement in the future can be met without purchasing additional vehicles; or (2) more stations can be added to the system with the same number of vehicles; or (3) capital investment can be reduced by using a smaller number of vehicles and/or less expensive, slower vehicles. Hence, for a given flow matrix F=(fij) and a circular site distance matrix R=(ruv), the CLP is defined as assigning n stations to n predetermined sites around a circle so as to minimize n n the material handling requirement given by Z = Y fijrs(i)sO). Throughout the paper, the i=1 j=l fixed cost of assigning a station to any site is assumed to be negligible, or nearly equal among the sites. 3

An increasing number of problems arising in modem manufacturing applications can be modeled as a CLP. Depending on the type of application, the material handling requirement may be interpreted in different ways. For example, consider the case where material flow between individual stations is supported by a closed loop conveyor, as shown in Figure 3(a). In such an application the site distance matrix is clearly a circular one. Furthermore, the material handling requirement can be defined as the total distance all jobs have to travel on the conveyor. Hence, given a uniform conveyor speed around the loop, minimizing the material handling requirement effectively minimizes the total time jobs spend on the conveyor (which would minimize congestion on the loop). Figure 3 Other examples include a station layout for a robot arm rotating in one direction only (clockwise or counterclockwise) to serve stations located around a circle as shown in Figure 3(b); and tool layout on a turret (in flexible manufacturing systems) to minimize the total turret rotation time for switching the tools (during which time the machine is idle), provided that the slots are of equal size and the turret rotates in only one direction as shown in Figure 3(c). 2. LITERATURE REVIEW The CLP has been studied independently by several researchers over the last few years under various names. In formulating the CLP two types of objective functions have been used in the literature: (1) minimizing the total flows times distances per unit time; and (2) minimizing the total number of parts that cross the I/O station per unit time. The former has been used in the classical QAP formulation (Koopmans and Beckmann 1957) since it best represents the total interaction (or material handling requirement). A few studies have used this objective function in formulating the CLP. Kiran and Karabati (1988) develop a 4

polynomial time algorithm for a special case of the CLP where material flow is allowed only between a refixturing station and all other stations. They also present a branch and bound algorithm with dominance rules for the general case. Assuming that flow is conserved, Kiran, Unal and Karabati (1989) formulate the problem as a station sequencing problem and present an integer programming formulation. Based on empirical results, the authors report that the LP relaxation of the IP formulation yields integer optimal solutions for over 3,600 randomly generated problems. However, they were unable to prove that one would always obtain integer solutions. The objective function of the second type defined above has been used in a few studies. Afentakis (1989) first formulates the problem as an integer programming problem. A heuristic algorithm using block interchanges as opposed to pairwise interchanges is also presented. Kouvelis and Kim (1989) present dominance rules, three constructive heuristic algorithms, and a branch and bound algorithm with decomposition principles for large flow matrices. Both Afentakis (1989) and Kouvelis and Kim (1989) show that the problem with the objective function of the second type is still NP-complete. Lastly, Bartholdi and Platzman (1989) and Bozer and Srinivasan (1989) analyzed the throughput capacity of an AGV loop such as the one shown in Figure 1. Neither study, however, addressed the layout problem. 3. THE CIRCULAR LAYOUT PROBLEM The CLP can be formulated as a quadratic assignment problem (QAP). Letting In denote the set of first n positive integers, the QAP formulation of the CLP can be given as follows: n n n n Min. ~ l I ~ I fijruvxiuxjv (1) i=l j=l u=l v=l n (QAP) s.t. X xiu = 1, for all u in In, (2) i=l 5

n I Xiu = 1, for all i in In, (3) u=1 xiu = O or 1, for all i and u in In, (4) where xiu=l indicates that station i is located at site u. In order to develop an efficient solution procedure for the CLP, we will first present a special case, namely, the EquiDistance CLP. Subsequently, we will extend the results to more general cases of the CLP. 3.1. The Equi-Distance Circular Layout Problem (ED-CLP) Consider n equally spaced predetermined sites arranged around a circle as shown in Figure 4(a). Without loss of generality, we will assume that adjacent sites are unit length apart, and that the length of the circumference is equal to n. Recall that R=(ruv) is a (circular) site distance matrix, where ruv denotes the clockwise distance from site u to site v. Let us define D=(dij) as a matrix of decision variables for the CLP, where dij denotes the clockwise distance from station i to station j, i'j. For example, given the set of sites shown in Figure 4(a), we have r12=1, r13=2, and so on. However, given a corresponding layout shown in Figure 4(b), we have d52=1, d56=2, and so on. Note that D=(dij) is also a circular distance matrix, that is, dij+dji=n for all i andj in In, i j. Figure 4 The flow matrix F=(fij) can be calculated as follows: suppose there are K types of jobs, each of which has its own routing, that is, the sequence of stations they visit. Let Qk denote the average number of jobs of type k (k=l,-.,K) to be processed over a given length of time and Vij(k) be the total number of times that job type k is moved from station i to station j before it leaves the system. Then the flow matrix is obtained as K F=(fij), where fij = S QkVij(k), for all i and j in In, and fii=0 for all i in In. (5) k=-I 6

Given the special structure of the problem, we will attempt to formulate the ED-CLP as a Linear Programming (LP) problem. Although the CLP is defined for n>3, for notational convenience, we will consider CLPs only with n24 in the remainder of the paper. (It is straightforward to obtain the optimal solution for n=3.) As shown in Figure 4(b), regardless of the sequence of stations, the distances from station i to all other stations sum up to a constant. That is, n n(n-1) dij = 1 + 2 + *. + (n-l) =(2 ) for all i in In. (6) j=1 j*i By the same argument, the distances to station j from all other stations sum up to the same constant. That is, ~~~~n ~n(n-l) dij = 1 + 2 + - + (n-1) = 2 for all j in In. (7) i=l Furthermore, since D=(dij) is a circular distance matrix, di + dji = n, for all i and j in In, iej. (8) The next set of constraints proved to be critical for our study. These constraints are concerned with the precedence relationship of any three stations around a circle. As shown in Figure 5, starting at station i, either j precedes k (i.e., dij+djk=dik), or k precedes j (i.e., dij+djk=dik+n). Hence, dij + djk = (dik or dik+n), for all distinct i, j, and k in In. (9) Figure 5 Unfortunately, if we attempt to employ (9) as a constraint set, the formulation would have to include 0-1 integer variables. Hence, the following relaxed inequality will be used instead of (9): dik dij + djk < dik + n, for all distinct i, j, and k in In. (10) 7

As defined earlier, the objective is to minimize the material handling requirement. The decision variables are dijts, where dij denotes the clockwise distance from station i to station j, inj. Hence, the LP relaxation for the ED-CLP is constructed as follows: Min. ~ ~ fijdij (11) i j#i (LP~) s.t. dij n(n-1 for all i in In, (12) dij = n(n-) for allj in In, (13) i*j dij + dji = n, for all i and j in In, izj, (14) dij + djk < dik + n, for all distinct i, j and k in In, (15) dij + djk > dik, for all distinct i, j and k in In, (16) dij > 0, for all i and j in In, i#j. (17) Note that the above model represents a LP relaxation because constraints (15) and (16) are used instead of (9), and dij's are not restricted to integer values. An important characteristic of a feasible solution D=(dij) to LP~ is that all dij's implicitly have the same upper and lower bounds. Consider an arbitrary dij (li<jln) in D and a set of precedence constraints which contain dij as listed in (18) below: dil < dij + djl dil + n di,i-1 < dij + dji-1 di,i-1 + n di,i+l < dij + dj,i+l 5 di,i+ + n (18) dij-1 < dij + djj.1 < dij-i + n dij+l < dij + djj+l < dij+l + n din < dij + djn < din + n Summing up the above (n-2) constraints, we obtain: X dik < (n-2)dij + djk ~ ~ dik + n(n-2). (19) kij krij k-ij 8

Theorem 1. In any feasible solution D=(dij) to LP~, l<dij~n-l for all l<i;ejn. Proof. Since E dik = n(n-1)/2 - di by (12), constraint (19) can be rewritten as: kiij n(n-1)/2 - dij < (n-2)dij + n(n-1)/2 - dji < n(n-1)/2 - dij + n(n-2). By (14), the above constraint can be simplified to l<dij<n-1 for all l<i<j<n. Also, since dji=n-dij, we have ldij-n-1 for all lj<i<n as well, which completes the proof. / To facilitate the following proofs, we will simplify LP~ to obtain an equivalent formulation, say, LP as follows: 1. constraints (13) can be eliminated since they are redundant due to (12) and (14); 2. only those indices i, j, and k such that l<i<j<k<n need to be considered in (15) and (16) since precedence constraints with other indices are redundant due to (14); 3. dji in (11) and (12) can be replaced by n-dij for l<i<jfn, and (14) can be eliminated; and 4. any one row among the rows given by (12) can be eliminated since, after replacing dji in (11) and (12) with n-dij, both sides of the summation of all constraints given by (12) are equal to zero. This implies that the n rows in question are linearly dependent. Without loss of generality, we will eliminate the last row. Consequently, the resulting LP relaxation for the ED-CLP is given by: n-i n Min. 5 I fijdij+C (20) i=l j=i+l *~i-I n n(n-l) (LP ) s.t. -~ dji + ~ dij -(i-l)n, forl< i n-1, (21) j=l j=i+l dij + djk < dik + n, for 1 i <j < k n, (22) dij + djk dik, for 1 i <j < k <n, (23) dij > O, for 1 <i <j <n, (24) n-1 n where fij = fij - fji, and C = n l E fji. i=l j=i+l 9

Let B denote a basis of LP. As shown in Figure 6(a), B can be divided into four matrices labeled P, C, 0, and the identity matrix I, where P is further divided into E and -G, and C is further divided into H and G. For each triplet (i,j,k) where l~i<j<kln, there is a pair of rows in B given by (22) and (23). In LP with n stations, there are n(n-1)/2 columns (or decision variables), (n-1) rows in E given by (21), and 2(3) = n(n-1)(n-2)/3 rows in -G, H, and G given by (22) and (23). Since all the dij's must be basic variables in any basis by Theorem 1, only (n-l)(n-2)(2n-3)/6 out of the n(n-l)(n-2)/3 slack variables can be selected as basic variables in B. Let H denote the matrix which consists of the pairs of rows whose slack variables are both selected as basic variables, and let G denote the matrix which consists of the rows for which only one slack (out of a pair) is selected as a basic variable. Let r(M) denote the number of rows in a matrix M. Since P is a square matrix, r(-G) = n(n-1)/2 - (n-1) = (n-l)(n-2)/2. Hence, r(H) = n(n-l)(n-2)/3 - 2r(-G) = (n-l)(n-2)(n-3)/3. Within the submatrices H and G, respectively, the rows are arranged in the lexicographically increasing order of the indices; that is, (1,2,3), (1,2,4),, (1,2,n), (1,3,4), and so on. Figure 6 Recall that, P=(- and C=(-p-). It is known that (Bazaraa and Jarvis 1977, p.52): where -1l U W \ -CP= y (26) -CP = (26) ^v X/ 10

In order to prove that LP solves the ED-CLP, we will show that the optimal solution of LP actually yields an equi-distance layout. However, we will first show (using the following four lemmas) that -CP-1 consists of U, V, W, and X as shown in Figure 6(b), where U=V=O, X=I, and W is composed of 0 or +l's. Subsequently, we will show that for any basic feasible solution of LP, exactly one of the two constraints given by (22) and (23) holds at equality for all l1i<j<k<n; that is, a pair of slack variables associated with * (22) and (23) must assume the values (O,n) or (n,0) in any basic feasible solution of LP. Recall that, for each triplet (ijk) where l<i<j<kln, there is a pair of rows (given by (22) and (23)) in B. Let the first and second row in the pair associated with the triplet (i,j,k) be labelled r+(ijk) and r-(i,j,k), respectively. In other words, let r+(ij,k) denote the row from (22) in which the coefficients of dij, dik, and djk are 1, -1, and 1, respectively, and let r-(i,j,k) denote the matching row from (23); that is, r-(i,jk)= -r+(ij,k). Also, let r~(i,j,k) denote either r+(i,j,k) or r-(i,j,k). Consider next a quadruplet (i,j,k,l) where li<j<k<lln. There are exactly four triplets associated with this quadruplet: (i,jk), (ij,l), (ik,l), and (j,k,l). Let r~(i,j,k,l) denote one of the two rows associated with the m th triplet of the above four; that is, ro(i,j,k,l) = r+(ij,k) or r'(i,j,k), ro(i,j,k,1) = r+(i,j,l) or r"(i,j,l), and so on. Lemma 1. For any quadruplet (i,j,k,l) where li<j<k<lSn, there exists q=(q1,q2,q3q4) 4 such that s, qm rm(ij,k,l) = 0 if and only if qm = ~ co for some co>0 (1<m<4). m=l Proof. See Appendix. Lemma 2. Every row of H can be represented as a linear combination of the rows of G. Proof. Since G is included in C, it is sufficient to show that rank(G) = rank(C). Recall that, for the ED-CLP with n stations, r(G) = (n-l)(n-2)/2. Also, all the rows of G are linearly independent. (Otherwise, due to -G, matrix B would not represent a basis.) 11

Hence, rank(G) = r(G). On the other hand, consider a quadruplet (i,j,k,l) where l<i <j<k<l<n. By Lemma 1, r~(j,k,l) can be expressed as a linear combination of r~(i,j,k), r~(i,j,l), and r~(i,k,l). Hence, the maximum number of independent rows in C is given by (n21) = (n-l)(n-2)/2 when i =1. That is, rank(C) < (n-l)(n-2)/2 = rank(G). However, since C includes G, rank(C) > rank(G). Therefore, rank(C) = rank(G). U Lemma 3. Let R1 denote the matrix P in which the s th row of E is replaced by the r th row of H. Then, det Rl = 0 for 1<r_(n-1)(n-2)(n-3)/3 and l~s.n-l. Proof. See Appendix. Lemma 4. Let R2s denote the matrix P in which the s th row of E is replaced by the r th row of G. Then, det R2s = 0 for l (n-l)(n-2)/2 and l<s<n-1. Proof. Since R2s contains two identical rows with opposite signs, det R2s = 0 for all r and s. U Lemma 5. Let R3s denote the matrix P in which the s th row of -G is replaced by the r th row of H. Then, det R3s = 0 or ~det P for <1r<(n-l)(n-2)(n-3)/3 and l<s<(n-1) (n-2)/2. Proof. See Appendix. Lemma 6. Let R4s denote the matrix P in which the s th row of -G is replaced by the r th row of G. Then, det R4s is equal to -det P if r=s, and 0 otherwise, for l<r,s< (n-l)(n-2)/2. Proof. Straightforward. Using the last four lemmas (Lemmas 3 through 6), we will next prove a theorem which is a critical one for the paper. 12

Theorem 2. Consider a triplet (i,j,k) where l<i<j<kln and the corresponding pair of precedence constraints given by (22) and (23). In any basic feasible solution of LP, exactly one of these two constraints will hold at equality. Proof. Obviously, in any feasible solution of LP, constraints (22) and (23) cannot both hold at equality. However, both constraints may hold as strict inequalities in some feasible solutions. We will show that, in a basic feasible solution, both constraints cannot hold as strict inequalities; that is, a pair of slack variables associated with (22) and (23) must be equal to either (0,n) or (n,0). Let the g,h minor of P, denoted by Pgh, be the matrix obtained by eliminating the g th row and the h th column of P. Also, let M(i,j) denote the element in the i th row and the j th column of a matrix M. Then, by (26), we have: U(i,j) = - C(i,k)P(k,j). (27a) k=l That is, P (1)k+jdetPk U(i,j) = -C(i,k) det P k=l = det [ (-1) k+ C(i,k) det Pjk ], (27b) k=1 where p = n(n-1)/2. Note that the expression within the brackets defines the determinant of a matrix obtained by replacing the j th row of P with the i th row of C. Such a matrix was defined earlier as R1j in Lemma 3 where it was shown that det Rj_ = 0 for all i and j. Hence, U(iJ) = ) det R1j = 0 for all i andj. det P Ii Likewise, V(ij) = (-1) det R2., where R is as defined in Lemma 4. By Lemma 4, det R2 = 0 for all i andj. Therefore, V = 0. Following a similar approach, W(i,j) = d() ij ~~~~~~~~~~~~~~~~~det P 13

det Rij, where R3. is as defined in Lemma 5. Thus, by Lemma 5, W(i,j) is equal to 0 or +1 for all i and j. Consider next the matrix H. Recall that H is composed of pairs of rows. Let Hi and Hi denote two rows in a pair. Then, Hi = -Hi by definition. Using an expression similar to (27a), one may obtain a row in W, say, Wi by using H(i,k) in place of C(i,k). Likewise, one can obtain another row in W, say, Wi by using H'(i,k) in place of C(i,k) in (27a). Since H (i,k) = -H(i,k) for all i and k, it is straightforward to show that Wi= -Wi for all i. Thus, W also is composed of pairs of rows with opposite signs. Lastly, X(ij) = det det R4j, where R4 is as defined in Lemma 6. Thus, by Lemma 6, X=I. Let bl, b2, b3, and b4 denote the subvectors of b associated with E, -G, H, and G, respectively, as shown earlier in Figure 6(c). Then, bl(i) = n(n-1)/2 - (i-l)n for l<_in-1, and b3 = (n, 0, n, 0,.., n, 0). Also, b(i) and b4(i) is either 0 or n, where b2(i) + b4(i) = n for all i. Also, let Y={ (Yml,Ym2) I m=l,..-, (n-l)(n-2)(n-3)/6) denote the set of pairs of slack variables associated with H. Recall that a basic feasible solution of LP is equal to Bl b. Let Y(i) denote the i th slack variable in Y. Then, Y(i) = Uibl + Wib2 + Ib3 Hence, Yml = kn + n and Ym2 = -kn for all m, where k is an integer unrestricted in sign. Since all slack variables must be nonnegative, we have (k+l)n > 0 and -kn > O0. Thus, k = -1 or 0, which implies that (Yml,Ym2) = (0,n) or (n,0) for all m. Similarly, let T = ((Tml,Tm2) I m=l,-**, (n-l)(n-2)/2) denote the set of pairs of slack variables associated with G and -G. Since the slack variables associated with -G are equal to 0 by definition, (Tml,Tm2) = (0,n) or (n,O) for all m. Hence, in any basic feasible solution of LP, exactly one of the two precedence constraints in a given pair will hold at equality. U Recall that a solution D=(dij) of LP yields an upper-right triangular matrix since only those dij's with l1i<j<n are considered in LP. However, since the elements in the lower-left triangular matrix can be uniquely determined by (14), in the remainder of the paper, "a 14

solution of LP " refers to the complete solution matrix. Using the following lemma and a corollary, we will next show that any basic feasible solution of LP is an integer solution. Lemma 7. Let D be a feasible solution of LP. If there exists at least one fractional value in D, then there exists at least one pair of precedence constraints given by (22) and (23), both of which hold as strict inequalities. Proof. Let dij = a be a fractional value in D. Suppose there is no pair of constraints both of which hold as strict inequalities. That is, every constraint in (18) holds at equality on one side. Further suppose that m out of n-2 constraints in (18) hold at equality on the right side, and the remaining (n-2-m) constraints hold at equality on the left side of the constraint (Omn-2). Then, regardless of which m constraints hold at equality on the right side, by summing up (n-2) equalities, we obtain (n-2)dij + E djk = ~ dik + mn, k#ij kxij or equivalently, (n-2)a + n(n-1)/2 - (n-a) = n(n-l)/2 - a + mn. Simplifying the above equation, we obtain a = m+1, which is contradictory. Hence, there exists at least one pair of precedence constraints both of which hold as strict inequalities. U Corollary 1. Let D be a feasible solution of LP. If either (22) or (23) holds at equality for all l<i<j<kln, then D is an integer solution. Proof. The above corollary is the contra positive of Lemma 7. Theorem 3. Any basic feasible solution of LP is an integer solution. Proof. By Theorem 2, we showed that in any basic feasible solution of LP exactly one of the two constraints given by (22) and (23) will hold at equality for all triplets (i,jk) where l~i<j<kcn. Furthermore, it was shown in Corollary 1 that in a feasible solution of LP, if exactly one of the two precedence constraints in a given pair holds as an equality for all li<j<kPn, then the solution is an integer solution. Hence, any basic feasible solution of LP is an integer solution. a 15

It is straightforward to show that the coefficient matrix of LP is not unimodular. However, as shown above, due to the special structure of LP, all its extreme points are integer. Lastly, we will prove that if a feasible solution D of LP is an integer matrix, and either (22) or (23) holds at equality for all li<j<kdn, then D actually yields an equi-distance layout. To do so, let us define an element matrix D=(dij) of size n as a square matrix, where all diagonal elements are 0, and each element of In-i={ 1, 2,..-, n-l 1 appears once and only once in each row and each column of D. An example of an element matrix is shown in Table I(a). An element matrix D=(dij) of size n is called a circular element matrix if dij+dji = n, for all i and j, irj. An example of a circular element matrix is shown in Table I(b). Let us next define the standard matrix D~=(d~j) of size n as a square matrix where d~j = j-i for li<jln, and n-(i-j) for 1lj<i-n, and 0 for 1<i=j<n as shown in Table I(c). Note that a standard matrix is also a circular element matrix. Table I Theorem 4. Any basic feasible solution D of LP is an element matrix. Proof. Suppose D is not an element matrix. Then either there exists at least one row or a column of D in which a value K appears more than once, or there exists at least one row or a column of D in which a value K does not appear, for some integer K (1<Kgn-l). 1) Without loss of generality, suppose that K appears more than once in the i th row of D. Let dij = djk = K. Since either (22) or (23) holds at equality by Theorem 2, djk is equal to 0 or n; which contradicts Theorem 1. 2) Without loss of generality, suppose that K does not appear in the i th row of D. Recall n-l that (21) is equivalent to (12) due to (14). Since Y k = n(n-1)/2, either the row cannot k=1 16

sum up to n(n-1)/2, or some other integer M (1~<M*Kn-1) has to appear more than once in the row. From 1) above, this also contradicts Theorem 1. * Using the following two lemmas and a corollary, we will finally show that LP optimally solves the ED-CLP. Recall that, in the station distance matrix D=(dij), dij denotes the clockwise distance from station i to station j. By "interchanging stations i and j" in D, we mean interchanging columns i and j of D and, at the same time, interchanging rows i and j of D. Lemma 8. Consider an element matrix D. If any pair of stations in D are interchanged, the resulting matrix D' is also an element matrix. Proof. See Appendix. Corollary 2. If any pair of stations in a circular matrix are interchanged, the resulting matrix is also a circular matrix. Proof. The proof is straightforward by the proof of Lemma 8. Lemma 9. Consider a feasible solution D of LP. If D is an element matrix, then the standard matrix can be obtained by a series of pairwise interchanges of stations in D. Proof. Since D is an element matrix, the value 1 appears once and only once in each column and each row of D. Suppose we perform a series of pairwise interchanges of stations in D to obtain D'=(di) where dii+l=l, for i=1,2,...,n-1, and consequently dn,1 = 1. Since D' is also an element matrix by Lemma 8, and we know that d23=l, d 13 must assume one of the values in (2,3,-**,n-1 ). By (22) and (23), d 13 < d i2 + d 23 d 13 + n. Since d 12 + d23 = 2, d 13 must assume the value 2. By the same argument, dii+2 =2, for i=1,2, —,n-2. Similarly, since we know that d34=l and d24=2, d 14 must assume one of the values in (3,4,-,n-1). By (22) and (23), d 14 < d 12 + d24 < d 14 + n. Since d 12 + d 24 = 3, d 14 must assume the value 3. By the same argument, d,i+3 = 3, for 17

i=1,2,..*,n-3. Repeating this procedure, the upper-right triangular matrix of D can be obtained as given in Table I(c). Since D is a circular matrix by (14), D' is also a circular matrix by Corollary 2. Hence, the lower left triangular matrix of D can be also obtained as given in Table I(c), which is the standard matrix. U Theorem 5. LP optimally solves the Equi-Distance Circular Layout Problem. Proof. By Theorem 4, we showed that any basic feasible solution of LP is an element matrix. Furthermore, it is shown in Lemma 9 that if a feasible solution D of LP is an element matrix, then the standard matrix can be obtained by a series of pairwise interchanges of stations in D. It is straightforward to show that if D is a standard matrix, then D yields a layout in which the stations are equally spaced along a circle in the same sequence as in D. Therefore, LP optimally solves the ED-CLP. / 3.2. The Non-Equi-Distance, Conserved-Flow CLP Consider a CLP in which flow is conserved at each station, but adjacent sites are not equally spaced around a circle (namely, the NED-CF CLP). Flow is said to be conserved at station k if total flow entering station k is equal to total flow leaving station k, i.e., if n n ~ fik = I fkj. A flow matrix is called a conserved flow matrix if flow is conserved at i=l j=1 each station. Note that flow may not be conserved at some stations if there are more than one I/O stations, or if defective jobs are scrapped at some stations. In LP (presented in Section 3. 1), the flow values do not appear in any of the constraints. Hence, the flow values do not affect the feasible space of LP. Therefore, LP solves the ED-CLP, regardless of whether flow is conserved or not at each station. However, flow conservation plays an important role in analyzing the Non-Equi-Distance CLP as shown below. The Equi-Distance CLP with conserved flow is clearly a special case of the NED 18

CF CLP. Although LP cannot be directly applied to the NED-CF CLP, it is shown by Theorem 6 that the optimal solution of the NED-CF CLP can be obtained by solving LP. Theorem 6. LP* yields the optimal solution for the NED-CF CLP. Proof. Consider an arbitrary non-equi-distance layout with conserved flow. Let X(i) = n n X fki and g(i) = z fik denote the total in-flow and total out-flow of station i, respectively. k=l k=1 Suppose station i is moved clockwise a small distance, say, 8>0 units along the circumference. As a result, the material handling requirement is increased by 68(i), while it is decreased by 85.(i). Since flow is conserved at station i, that is, X(i) = g(i), the above increase and decrease in the material handling requirement cancel each other out, and the objective function value does not change. The same argument holds if station i is moved counterclockwise. Moreover, the result holds for any 8>0 as long as station i remains between the two adjacent stations j and k. (If station i is moved beyond either j or k, then the objective function value may change due to a new sequence of stations. This issue will be further mentioned in Theorem 7.) Note that the above result holds for any station, independent of the locations of the other stations. Therefore, the objective function value does not change even if all the stations were moved in either direction as long as the sequence of stations remains unchanged. Therefore, for any NED-CF layout, there exists an Equi-Distance CF layout with the same sequence of stations, and hence, the same objective function value. Let S (ED) denote an optimal layout for an ED-CLP obtained from LP. Since LP optimally solves the EDCLP, all layouts having the same sequence of stations as in S (ED) are optimal layouts for the original NED-CF CLP, regardless of which site the sequence of stations starts from. U 19

Corollary 3. If flow is conserved at each station, then the sequence of stations in a circular layout completely determines the objective function value, regardless of the exact site locations. Proof. The proof is straightforward by the proof of Theorem 6. In proving Theorem 6, station i was not allowed to move beyond either one of the two adjacent stations. However, under a certain condition stated below, this restriction can be relaxed. Theorem 7. Consider a pair of adjacent stations i and j in an arbitrary circular layout with conserved flow. If fij=fji, then interchanging stations i and j does not change the objective function value of the layout. Proof. See Appendix. In particular, if there is a pair of adjacent stations i and j such that fij=fji in an optimal layout S with conserved flow, then, by Theorem 7, an alternative optimal layout can be obtained by interchanging stations i and j in S. Theorem 8. If the flow matrix is symmetric, then any layout is optimal for the CLP. Proof. The proof is straightforward by the proof of Theorem 7. 3.3. The Non-Equi-Distance, Non-Conserved-Flow CLP For the Circular Layout Problem in which neither the sites are equally spaced nor the flow is conserved at each station, the LP relaxation shown in Section 3.1 does not apply. Hence, the problem must be formulated as a QAP. Presently, the most successful exact solution procedure for the QAP is a branch and bound technique based on matrix reductions and Gilmore-Lawler bounds (Finke, Burkard and Rendl 1987). Note that the NED-NCF CLP still has a circular distance matrix. By taking advantage of the circularity, we can 20

obtain a new lower bound which is at least as tight as the Gilmore-Lawler bound. For details on the Gilmore-Lawler lower bound, the reader may refer to Burkard and Derigs (1980) or Bazaraa and Elshafei (1979). Consider the flow between stations i and j. Due to the circularity given by (8), regardless of the locations of stations i and j, a certain amount of flow, which is given by the minimum of fij and fji, has to travel around the circle once. Given a flow matrix F=(fij), let H=(hij) denote the netflow matrix, where hij = fij - min(fij,fji). Let W denote the sum of smaller flows in each pair (fij, fji), that is, W = ~ ~ min(fij,fji). Also, let K denote the i j>i lower bound obtained by applying the Gilmore-Lawler lower bound scheme to the net flow matrix H. Then, given that the total length of the circle is equal to n, i.e., the number of stations, the net flow lower bound is equal to K + nW. Theorem 9. The net flow bound is at least as tight as the Gilmore-Lawler bound. Proof. Let 0=((i,j) I fi 2 fji ). Also, let S=(s(i), i=l,-*.,n) be the layout vector where s(i) denote the site occupied by station i. Recall that R=(ruv) denotes the site distance matrix as defined in Section 1. Then, the objective function value Z given by (11) can be written as follows: n n Z = ~ fij rs(i)s(j) i=l j= = fij rs(i)s(j) + fij rs(i)s(j) (ij)~ 4 (ij)e D = I fij rs(i)s(j) + I fij (n-rs(j)s(i)) (ij)~ 4 (ji)e < = ~ (fij-fji) rs(i)s(j) + n fij (ij)E 0 (j,i)e 0 = ~ ~ hij rs(i)s(j) + nW, (28) i j 21

where nW represents the fixed "cost" (i.e., flows times distances) which is independent of the layout. Since a nonnegative constant is subtracted prior to computing the lower bound, the net flow lower bound will be at least as tight as the Gilmore-Lawler bound. If W is equal to zero, that is, if at least one element in each pair (fij, fji) is equal to zero, then the net flow bound is identical to the Gilmore-Lawler bound. 1 To evaluate the performance of the net flow bound relative to the Gilmore-Lawler bound, we compared the CPU times that each corresponding branch and bound code required to solve a set of randomly generated problems. The parameters considered in generating the random problems are: 1. the number of stations (N = 5, 8, or 12); 2. the density of the flow matrix: dense (no O's), medium (20% O's), or sparse (40% O's); 3. symmetry of the flow matrix: random or close to symmetric (in the latter case fji is generated from a uniform distribution over the range [.8fij, 1.2fij); and 4. distribution of the site locations around the circle: even, medium, or uneven. Unlike the other parameters listed above, it is difficult to control the evenness of the site locations. Hence, instead of directly controlling the evenness, we will choose a relatively even, medium and uneven distance matrix among 50 randomly generated distance matrices using the following scheme. Recall that the total length of the circle is n for a problem with n stations, and R=(ruv) is the n site distance matrix. Let Q = 5 Iru,u+l-1, where rn,n+l = rn,1, denote the degree of u=1 unevenness of the site distance matrix R. (Note that in a perfectly even distance matrix, ru,u+l=l for all u=l,*-*,n.) Then, the distance matrix whose Q value is the smallest, 25th, and the largest among the 50 randomly generated distance matrices is taken as the even, medium, and uneven distance matrix, respectively. Flow matrices are also randomly generated where each fij is a random integer between 0 and 100. For each parameter set, three problems with random flows are solved by the branch and bound code developed by Burkard and Derigs (1980) using the net flow bound and the Gilmore-Lawler bound. 22

Comparison of the CPU times between the two bounding schemes is summarized in Table II. Table II Although the net flow bound is not a fundamentally new bound, the branch and bound code with the net flow bound clearly outperforms the same code with the Gilmore-Lawler bound over all the parameter values tested. For problems with 12 stations, a dramatic improvement has been achieved: most problems took less than a minute with the net flow bound whereas all the problems exceeded the one hour time limit with the Gilmore-Lawler bound. Note that, as the flow matrix approaches a symmetric one, a larger amount of fixed "cost" can be subtracted a priori; this yields a tighter lower bound and results in a larger improvement over the Gilmore-Lawler bound. As an extreme case, if the flow matrix is perfectly symmetric, then any layout is an optimal layout (as stated earlier in Theorem 8) and the net flow lower bound is equal to the optimum objective function value. Also, based on Table II, neither the distribution of site locations nor the flow density appears to be a critical parameter. 4. CONCLUSIONS In this paper, we studied a special case of the Quadratic Assignment Problem, namely, the Circular Layout Problem in which the "sites" are located around a simple closed loop path with no shortcuts. Assuming that all the flows occur in one direction only (i.e., clockwise or counterclockwise), we showed that, if the sites are equally spaced and/or flow is conserved at each "facility", then the problem can be solved as a linear programming problem (which can be implemented as a polynomial time algorithm). Although the sites are not likely to be equally spaced in most cases, flow is usually conserved at each "facility" in manufacturing applications. For those cases where neither condition holds, however, we derived a lower bound by modifying the well-known Gilmore-Lawler bound. The 23

resulting bounds were reasonably strong and they become tighter as the flow matrix approaches a symmetric one. Currently, we are in the process of extending the above results to the bidirectional Circular Layout Problem. Although conveyor-based systems are unidirectional, some automated guided vehicle systems and robot arm applications can be bidirectional. 24

REFERENCES Afentakis, P. (1989) "A Loop Layout Design Problem for Flexible Manufacturing Systems," The International Journal of Flexible Manufacturing Systems, 1, pp.175-196. Bartholdi, III, J. J. and Platzman, L. K. (1989) "Decentralized Control of Automated Guided Vehicles on a Simple Loop," IIE Transactions, 21, pp.76-81. Bazaraa, M.S. and Elshafei, A. N. (1979) "An Exact Branch and Bound Procedure for Quadratic Assignment Problem," Naval Research Logistics Quarterly, 26, pp.109-121. Bazaraa, M. S. and Jarvis, J. J. (1977) Linear Programming and Network Flows, John Wiley and Sons, NY. Bozer, Y. A. and Srinivasan, M. M. (1989) "Tandem Configurations for Automated Guided Vehicle Systems and the Analysis of Single Vehicle Loops," to appear in IIE Transactions. Burkard, R.E. and Derigs, U. (1980) Assignment and Matching Problems: Solution Methods with FORTRAN-Programs, Lecture Notes in Economics and Mathematical Systems #184, SpringerVerlag, NY. Finkbeiner, II, D. T. (1966) Introduction to Matrices and Linear Transformations, 2nd edition, W. H. Freeman and Company, San Francisco. Finke, G., Burkard, R. E. and Rendl, F. (1985) "Quadratic Assignment Problems," Working Paper, Department of Applied Mathematics, Technical University of Nova Scotia, Halifax, NS, Canada. Finke, G., Burkard, R. E. and Rendl, F. (1987) "Quadratic Assignment Problems," Annals of Discrete Mathematics, 31, pp.61-82. Kiran, A. S. and Karabati, S. (1988) "The Station Location Problem on Unicyclic Material Handling Networks," Working Paper, University of Southern California, Department of Industrial and Systems Engineering, Los Angeles. Kiran, A. S., Unal, A. T. and Karabati, S. (1989) "A Location Problem on Unicyclic Networks: Balanced Case," Working Paper 89-11, University of Southern California, Department of Industrial and Systems Engineering, Los Angeles. Koopmans, T. C. and Beckman, M. (1957) "Assignment Problems and the Location of Economic Activities," Econometrica, 25, pp.53-76. Kouvelis, P. and Kim, M. W. (1989) "Unidirectional Loop Network Layout Problem in Automated Manufacturing System," Working Paper 88/89-4-5, Department of Management, The University of Texas at Austin. Sahni, S. and Gonzalez, T. (1976) "P-Complete Approximation Problem," Journal of Associated Computing Machinery, 23, pp.555-565. Tompkins, J. A. and White, J. A. (1984) Facilities Planning, John Wiley and Sons, NY. 25

Appendix 4 Proof of Lemma 1. (=) Consider q=(co,-o,c,-co) and A = (aij) = S qm r m(i,j,k,) = m=l cor+(i,j,k) - or+(ij,l) + cor+(ik,l) - cor+jk,l) where aij is the coefficient associated with dij. Then, as shown in Table Ill, aij = aik = ail = ajk = aji = akj = 0, and consequently A = 0. The proof can be generalized by noting that, if any one of the above four terms of A, say, r+(ij,k) is replaced by r"(i,j,k), then we can maintain A equal to 0 simply by reversing the sign of ql. 4 (=>) Suppose there exists q=(qlq2,q3,q4) such that A = (aij) = qmrm(ij,k,l) = 0. m=l Since each column in Table Im contains exactly two nonzero elements, they must be of equal magnitude with opposite signs. Therefore, qm = +_c for some o>O (lm<4). U Table Im Coefficients of A. dj dij d il djk djl dki corf+(ijj) cO -co cO -cor+i~j,!) -co co -<O cor+(ijC,) co -c col -or+(ij) 0- co — 0o -AOr (jk, - co 0 0 0 0 A O 0 0 0 0 0 Proof of Lemma 3. By Lemma 2, the r th row of H can be represented as a linear combination of the rows of -G as well. Thus, det R1s = 0 for all r and s. U Proof of Lemma 5. Let Mi denote the i th row of a matrix M. Also, let P(r) be the set 26

of row numbers in G such that Hr = X akGk, where ak#O. (Note that P(r) cannot be ke P(r) an empty set due to Lemma 2.) Recall that Hr and Gk, ke P(r), are both composed of 0 or ~1. Furthermore, neither Hr nor Gk, ke F(r), is equal to 0, and by Lemma 1, all the ck's are equal in magnitude. Hence, ak is equal to +1 for all ke P(r). Consider the i th row of a matrix M. As shown in Finkbeiner (1966, p.102), if Mi can be expressed as the sum of two vectors, say, RI and R2, then det M = det M1 + det M2 where M1 (M2) is obtained by replacing the i th row of M by R1 (R2). Consequently, det R3s = det Rks, where Rks denotes the matrix P in which the s th row of -G is ke P(r) replaced by akGk, ke P (r). Hence, if se P (r), then det Rks = 0 for all ke P(r), which implies that det R3s = 0. However, if se P(r), then det Rks = -akdet P if k=s, and 0 otherwise. Thus, det R3s = -<sdet P = +det P. Therefore, det R 3 = 0 or ~det P for all r and s. Proof of Lemma 8. Consider an element matrix D=(dij). Suppose stations i and j in D are interchanged to obtain IY=(dij). Let us define the element column (row) of size n as the column (row) in which each element of (0,1,2,.-.,n-1) appears once and only once. For all k except k=i or j, column k in D' remains an element column, since only dik and djk are interchanged within column k. The elements in columns i and j in D move to columns j and i inlY, respectively, although the positions of dij and dji are interchanged. Two diagonal elements dii and djj become d jj and d ii, respectively, and hence maintain all diagonal elements inlY as 0. Hence, columns i and j in IY are also element columns. Therefore, all columns inoY are element columns. By the same argument, all rows in D' are element rows. Furthermore, all diagonal elements inD' remain 0. Therefore, D' is also an element matrix. M 27

Proof of Theorem 7. Let S(i,j) be a layout in which station i immediately precedes station j in the clockwise direction, S(j,i) be the same layout as S(ij) except that the station i and j are interchanged, Z[S] denote the material handling requirement of layout S, D=(dij) be the station distance matrix determined by S(ij), 8 denote the set of all stations except stations i and j, and C denote the length of circumference. Then, Z[S(iJ)] = fijdij + I fikdik + fjkdjk + fi(C-dij) + ~ fkidki + fkjdkj + ke k kE ke k 9 ~ ~ flandkmn. ke 0 me 0 Z[S(j,i)] = fij(C-dij) + fik(dik-dij) + fjk(djk+dij) + fjidij + fki(dki+dij) + kE kEe ke9 fkj(dkj-d) + ~ fkmdkm. ke E k e me Hence, Z[S(ij)] - Z[S(j,i)] =2fijdj - Cfij + fikdij - fjkdij + Cfji- 2fjidi- fkidij + I fkjdij ke k kE 0 kee k = 2dij(fi-fji)- C(fij-fji)+ dij{ fik- fjk- ~ fki + j fkj ke9 keO ke0 ke0 = (fij-fji)(2dij-C) + dij { (i) - g(j) - X(i)+ k(j) - 2(fij-fji) = -C(fij-fji) = 0, if fij = fji, n n where X(i) = ~fki, and g(i) = fik. k=l k=l 28

station 1. 12 0 3 2 input * output 4 * buffer buffer. /O station 6 5 10 7 9 Figure 1. A closed loop manufacturing system with two vehicles and 12 stations. site Figure 2. The circular representation of a CLP with five sites, where r14 is equal to r41, since site 1 and site 4 are symmetrically located around the circle. 29

M/C 1 M/C 2 M/C 3 I 0000 ooooo' 00000 oo00000 o00 -oI - 000 0 = = = =o= = = ooo' = — ~~ -,= ir = lTI _'_ _ I ____I _I I I r k nnn I - =1 ~ Ec1 -0OO00000 O 0 000. A0000000000 000 / 000000o l =~~~~~~~~ (a) Machine layout in a conveyor-supported manufacturing system. (Adapted from Tompkins and White 1984, p.407.) (b) Machine layout for a unidirectional robot arm. (c)Tool layout on a turret. Figure 3. Applications of the circular layout problem. 30

(a) sites (b) stations Figure 4. A layout example in the ED-CLP with eight stations. (a) dij+djk=dik (b) dU+djk=dik+n Figure 5. Precedence relationships of three stations around a circle. -1 B= -1 P 0 U w I v x I Il 1 b b3 (c) (a) (b) Figure 6. The structure of the basis of LP*. 31

Table I Examples for three types of matrices. 01234 02431 01234 20341 30214 40123 420 13 13042 34012 3 4 1 02 24103 23401 13420 41320 12340 (a) an element matrix (b) a circular element matrix (c) a standard matrix Table I Comparison of CPU seconds between Net Flow (NF) bound and Gilmore-Lawler (GL) bound. (N=5) M D S (N=8) M D S (N=12) M D Symmetric Flow Random Flow Even Medium Uneven Even Medium Uneven NF GL NF GL NF GL NF GL NF GL NF GL.006.019.009.010.006.015.005.005.006.006.006.006.008.024.005.023.004.019.002.002.002.002.003.003.002.021.002.019.002.018.005.005.002.004.002.003.003.021.005.023.005.017.002.006.003.005.004.007.004.017.004.020.002.017.008.016.006.014.006.011.004.023.002.023.002.025.007.014.004.010.002.008.006.024.004.022.002.017.006.012.005.011.004.008.004.017.003.010.004.013.003.006.003.003.002.003.008.017.004.013.004.012.006.008.004.006.002.005.285 5.621.146 5.037.152 4.945.075.204.070.182.044.107.071 5.781.075 5.625.109 5.188.209.406.183.258.127.336.128 6.860.052 6.447.069 5.800.089.165.099.192.065.085.086 5.429.081 5.222.06844.339.747.256.482.225.490.146 5.161.186 5.400.073 57.114.415.102.402.068.365.200 6.236.170 5.859.074 4.979.344.722.138.469.133.350.069 4.446.029 4.398.040 4.209.292.642.304.421.161.370.150 4.861.124 4.945.064 4.465.155.460.090.322.054.238.148 4.639.088 4.612.056 4.041.196.489.209.402.163.420 11.7 NA (2).4 NA 15.7 NA 18.8 142.8 11.0 111.9 15.0 156.3 29.4 1.6 9.3 23.9 145.0 27.0 182.0 11.6 129.5 41.2 33.8 18.8 109.5 626.4 46.0 363.4 94.2 391.7 38.8 NA 46.2 NA 28.3 NA 27.3 242.8 33.4 235.8 26.3 355.3 18.6 32.3 8.5 62.3 311.7 45.1 215.0 33.7 270.4 23.4 20.4 117.7 68.4 402.1 54.2 317.2 35.6 113.9 80.3 NA 50.1 NA 52.9 NA 56.3 344.2 64.9 249.5 26.6 151.7 43.7 38.5 28.0 45.9 307.0 32.0 238.1 22.0 110.8 27.9 24.9 27.1 44.2 280.9 31.6 231.2 19.3 223.4 (1) Flow Density: S = sparse, M = medium, D = dense. (2) exceeds one hour time limit. 32