Question

4. McTavish Cleaning Inc. provides a basic house-cleaning service to stressed-out trainee executives. This basic house-cleaning service includes four components, namely, vacuuming, kitchen-cleaning, bathroom-cleaning, and general straightening-up. McTavish employs a total of five maid-persons and wants to allocate four of them to its basic house-cleaning service with the objective of minimizing the total time it takes to provide the service. The time (measured in hours) it takes each maid-person to provide each component is listed in the following table: Vacuum Kitchen BathroomStraighten-Up Harold Betsy Mildred Jennifer George 2 4 4 i) Use the Hungarian Method to determine how McTavish should allocate their staff in order to minimize the total time that it takes to provide the basic house-cleaning service. i) What is the minimum total time that it takes to provide the basic house-cleaning service? iii) Would your answers to parts i) and ii) change if George were to refuse to do any more vacuuming? If so, how?

Answer 1

STEP 1

Make sure the matrix is square with equal number of rows and columns.

Here the number of rows and columns are not equal. Hence add an additional column to get equal number of rows and columns by the addition of dummy columns.

Assign the largest number in the matrix to each cell in the dummy column   

Also, George is refusing to do vacuuming. As in dummy cells, assign the largest number in the matrix to the vacuum cell of George/. The largest number is 9.

Vecum Kitchen Bathroom Straighten-up dummy Harold Betsy9 Mildred8 Jennifer 7 George95

STEP 2   

• Reduce the rows-Subtract the minimum value of each row from that row so that we get at least one zero in each row
• eg the minimu, value is 1 in row 1 .reduce 6,5,2,1,9 by 1 to get 5,4,1,0,8
• 
  Vacuum Kitchen Bathroom Straighten-Up dummy Harold Betsy6 Mildred4 Jennifer 4 George5
  

STEP 3   

• Reduce the columns-Now subtract the minimum value of each column from that column , so that we get atleast one zero in each column

18 reduce column Vacuum Kitchen BathroomStraighten-Up dummy Harold 21 Mildred Jennife0 George1 24 0

  

STEP 4

Cover the zero elements- Now cover the zero elements with the minimum number of lines possible. Instead of lines , I have used yellow fill

We have 2 possibilities.

       

ines VacuumKitchen BathroomStraighten-Up dummy Harold Betsy Mildred Jennifer 0 George1

                                             

Vacuu Kitchen BathroomStraighten-Up dummy Harold Betsy Mildred Jennifer George1 4 4

STEP 5

Check for optimality

Check whether The number of lines is equal to the order of matrix.

Here minimal number of lines=5

Which is equal to

the order of matrix =5 .

Hence the matrix is optimized.

]STEP 6

• 0's positions determine the possible combination.
• Select matchings ie the zeros, so that each row or column has only one zero selected.
• This combination may also include dummy

VacuumKitchen BathroomStraighten-Up dummy new Harold Betsy Mildred 0 Jennifer 0 George 1

STEP 7

• Now after selecting the matchings (zeros), disregard the dummy column
• Apply this to the original matrix.
• This shows who does what work and associated time taken

Vacuum Kitchen BathroomStraighten-Up Harold Betsy Mildred Jennifer0 George

• 
  time taken Harold Bathroor 2 Betsy Straightd3 Mildred Kitchen 5 Jennifer Vacuum 7 George total 17
  

MINIMUM TIME= 17 HOURS

2.

now George is also refuseing other works-clean any more kitchens and bathrooms

so as in answer 1 , assign the largest number in the matrix to the cells of George- kitchens and bathrooms

the allocation of jobs remains the same as before( in answer 1)

Straighte Vacuum Kitchen Bathroom n-Up dumm Harold Betsy Mildred Jennifer George9

reduce row Straighte Vacuum Kitchen Bathroom n-Up dummy Harold Mildred Jennifer George reduce column Straighte Bathroom n-Up dummy Vacuum Kitchen Harold Mildred Jennifer George

ines Straighte Bathroom n-Up dummy Vacuum Kitchen Harold Mildred Jennifer Straighte Bathroom n-Up dummy Vacuum Kitchen Harold Mildred Jennifer

		time taken
Harold	Bathroom	2
Betsy	Straighten-Up	3
Mildred	Kitchen	5
Jennifer	Vacuum	7
George
	total time	17