0
$\begingroup$

Can someone suggest an algorithm to solve job assignment problem with condition?

With condition means that some jobs cannot be done by some workers. For example table as shown below:

enter image description here

In this table x - means that it is impossible to do. For example, worker 1 cannot do jobs 1,3 and 5.

I encountered such situation and there may be cases as shown above when usual Hungarian algorithm seems cannot solve such task because there is no way to complete all tasks by distributing one task per worker.

However, my main case it is allowed that one worker wil do several tasks (tasks, which worker can do). Main task is to complete all jobs using existing workers, but it is desirable that, all workers do roughly same number of tasks.

So is there some solution of such problem? May be any algorithms do exist?

$\endgroup$
  • $\begingroup$ isn't this constraint optimization problem which can be solved by Genetic Algorithms/local search or even complete methods? $\endgroup$ – seteropere May 18 '13 at 21:50
  • 1
    $\begingroup$ I don't quite understand your "real world" problem. Can you put it in mathematical terms? $\endgroup$ – Raphael May 19 '13 at 15:01
2
$\begingroup$

Instead of putting x, put some very high cost values in those cells. Then the Hungarian algorithm avoids selecting those cells automatically (if that's possible).

$\endgroup$

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.