I want to solve job assignment problem using Hungarian algorithm of Kuhn and Munkres in case when matrix is not square. Namely we have more jobs than workers. In this case adding additional row is recommended to make matrix square. For example in the following link.

enter image description here And here task IV is assumed to be done. But in real we do not have man D. Who will actually do task IV? Can someone explain this phenomena?

In general I want to complete all tasks by loading workers uniformly and get maximum cost. So how to implement this task by using job assignment algorithm above?


Purpose of introducing a dummy variable:

Your assignment problem is such that, the number of jobs is greater than number of persons available. In every assignment problem, it is assumed that each person will do one job, and a job will be done by only one person.

Hence assuming that you are a manager, and you have three workers working for you, and you have four jobs, you will accept only three jobs out of four. Now the question is which three you will accept and how would you assign them?

So you introduce a dummy person. Now do the assignments using standard Hungarian Algorithm. So three workers get three jobs such that net man-hours are minimum. And outsource the remaining job (in your case, job no. $IV$).

This solution helps choosing those three jobs, which can be done in the fastest way in your firm.

Answers to your questions

1) No. Nobody in your firm will do job $IV$. The Hungarian algorithm just helped you to identify which three jobs to accept and how to assign them.

2) What do you mean by 'get maximum cost'? This is a minimization problem and numbers in the table represent man-hours, not the cost. But assuming you want to maximize profit lets say, then you have to convert the maximization problem into minimization problem (as done here) and solve as usual.

Some more references as follows.

The logic behind the Hungarian algorithm is discussed in this video nicely. While the flowchart along with explanation for the algorithm is given in this link.

All the best.

  • $\begingroup$ @Nurlan Kenzhebekov, If this answer clarifies the doubt, you may want to accept it as the answer. $\endgroup$ – Subodh May 21 '13 at 6:01

Job Assignment Problem is a kind of Pure Binary Linear Problem. Therefore, you can solve this problem by using BLP.

  • 1
    $\begingroup$ This doesn't address the question of how to solve this "pure binary linear problem". $\endgroup$ – Christian Clason Jun 21 '13 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.