I have this assignement problem:

There are three machines to perform four tasks. The costs of assigning to a machine each of the tasks are given by the following matrix:

$$\begin{pmatrix} 2 & 6 & 4 & 4\\ 3&4&4&3\\ 2&5&6&5 \end{pmatrix}$$ $a)$ Determine an optimal assignement assuming that each machine must perform exactly one task and therefore, one of the tasks will not be performed.

$b)$ determine an optimal assigement assuming that each machine can perform at the most two tasks and that every task must be performed.

So far, the assignement problems I've been asked to solve have a square matrix as the cost matrix, and each agent was required to perform exactly one task in a way that all tasks were performed and I would use the Hungarian algorithm to solve them. However, the algorithm works only for $n \times n$ matrix and I don't know how to proceed. So my question is:

How do I transform this problem so I can use the Hungarian Algorithm to solve it?

Thanks in advance.

  • 1
    $\begingroup$ Add a row with costs of 0. Any assignment to this row will be a task that is not done. Do something similar with columns in problem 2 - remember you will still need a square matrix though. $\endgroup$ – Paul May 15 '16 at 18:26
  • $\begingroup$ @Paul Thank you! So when the algorithm stops (the number of lines covering the zeros is equal to the number of rows), in the first problem I need to consider the row with costs of $0$ to construct the matching. But in the second problem I don't how adding a column with costs of 0 solves it. Since I can make a machine perform two tasks, wouldn't the same argument (adding a $0$ row) work too? I just need to mark two zeros on a single row so that each $0$ is in a different column, right? $\endgroup$ – user313212 May 16 '16 at 18:06
  • $\begingroup$ Similar, but not the same problem. Your second problem will have 6 rows and columns. Ask yourself where the 6 rows are coming from and then add appropriate columns to make it square. $\endgroup$ – Paul May 16 '16 at 21:25
  • $\begingroup$ @Paul If I add only one row, I get a $4 \times 4$ matrix, and then each machine performs exactly one task. But I need a machine to perform two tasks so that the other two machines perform exactly one. So I add a new row and a new column to get a $5 \times 5$ matrix. But I can't see why I must add a new row... $\endgroup$ – user313212 May 17 '16 at 16:01
  • $\begingroup$ @Paul Is it somehow related to the fact that I can assign two tasks to one machine in three different ways? $\endgroup$ – user313212 May 17 '16 at 16:06

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.