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?

  • 1
    $\begingroup$ How do you define "loading workers uniformly"? $\endgroup$ – Aryabhata May 3 '13 at 14:26
  • $\begingroup$ "loading workers uniformly" means distribute tasks among workers uniform, i.e. every worker will do same amount of tasks. $\endgroup$ – Nurlan May 4 '13 at 11:47
  • $\begingroup$ Not sure if this works, but: What about a more graphically approach? Sketch the problem as a weighted matching problem on a bipartite graph. Then use the Hungarian Method / Dijkstra on this graph to compute a matching. $\endgroup$ – Laura Sep 10 '13 at 20:14

Your Answer

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

Browse other questions tagged or ask your own question.