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 Radiography-p"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 space-consuming 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 fixed-wing aircraft.

In devising solution algorithms, some assumptions must be made concerning distances. A common assumption is that distances between spaces are rectangular and measured "center-to-center." 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 f-1

subject to

(9.1)

for all j

for all /

X;j = 0 or 1, for all

where is the non-negative 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 weight-times-distance 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 well-behaved 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 x-axis 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 - x-l -\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

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 either-or 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 BRANCH-AND-BOUND TECHNIQUE

The combinatorial nature of problem (QAP) suggests the use of branch-and-bound 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.

Facility



Figure 9.3 Required Configuration.

Table 9.4 Distance Matrix.

Location

The first step in the branch-and-bound 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 assignment-to-location 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 branch-and-bound 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 non-negative. 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 non-negative, 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

Table-9.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]