Question

The Assignment Method The Operations Manager of a construction company wants to assign four contractors to four jobs in such a way as to minimize the time taken to complete four buildings of a special kind and size. Based on experience, the times taken (in months) for each contractor to complete each job are given in the table below

JOBS		CONTRACTOR
	1	2	3	4
1	15	15	16	14
2	20	18	16	19
3	24	26	20	23
4	30	35	38	25

Required:- a. Using the Hungarian (manual) method, determine the optimal assignment of contractors to jobs in order to minimize the total time taken to complete the jobs. Indicate this overall time and show all working. [12 marks]

b. Write an LP formulation that could be used to solve this problem with the relevant LP software packages. [13 marks]

Answer 1

Hungarian Method

1) Row reduction:

In each row, subtract the lowest element of row from each elements of row.

	Contractors
Jobs	1	2	3	4	Row minimum
1	15	15	16	14	14
2	20	18	16	19	16
3	24	26	20	23	20
4	30	35	38	25	25

Row minimized matrix

	C1	C2	C3	C4
J1	1	1	2	0
J2	4	2	0	3
J3	4	6	0	3
J4	5	10	13	0

Step 2: Column reduction

In each column, subtract the lowest element of column from each elements of column.

                     

	C1	C2	C3	C4
J1	1	1	2	0
J2	4	2	0	3
J3	4	6	0	3
J4	5	10	13	0
Column minimum	1	1	0	0

Column reduced matrix

	C1	C2	C3	C4
J1	0	0	2	0
J2	3	1	0	3
J3	3	5	0	3
J4	4	9	13	0

Assignment of the jobs to contractors:

Only three assignments are possible, whereas 4 assignments are required. Thus the solution is not optimal. Further reduce the matrix.

1. Draw lines over row/column such that all the zeros are covered with as many as minimum lines.

2. From the uncovered elements select lowest element (L)

3. Subtract the L form the uncovered elements

4. Add the L to elements where lines intersects

5. Keep the remaining elements unchanged.

Reduced matrix 1:

	C1	C2	C3	C4
J1	0	0	3	1
J2	2	0	0	3
J3	2	4	0	3
J4	3	8	13	0

Reassign the jobs to contractor:

first assign J4, then J3, then J2 and J1

Since the number of assignement is equal to no. of row or columns, the optimal solution is obtained.

Optimal asignment and total time is as follows:

Jobs	Contractors	Time
J1	C1	15
J2	C2	18
J3	C3	20
J4	C4	25
total time	78

Total time = 78