Question

Use the Hungarian Method to solve the following Assignment Problem.

Consider the following management decision problem: you have 4 employees E1, E2, E3, and E4 that must be reassigned to new jobs J1, J2, J3, and J4 (which they can all "sort of" do, with different training and quality costs) - and you must decide which employee should do which job (i.e., you need to make an assignment which has the least total cost for the company). Below is the cost matrix showing what the costs would be for assigning each employee to one of the jobs. You want to minimize the total cost for an assignment of the employees each to one job,

i.e., to minimize Σ_i (cost for Ei to do job Jπ(i)) where π(i) is the label of the job that employee i is assigned to.

	J1	J2	J3	J4
E1	75	70	73	80
E2	70	89	70	70
E3	85	70	80	76
E4	77	70	73	80

Answer 1

Step 3: Optimization -

Aim is to cross all the zeroes with the minimum number of lines. To do this,

Row Scanning -

Scan each row starting from the first row. If the row has exactly one zero, mark that zero and draw a vertical line passing from that zero. If the zero in another row is already cancelled, it will not be counted. If there are no zeroes or more than one zero in a row then leave the row as it is. If all the zeroes have been cancelled, then move to the last step. If not, go to column scanning .

Column Scanning - Scan each column starting from the first column. If the Column has exactly one zero, mark that zero and draw a horizontal line passing from that zero. If the zero in another column is already cancelled, it will not be counted. If there are no zeroes or more than one zero in a column then leave the column as it is.

Hence, this is the optimal solution.

The optimal solution is, (From the last matrix squared zeroes are the optimal solution)

E1 ---> J1 ...... 75

E2 ---> J4 ....... 70

E3 ---> J2 ...... 70

E4 ---> J3 ....... 73

Total optimal cost = $ 288