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]
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
Get Answers For Free
Most questions answered within 1 hours.