Hungarian Method for Restriction on Assignment Problem-Example

Hungarian Method for Restriction on Assignment Problem Example

In this article we will study the step by step procedure of Hungarian method to solve assignment problem with some kind of restriction.

Assignment Problem with Restrictions Example

Five employees are available to perform four jobs. The time it takes each person to perform each job is given as follows:

Person \ Job	Job 1	Job 2	Job 3	Job 4
Person 1	22	18	30	18
Person 2	18	-	27	22
Person 3	26	20	28	28
Person 4	16	22	-	14
Person 5	21	-	25	28

Determine the assignment of employees to jobs that minimizes the total time required to perform the four jobs.

Solution

In the given problem there are 5 persons and 4 Jobs. The problem can be formulated as $5\times 4$ assignment problem with $c_{ij}$ = time it to takes $i^{th}$ person for $j^{th}$ job.

Let

$$ \begin{equation*} x_{ij}=\left\{ \begin{array}{ll} 1, & \hbox{if $i^{th}$ Person is assigned to $j^{th}$ Job;} \\ 0, & \hbox{otherwise.} \end{array} \right. \end{equation*} $$

The time it takes each person to perform each job is given as follows:

Person \ Job	Job 1	Job 2	Job 3	Job 4
Person 1	22	18	30	18
Person 2	18	-	27	22
Person 3	26	20	28	28
Person 4	16	22	-	14
Person 5	21	-	25	28

As the table is not a square matrix, add a dummy column with time equals 0.

Also in the given assignment problem person 2 cannot perform job 2, person 4 cannot perform job 3 and person 5 cannot perform job 2. To avoid this we assign a very high cost (say, infinity i.e. $\infty$) to the corresponding cells.

Step 1

The minimum in each row is 0. Subtract the minimum of each row of the above cost matrix, from all the elements of respective rows. The modified matrix is as follows:

Step 2

The smalles cost in first column is 16, in the second column is 18, in the third column is 25, in the fourth column is 14 and in the fifth column is 0.

Subtract the minimum of each column of the modified matrix, from all the elements of respective columns. The modified matrix is as follows:

Step 3

Draw the minimum number of horizontal and vertical line to cover all the zeros in the modified matrix.

The minimum number of lines = 4, which is less than the order of assignment problem (i.e. 5). Hence the optimal assignment is not possible.

Step 4

The smallest element in the matrix, not covered by the lines is 2. Subtract 2 from all the uncovered elements and add 2 at the intersection of horizontal and vertical lines. And obtain the second modified matrix.

Draw the minimum number of horizontal and vertical line to cover all the zeros in the above modified matrix.

Step 5

The minimum number of lines = 5, which is equal to the order of assignment problem (i.e. 5). Hence the optimal assignment using Hungarian method is possible.

Step 6

Examine the row successively until a row-wise exactly single zero is found, mark this zero by $\square$ to make the assignment and mark cross $(\times)$ over all zeros in that column. Continue in this manner until all the rows have been examined. Repeat the same procedure for columns also.

Step 7

Repeating Step 6 successively we have

Step 8

From the above table it is clear that in each row and in each column exactly one marked $\square$ zero is obtained. The optimal assignment is

Person 1 $\to$ Job 2

Person 2 $\to$ Job 1

Person 3 $\to$ Job 5

Person 4 $\to$ Job 4

Person 5 $\to$ Job 3

The expected time for five persons to complete five jobs is as follows:

Persons	Jobs	Time
Person 1	Job 2	18
Person 2	Job 1	18
Person 3	Job 5	0
Person 4	Job 4	14
Person 5	Job 3	25

Thus the total minimum time required to perform all the four jobs by five persons = 18 + 18 + 0 + 14 + 25= 75.

Endnote

In this tutorial, you learned about step by step procedure of Hungarian Algorithm to solve assignment problem with restrictions.

To learn more about Assignment problems please refer to the following tutorials:

Assignment Problems

Read step by step solution

Let me know in the comments if you have any questions on Hungarian Algorithm to solve Assignment problems and your thought on this article.