Table 9.20 Branching on Node A-D *- 1 - 3 Where 6,, = 40 = max W (bound for node A-D 2-3 becomes 370 + 40 = 410). "

Table 9.21 Restriction as a Result of Assigning 2 - 3 to A-D (no reduction possible after restriction, so lower bound on node A-D *- 2-3 is 370; branching continues from node A-D <- 2-3 using the restricted cost matrix).

Figure 9.4 Branch-and-Bound Tree for Example 9.2.

.350

Table 9.22 All , Are Zero. (Arbitrarily consider node A-C 2-4; the bound on node A-C - 2-4 is 370 + 0 = 370; on node A- "- 2-4 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.)

Branch-and-bound 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 A-C - 2-4, Where 6, = 20 = max \ej (the bound for node A-C 1-3 thus becomes 370 + 20 = 390).

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?

9.2 HEURISTIC PROCEDURES-CRAFT AND HC63-66

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 pair-wise exchanges in order to improve a starting solution, which the analyst must specify. Pair-wise 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 cost-attractive 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 1-2 1-3 1-4 2-3 2-4 3-4

D«2 Cost Change -100 -50 -80 -60 90 -100

Figure 9.5 Starting Solution for CRAFT (Cost = 510).

Of the six possible pair-wise exchanges, either pair 1-2 or pair 3-4 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 pair-wise exchanges are shown in Figure 9.6.

A.2 B.3 C«4 Exchange Pair 1-2 1-3 1-4 2-3 2-4 3-4 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 pair-wise exchange effects are given in Figure 9.7.

A»2 B.l C«4

• D.3

Exchange Pair 1-2 1-3 1-4 2-3 2-4 3-4

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 HC63-66 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 pair-wise 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, K-l,...,l, steps away from each facility in the eight different dirertions. HC63-66 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 pair-wise 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 pair-wise exchanges. Starting with the solution in Figure 9.8, the effects for the first iteration are reported below.

Exchange

Pair 1-2 1-3 1-4 1-5 1-6 2-3 2-4 2-5 2-6 3-4 3-5 3-6 4-5 4-6 5-6 Cost

Change 10 30 10 25 30 30 20 40 45 5 70 110 90 60 5

As no pair-wise exchange will yield a cost improvement, a pair-wise 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 in-DIMENSIONAL 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.

One-Dimensional 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 one-dimensional 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 one-dimensional 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 J-l

= XDX ~ XWX + i XDX,

= XBX, since w,. = w by symmetry.