Chapter 11, Problem 46AP

Summary Introduction

Interpretation: A real estate firm wishes to open four new offices in Boston area and they are having six potential sites available. Based on the number of employees in each office and the location of the properties that each employee will manage, the firm estimated the total travel time in hours per day for each office and each location. The optimal assignment of offices to sites to minimize employee travel time needs to be determined.

		Offices
		A	B	C	D
	1	10	3	3	8
	2	13	5	2	6
Sites	3	12	9	9	4
	4	14	2	7	7
	5	17	7	4	3
	6	12	8	5	5

Concept Introduction: A discrete facility location problem is considered, when a balance has to be achieved between the minimum and maximum number of customers, wherein there is a difference that arises between the allocation of these customers made to every plant.

Answer to Problem 46AP

The optimal travel time has been derived as 17.

Explanation of Solution

Given information:

		Offices
		A	B	C	D
	1	10	3	3	8
	2	13	5	2	6
Sites	3	12	9	9	4
	4	14	2	7	7
	5	17	7	4	3
	6	12	8	5	5

When there are no inter-departmental interactions and a discrete set of alternative locations could be considered, then assignment problems can be considered to be appropriate. Following are the procedure for solution for assignment problems:

1. The smallest number in row 1 needs to be identified and it should be subtracted from all the entries in that row. This procedure needs to be repeated for all the rows in cost matrix.
2. Similarly, the smallest number in column 1 needs to be identified and it should be subtracted from all the entries in column 1. This procedure needs to be repeated for all the columns in cost matrix.
3. At a certain point, each column and each row will have at least a zero. If there is possibility for making a zero assignment, then the same can be done, which in turn will be the optimal solution, and if not, then proceed to the next step.
4. The maximum number of zero cost assignments needs to be determined, which will be equal to smallest number of lines adequate to cover all zeros. These lines are not necessarily unique and are found by inspection. The number of lines drawn should be less than the maximum number of zero cost assignments.
5. The smallest uncovered number should be identified and proceed with the following steps:
1. Subtract smallest uncovered number from all the other uncovered numbers.
2. Add this to the step at the point where the line crosses.
3. Return back to step 3

Step 1: The below shown matrix, not being a square matrix, dummy rows to balance the sites and offices are added.

	Offices
Sites	A	B	C	D
1	10	3	3	8
2	13	5	2	6
3	12	9	9	4
4	14	2	7	7
5	17	7	4	3
6	12	8	5	5

By adding the dummy rows the matrix has been modified as shown below:

	Offices
Sites	A	B	C	D	E	F
1	10	3	3	8	0	0
2	13	5	2	6	0	0
3	12	9	9	4	0	0
4	14	2	7	7	0	0
5	17	7	4	3	0	0
6	12	8	5	5	0	0

Step 2: The row reducing matrix needs to be performed by subtracting the smallest number from each row. Since in this case, the resultant zero assignment has been achieved for each office, further column reduction matrix is not performed.

	Offices
Sites	A	B	C	D	E	F
1	0	1	1	5	0	0
2	3	3	0	3	0	0
3	2	7	7	1	0	0
4	4	0	5	4	0	0
5	7	5	2	0	0	0
6	2	6	3	2	0	0

Step 3: From each site identifying of the zero assignment gives the following matrix

	Offices
Sites	A	B	C	D	E	F
1		1	1	5	0	0
2	3	3		3	0	0
3	2	7	7	1		0
4	4		5	4	0	0
5	7	5	2		0	0
6	2	6	3	2	0

Thus the optimal solution for travel time will be $10+2+2+3+0+0=17$