Question

Question 3

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]

Answer 1

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

a.

Step 1: Identify the smallest element of each row and subtract from all elements of the row. This will make sure we will have one 0 in each row

	Contractors
Jobs	1	2	3	4
1	1	1	2	0
2	4	2	0	3
3	4	6	0	3
4	5	10	13	0

Step 2: If each row and each column does not have at least one 0 then Identify the smallest element of each columns and subtract from all elements of the column. This will make sure we will have one 0 in each column

	Contractors
Jobs	1	2	3	4
1	0	0	2	0
2	3	1	0	3
3	3	5	0	3
4	4	9	13	0

Step 3

Draw horizontal/vertical lines to cover 0's. If the minimum number of lines to cover 0's equal with the number of row/columns then go to step 5 else go to step 4

Here, minimum number of lines to cover all 0's is 3 which is less than no of rows/columns(4) so go to step 4

Step 4

Identify the smallest number from list of uncovered elements mentioned in step 4. Add the smallest number to the elements present in horizontal and vertical lines and add to the uncovered elements

	Contractors
Jobs	1	2	3	4
1	0	0	3	1
2	2	0	0	3
3	2	4	0	3
4	3	8	13	0

Here, smallest uncovered element is 1 which is added to 2 (the intersection element of Row 1, column 3) and 0 (the intersection element of Row 1, column 4) and subtracted from the uncovered elements

Now start we did in step 3 to cover the 0's by minimum number of horizontal/vertical lines

As now, number of horizontal/vertical lines matches with the number of rows/columns so we can proceed with step 5

Step 5

Assignment is such that we will assign the first cell with element 0 to Job 1 and cross the rest of the 0's from that row and will do similarly till all the jobs get assigned

Optimal assignment :

Job 1 => Contractor 1

Job 2 => Contractor 2

Job 3 => Contractor 3

Job 4 => Contractor 4

Total time taken to complete the job = 15+18+20+25 = 78 minutes