Industrial Engineering Chapter 5 Homework Because of the nature of the maintenance

1

SOLUTIONS TO SELECTED EXERCISES IN CHAPTER 5

5.1. Without using formulations, briefly describe the purpose of the typical mathematical

models used in facility planning. Provide typical applications for each of these models.

Solution

(a) Minisum location model: used to find the location of a new facility in such a way

5.2. Find the optimal solution for the minisum location model assuming: (a) squared

Euclidean distances; (b) Euclidean distances. Find the optimal location of a new machine

assuming existing machines located at (4,2), (8,5), (11,8), and (13,2) with weights equal

to 1/6, 1/3, 1/3, and 1/6, respectively.

Solution

(a) Squared Euclidian distances:

−+−=

iii

)yb()xa(d

22

2

(b) Euclidean distances:

−+−=

iii

)yb()xa(d

22

5.3. Four existing facilities are located at (4,2), (8,5), (11,8), and (13,2). The weights are

equal to 1/6, 1/3, 1/3, and 1/6, respectively. (a) Draw the resultant weight diagram for x.

(b) Draw the resultant weight diagram for y. (c) Determine the optimal solution from

both diagrams. (d) Construct the grid for finding contours. (e) Draw the contour through

the point (6,9) and the contour through the point (9,6).

Solution

(a) Resultant Weight Diagram for x:

-1

(d) Grid for finding contours:

-1

+1

1 ⅔0–⅔-1

4

(e) Contour through point (9,6)

5.4. Four machines are located in a plant at points (0,10), (20,0), (40,10), and (10,10).

These machines require maintenance at expected frequencies of 10, 11, 12, and 5 times

per month, respectively. Because of the nature of the maintenance, all machines must be

maintained at the maintenance center. A machine can be serviced by exactly one

maintenance center. Moreover, the cost of transporting the machines to and from the

maintenance center is $10 per unit of distance, including the cost of lost profits resulting

from the machines being down. The monthly cost of owning and operating a maintenance

center is $6000. Rectilinear travel is assumed. (a) Calculate the number of possible

allocations for two maintenance centers. (b) List all possible combinations indicating

which machines are allocated to which maintenance center. (c) Find the total cost per

month associated with the allocation of machine 1 to the first center, and machines 2, 3,

and 4 to the second center.

Solution

+1

1 ⅔0–⅔-1

5

(b) Combination F1 F2

1 1 2,3,4

(c) w1 = 10, P1(0,10)

Based on results shown below, the location of the second center F2 is x2 = 20, y2 = 10.

P4 P2 P3 P2 P3 P4

5.5. Consider a single-facility rectilinear mini-max location problem with existing

facilities located at (2,10), (7,9), (7,12), (3,15) and (1,14). (a) Find the optimal solution.

(b) Find a contour line of value 8. Draw a graph showing the location of all facilities, the

optimal solution, and the contour.

Solution

(a) c1 = 12, c2 = 19, c3 = 2, c4 = 13, c5. Any point of the line segment joining the points

6

Border Lines:

x+y ≤ 20

Corner Points:

(5, 15)

5.6. Consider a mini-max single-facility location problem with existing facilities at (1,1),

(2,2), (3,3) and (4,4). Assuming rectilinear distances, find the optimal location of the new

facility and the corresponding value z of the objective function.

Solution

a b a+b -a+b

6 12

3

15

3 9

7

5.7. In Problem 5.6 draw the contour corresponding to the value z = 10. Compute the

coordinates of each corner point of the contour.

Solution

c1=2, c2=8, c3=0, c4=0

5.8. Consider the problem of designing a complex of six novelty and craft shops A, B, C,

D, E, F in a resort area. The six shops are to be located in a rectangular building

consisting of six locations arranged as two rows and three columns. The corresponding 6

cells or sites in a rectangular grid of the floor of the building are numbered from left to

right and top to bottom as 1, 2, 3, for the first row; and 4, 5, 6 for the second row. Each of

the six sites is a candidate for the location of each shop. The travel costs between

locations, shown in the matrix on the left, are proportional to the rectilinear distances.

Distances are measured in units of site widths, between the centers of sites. The matrix on

the right shows the number of trips between facilities:

0 1 2 1 2 3 0 4 6 2 4 4

1 0 1 2 1 2 4 0 4 2 2 8

2 1 0 3 2 1 6 4 0 2 2 6

1 2 3 0 1 2 2 2 2 0 6 2

2 1 2 1 0 1 4 2 2 6 0 10

3 2 1 2 1 0 4 8 6 2 10 0

(a) What kind of model can be used for solving this problem? (b) Find a lower bound on

the total cost. (c) If shops A, B, C, D, E and F are assigned to locations 2, 4, 5, 3, 1, and

6, respectively, find the total cost of this assignment. (d) How many terms does the

objective function have? (e) Find the terms (coefficients and variables) associated with

the assignments of facilities A and B.

Solution

(1,11)

8

(b) Flow values arranged from high to low:

Distance values arranged from low to high:

(c) For each cell in the following table the entry is equal to (V)(d).

Shop 1 Shop 2 Shop 3 Shop 4 Shop 5 Shop 6

Shop 1 (4)(2) (6)(1) (2)(1) (4)(1) (4)(2)

5.9. There are three plants A, B, and C with potential sites 1, 2, and 3. The following

costs per trip between locations are known:

– 3 2

3 – 6

2 6 –

The number of trips between plants can be summarized as follows:

– 8 5

8 – 4

5 4 –

Write the mathematical formulation of the model, including the numerical value of each

coefficient in both the objective function and each constraint. Find the optimal solution.

Solution

(a) Objective Function:

(b) Constraints:

xA1 + xB1 + xC1 = 1 (location 1)

(c) Find a lower bound on the value of the objective function. Sequence of flows in

5.10. Machines 1, 2, 3, 4 and 5 are located at the points (-1,0), (4,1), (-7,2), (-2,3), (5,4),

respectively. There are 6, 9, 4, 1, and 2 trips per week, respectively, between the

machines and a new facility. (a) Use the resulting force diagram to calculate the x-

coordinate of the optimal location for a minisum model considering rectangular distances.

(b) Find the optimal location using a mini-max model.

Solution

-22

-14

-7 -2 -1 4 5

10

(b) Using the mini-max model:

ai b

iai+bibi -ai

-1 0 -1 1

5.11. We are interested in determining the location (x, y) of an ambulance. There are four

5.12. Machines 1, 2, 3, and 4 are evenly spaced along a circumference having a known

radius. The number of trips to a new facility is shown in the diagram given below for each

machine. Using rectangular distances and the minisum model, find the location of the new

5.13. In a company, departments send jobs to be processed to locations each having a

microcomputer available. Let tij be the time needed to take one job from Department i to

Location j. Assume that i = 1,2,…, n; j = 1,2,…, m. Moreover, let di be the demand (number

of jobs) from Department i. Let K be the number of microcomputers available for

11

processing the jobs sent by the departments. Formulate a mathematical model to determine

the location of each microcomputer (at most one microcomputer per location) in order to

minimize the total time. Assume that all jobs from each department must be assigned to

exactly one location.

Solution

xij = 1 if the demand from department i=1,…,n is assigned to location j=1,…,m

∑∑

=iiji

jij xdcZMinimize

m

5.14. Given the assignment (1, 3, 4, 2) and the matrices

⎟

⎠

⎞

⎜

⎝

⎛

=

0985

90410

8407

51070

D

⎟

⎠

⎞

⎜

⎝

⎛

=

0492

4048

9403

2830

W