back start next
[start] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [ 40 ] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51]
40  15 HEIGHT Radiographyp"j       ci c3     " t j" 1 
Figure 9.1 Floor Configuration. convection coils. Certain departments had to be under the cranes. Figure 9.1 shows the configuration of the shop floor. From the terms of the contract and a knowledge of the production processes involved, work flows (in tons) were determined. These are given in Table 9.1. Transportation costs were not as easily or as accurately found. Different transportation methods, operated at different costs, were to be used (towmotor, crane, and dolly). These costs were based on time and motion studies, maintenance records, and the experience of production personnel. Table 9.1 Interfacility Work Flow. FROM  .....z < §!   §g    § cr   ICO  (CO  LL. CO   > < CD < CC  LOADING/ UNLOADING              ROLL RACK     1920  1480        6000  CONVECTION BOXES             3200  CONV TUBE STORAGE    1920           RADIANT COIL ASSEMBLY             1080  CROSSOVER              RADIANT HOOP ASSEMBLY              HOOP STORAGE              TUBE SHEET STORAGE              FITTINGS STORAGE   3400  1920   1440                      RADIOGRAPHY   6000  3200   1080        
This sketch of an actual study indicates the typical complexity of floor layout problems and emphasizes the need to combine the methods of this chapter with judgment. The three elements of the typical layout problem are present: (1) a set of facilities to be located, with each requiring a certain amount of space; (2) interfacility weights, computed as work flow in tons times cost per ton per unit distance; and (3) a limited amount of space available in which to locate all the facilities. The concept of locating spaceconsuming facilities is not limited to floor layout problems. The quadratic assignment model has been used to locate the instruments on helicopter control panels by Wyman and Callahan (1975). Each instrument corresponds to a facility, the control panel is the available space, and the weights correspond to the frequency of eye movement between each instrument pair during a sample of typical flight patterns. The study resulted in the discovery that helicopter instrument panels should have different configurations from those of fixedwing aircraft. In devising solution algorithms, some assumptions must be made concerning distances. A common assumption is that distances between spaces are rectangular and measured "centertocenter." This corresponds to the factory or warehouse floor application where movement takes place along a rectangular grid of aisles. In applications like the aircraft instrument panel, Euclidean distances may be more appropriate. If the effort involved in locating the proper gauge goes up more than linearly the farther away the pilot must look, squared Euclidean distances might be substituted for Euclidean distances to represent "costs." A mathematical programming formulation of problem (QAP) for locating m facilities is: minimize 2 2 S 2 w.djiX.jXki . /I k\ j=l f1 subject to (9.1) for all j for all / X;j = 0 or 1, for all where is the nonnegative weight that multiplies the distance between facilities i and k; dj is the distance between locations j and £; and Xl, = I if facility i is assigned to location j, 0 otherwise.
Each term of the quadruple summation considers the assignment of a pair of facilities to a pair of locations. The Wi,4i product is the weighttimesdistance component of the cost function resulting from the flow between facility / and facility over the distance between locations ; and £ The first set of constraints requires each location to have a single facility located there. The second set of constraints ensures that each facility is assigned to a single location. There may be more locations than facilities or the facilities may require different amounts of space. The former problem may be solved by using dummy facilities in the formulation, the latter by dividing facilities into subfacilities each requiring a standard amount of space and using large values for the interfacility weights between the component parts. The latter approach is not guaranteed to generate an optimal layout for the original problem however. Problem (QAP) is not amenable to solution by standard linear and nonlinear programming algorithms. Some insight into the difficulty of formulating the problem as a wellbehaved programming problem may be gained by examining a numerical example. Example 9.1 Suppose we wish to locate three offices along a corridor, keeping a unit distance between them. Interoffice weights are given in Table 9.2. The available locations along the xaxis are: : = 1, x = 2, and X = 3. Let the (unknown) locations of offices 1, 2, and 3 be Xl, , and , respectively. Then we may write this instance of problem (QAP) as: minimize 3X  xl \r x,  + 4x2  subject to x,  X2I 3= 1, x,  1, X2  X3I ?i 1, 1 < X, < 3, 1 < X, < 3, 1 < < 3. Table 9.2 Interoffice Weights w,,. Office 1 2 3 Figure 9.2 Feasible Region (Shaded Areas). The objective function is convex and can be linearized as in Section 4.1. The main difficulty is with the constraints. Using the first constraint as an example, x,  X2I s= 1 implies either x,  X2 = 1 or x, b X2 1. This eitheror pair of constraints defines a disjointed feasible region as shown in Figure 9.2. Unfortunately, linear and nonlinear programming algorithms invariably require the feasible region to be connected. 9.1 SOLVING PROBLEM (QAP) BY A BRANCHANDBOUND TECHNIQUE The combinatorial nature of problem (QAP) suggests the use of branchandbound techniques. Because of large computer storage space requirements and computation times these techniques are restricted to relatively small problems. However, it is instructive to consider one such approach. It is probably best to specify the method through a numerical example. To assist comprehension, we will provide complete detail. Should this begip to seem excessive, the reader may wish to skip to the "big picture" depicted in Figure 9.4. Example 9.2 Table 9.3 gives the symmetric matrix of interfacihty weights, and Figure 9.3 shows the required configuration of a problem with four facilities.! Assuming unit square locations and rectangular distances, we obtain the symmetric distance matrix as given in Table 9.4. (For ease of exposition, locations will be denoted by the letters A, B, C, D.) Table 9.3 Interfacihty Weights for Example 9.2.
Figure 9.3 Required Configuration. Table 9.4 Distance Matrix. The first step in the branchandbound procedure is to construct a matrix that shows the cost of assigning all possible facility pairs to each pair of locations. Let M be the number of different pairs of objects that may be chosen from m different objects. Then M = (m  m)/2 and the cost matrix will be of dimension M X M. Table 9.5 gives the assignmenttolocation cost matrix for the example. We next cite a property [theorem 368 of Hardy, Littlewood, and Polya (1952)] of the inner product of two vectors to calculate a lower bound on the optimal solution value. Table 9.5 Cost Matrix of Assigning Each Pair of Facilities to Each Pair of Locations. Facility Pair             Interfacility Weight            Location         Pair  Distance    Cost Matrix                                                   
Property 9.1 [Minimizing the inner product of two vectors]. Given the vectors a = ( „ 2,, ), and = (b„b2,...,b,J, the inner product ab = 2 a,b, is minimized when the elements of either a or b are arranged in ascending order, and the elements of the other vector are arranged in descending order. Intuitively, this arrangement forces the angle between the two vectors to be as close to 90° as possible. The second step in the branchandbound method is to rank the distance and cost components so that the sum of the diagonal entries of cost matrix becomes a lower bound on the cost of the optimal solution. Unfortunately, the diagonal assignment is usually not feasible. Table 9.6 shows this arrangement. The lower bound is 30 + 40 f 60 + 50 I 70 + 100 = 350. The next step is to "reduce" cost matrix by successively subtracting constants from columns and rows. The object is to end up with all diagonal entries being zero, while keeping all other entries nonnegative. Continued reference to the matrix will be used as (an expedient) to mean the latest version of the cost matrix. First, subtract from each column the diagonal entry in that column as shown in Table 9.7. The sum, R, of the reducing constants is 350. The optimal assignment will remain unchanged because subtracting a constant from any row or column merely reduces the optimal cost by that amount. As we will need all entries of the cost matrix to be nonnegative, the next step is to subtract from each row the minimum entry in that row as shown in Table 9.8. The sum of the reducing constants now isJ? = 240. The process of subtracting diagonal entries and minimum Table9.6 Cost Matrix with Ranked Distances and Flows. 1 . . . . . Facility Pair             Interfacility Weight            Location         Pair  Distance    Cost Matrix                                                   
[start] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [ 40 ] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51]
