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]
42 Table 9.20 Branching on Node AD * 1  3 Where 6,, = 40 = max W (bound for node AD 23 becomes 370 + 40 = 410). " Location    Facility Pair    Pair                                                                                           
Table 9.21 Restriction as a Result of Assigning 2  3 to AD (no reduction possible after restriction, so lower bound on node AD * 23 is 370; branching continues from node AD < 23 using the restricted cost matrix). Location Pair    Facility Pair                                                   
Figure 9.4 BranchandBound Tree for Example 9.2. .350 Table 9.22 All , Are Zero. (Arbitrarily consider node AC 24; the bound on node AC  24 is 370 + 0 = 370; on node A " 24 the bound is 370 and the procedure identifies the ABCD assignment 2 14 3 . This is an optimal solution because no other active node has a lower bound.) Location Pair    Facility Pair      23 12                                       
Branchandbound is a general method that gives optimal solutions. Any distances may be used. The implementation here is typical of several proposed methods. The maximum problem size that can be solved exactly on the largest generally available computers is about m = 16 facilities, whereas total enumeration of the set of all permutations of I,2,...,/n can solve problems up to about size w = 11.
Table 9.23 Branching on Node AC  24, Where 6, = 20 = max \ej (the bound for node AC 13 thus becomes 370 + 20 = 390). Locaiion    Facility Pair   Pair      34 14                                     
Table 9.24 No Reduction Possible After Restriction for Node A < 1  3 (the lower bound on this node is 370; and the node defines the alternate optimal solution 34? Location    Facility Pair    Pair    2 3 12    AD AC BD AB BC  OO  QC 0    
9.2 HEURISTIC PROCEDURESCRAFT AND HC6366 To "solve" large (m > 16) instances of problem (QAP) one must resort to heuristic procedures. Most of these methods are simplistic in nature and similar to each other. We briefly discuss two of them here. The first of these, CRAFT (computerized relative allocation of facilities technique) relies on the principle of pairwise exchanges in order to improve a starting solution, which the analyst must specify. Pairwise exchanging cannot be generally regarded as a "greedy" method because each variable is not changed optimally at each iteration of the solution method. A restriction is imposed at each move by specifying that if it is costattractive to move facility /, say, from location A to location B, the CRAFT procedure also moves the facility presently in location to location A. This is done even when a better strategy may be to move this latter facility elsewhere. For this reason and others, CRAFT may not obtain optimal solutions. Of course, there are many ways to modify the basic approach of CRAFT to obtain improved versions. Our purpose here is to provide a description of two classical heuristic approaches to solving problem (QAP). Example 9.3 We illustrate CRAFT using the problem data of Example 9.2, and the starting solution indicated in Figure 9.5. A«l B»3 C«4 Exchange Pair 12 13 14 23 24 34 D«2 Cost Change 100 50 80 60 90 100 Figure 9.5 Starting Solution for CRAFT (Cost = 510). Of the six possible pairwise exchanges, either pair 12 or pair 34 could be exchanged to obtain a cost reduction of 100. We arbitrarily choose to exchange the locations of facilities 1 and 2. The second solution and the six possible pairwise exchanges are shown in Figure 9.6. A.2 B.3 C«4 Exchange Pair 12 13 14 23 24 34 D«l Cost Change 100 40 10 30 100 100 Figure 9.6 Second CRAFT Solution (Cost = 410). Facilities 1 and 3 are now exchanged. This solution and the associated pairwise exchange effects are given in Figure 9.7. A»2 B.l C«4 • D.3 Exchange Pair 12 13 14 23 24 34 Cost Change 80 40 Figure 9.7 Final CRAFT Solution (Cost = 370). The CRAFT procedure terminates owing to the positive cost changes for each exchange pair possibility. As this is one of the two optimal solutions, the heuristic has performed well. The HC6366 method employs the same basic algorithmic concept as CRAFT. In addition, it requires the floor layout to be a rectangular grid of unit squares. Rather than checking all pairwise exchanges at each step.
however, only pairs directly above, below, to either side, or on any of the four 45° diagonal Unes emanating from the facility to be evaluated are checked for "move desirability." In addition, the user specifies a maximum number (say, K) of steps away that candidate pairs are tested. In a single pass the algorithm checks for pair exchanges K, Kl,...,l, steps away from each facility in the eight different dirertions. HC6366 checks fewer candidate pairs at each step than does CRAFT and is therefore computationally faster. Example 9.4 As an illustration of the limitations of pairwise exchange methods, consider an m = 6 facility example with interfacility weights as given in Table 9.25. A candidate solution vnth a cost of 70 is shown in Figure 9.8. A»4 B»3 C«2 D«l E»5 F»6 Figure 9.8 Possible Solution for Example 9.4. For this example, at each iteration there are 15 possible pairwise exchanges. Starting with the solution in Figure 9.8, the effects for the first iteration are reported below. Exchange Pair 12 13 14 15 16 23 24 25 26 34 35 36 45 46 56 Cost Change 10 30 10 25 30 30 20 40 45 5 70 110 90 60 5 As no pairwise exchange will yield a cost improvement, a pairwise exchange method would terminate with this solution. The optimum solution shown in Figure 9.9 has a cost of 55, which represents a 21.4% cost reduction. A»l B»2 C«3 D»4 E.5 F.6 Figure 9.9 Optimum Solution for Example 9.4. Table 9.25 Interfacility Weights for Example 9.4. 9.3 THE HALL inDIMENSIONAL QUADRATIC PLACEMENT ALGORITHM We now describe the Hall method for generating optimal floor layout patterns where the assumption of minimizing weighted squared Euclidean distances can be made. The method is an optimizing technique that can solve large problems. The main advantage is that the facilities are not assigned to predetermined locations. The Hall method provides a layout pattern; the specific assignments or layouts are done by the analyst. In this regard, there is evidence that in some cases, an experienced practitioner can improve on the solution given by a heuristic algorithm. OneDimensional Problems Let IV be an m X m symmetric "connection" matrix in which the entry W/j is the weight between points / and j; wj = w, and vw,, = 0. Let the unknown vector of locations in one dimension be given by = (Xi,X2,...,x,„). Then the onedimensional quadratic placement problem is stated as: minimize Q{X) = x 2 Z i ~ subject to XX = 1, (9.2) where XX denotes the inner product of X with itself, ie, XX = x\+xl + ...+xl,. The constraint is added to prevent the solution x, = X2 = ... = x,„ = 0. The solution method will be developed for onedimensional problems and then generalized to two or more dimensions. It will be convenient to write Q{X) in matrix form. LetvW, and w., be the row sum and the column sum, respectively, of the connection matrix W. Then let D be a diagonal matrix with d„ = w,, and let matrix be given by = D  W. We can write QiX) in terms of the matrix, as indicated by the following property. Property f.2 [Quadratic equivalence using the matrix ]. Q(X) = XBX. proof: = i i  ,) = i i  2 , , + x) t\ j] /=1 j=\ ni m m m  (21 W.X?  2 2 S "uXiXj + X w.,x) /1 Jl = XDX ~ XWX + i XDX, = XBX, since w,. = w by symmetry.
[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]
