04-02-2025
Assignment Problem
Sessions 13
Assignment problem
In every workplace, there are jobs to be done and there are people
available to do them. But everyone is not equally efficient at every job.
Someone may be more efficient on one and less efficient on the other job.
The relative efficiency is reflected in terms of the time taken for, or the cost
associated with, performance of different jobs by different people.
An obvious problem for a manager to handle is to assign jobs to various
workers in a manner that they can be done in the most efficient way.
Interestingly, such problems can be formulated as linear programming
problems or as transportation problems and solved as such, but a method,
called Hungarian Assignment Method provides an easy route.
1
04-02-2025
Typical example of an assignment
problem
A production supervisor is considering how he should assign the four
jobs that are to be performed by four of the workers. He wants to
assign the jobs to the workers such that the aggregate time to
perform the jobs is least. Based on previous experience, he has the
information on the time taken by the four workers in performing
these jobs, as given in the Table below:
Job
Worker A B C D
1 45 40 51 67
2 57 42 63 55
3 49 52 48 64
4 41 45 60 55
Solving an assignment problem using the
Hungarian Assignment Method (HAM)
This method is based on the concept of opportunity cost
It uses a fact that if we add or subtract any constant from every element of
a cost table, the given problem does not change and remains essentially
the same
The method entails converting the original cost table into a series of
equivalent cost tables, called Reduced Cost Tables or Opportunity Cost
Tables, consisting of only zeros and positive values. This is done until an
optimal solution is obtained.
The optimal solution that is derived only with the help of zeros from a
reduced cost table is also the optimal solution to the original problem.
2
04-02-2025
Hungarian Assignment Method
Step 1: Locate the smallest cost element in each row of the cost table. Now
subtract this smallest element from each element in that row. As a result, there
shall be at least one zero in each row of this table called the Reduced Cost
Table.
Step 2: In the reduced cost table obtained, consider each column and locate
the smallest element in it. Subtract the smallest value from every other entry in
the column. As a consequence of this action, there would be at least one zero
in each of the rows and columns of the second reduced cost table.
Step 3: Draw the minimum number of horizontal and vertical lines (not diagonal
ones) that are required to cover all the ‘zero’ elements. If the number of lines
drawn is equal to n (the number of rows/ columns) the solution is optimal, and
proceed to step 6. If the number of lines drawn is less than n, go to step 4.
Hungarian Assignment Method
Step 4: If the number of lines covering all zeros is smaller than n, it has to
implication that the number of zeros and their locations do not permit us to
obtain the optimal solution. Thus, there is need to create more zeros. For
this, select the smallest uncovered (by lines) cost element. Subtract this
element from all uncovered elements including itself and add this element
to each value located at the interaction of any two lines. The cost
elements through which only one line passes remain unaltered.
Step 5: Repeat steps 3 and 4 until an optimal solution is obtained.
3
04-02-2025
Hungarian Assignment Method
Step 6: Given the optimal solution, make the job assignments as indicated by
the ‘zero’ elements. This is done as follows:
a. Locate a row which contains only one ‘zero’ element. Assign the job corresponding
to this element to its corresponding person. Cross out the zeros, if any, in the column
corresponding to the element, which is indicative of the fact that the particular job
and person are no more available.
b. Repeat (a) for each of such rows which contain only one zero. Similarly, perform the
same operation in respect of each column containing only one ‘zero’ element,
crossing out the zero(s), if any, in the row in which the element lies.
c. If there is no row or column with only a single ‘zero’ element left, then select a row/
column arbitrarily and choose one of the jobs (or persons) and make the assignment.
Now cross the remaining zeros in the column and row in respect of which the
assignment is made.
d. Repeat steps (a) through (c) until all assignments are made.
e. Determine the total cost with reference to the original cost table.
Example 1
Solve the following assignment problem using the Hungarian Assignment
Method. The figures in the table indicate the time taken by each operator
to perform each of the jobs
Job
Worker A B C D
1 45 40 51 67
2 57 42 63 55
3 49 52 48 64
4 41 45 60 55
4
04-02-2025
Solution to Example 1
Step 1: The minimum value of each row is subtracted from all elements in
the row. It is shown in the reduced cost table, also called Opportunity Cost
Table
Job
Worker A B C D
1 5 0 11 27
2 15 0 21 13
3 1 4 0 16
4 0 4 19 14
Solution to Example 1
Step 2: For each column of this table, the minimum value is subtracted from
all the other values. Obviously, the columns that contain a zero would
remain unaffected by this operation. Here only the fourth column values
would change.
Job
Worker A B C D
1 5 0 11 14
2 15 0 21 0
3 1 4 0 3
4 0 4 19 1
5
04-02-2025
Solution to Example 1
Step 3: Draw the minimum number of lines covering all zeros. As a general
rule, we should first cover those rows/ columns which contain a larger
number of zeros.
Job
Worker A B C D
1 5 0 11 14
2 15 0 21 0
3 1 4 0 3
4 0 4 19 1
Solution to Example 1
Step 4: Since the number of lines drawn is equal to 4(=n), the optimal
solution is obtained. The assignments are made after scanning the rows
and columns for unit zeros.
Job
Worker A B C D
1 5 0 11 14
2 15 0 21 0
3 1 4 0 3
4 0 4 19 1
The final pattern of assignments is 1-B, 2-D, 3-C, and 4-A, involving a total
time of 40 + 55 + 48 + 41 = 184 minutes
6
04-02-2025
Exercise 1
Using the following cost matrix, determine (a) the optimal job assignments
and (b) the cost of assignments
Job
Machinist 1 2 3 4 5
A 10 3 3 2 8
B 9 7 8 2 7
C 7 5 6 2 4
D 3 5 8 2 4
E 9 10 9 6 10
Exercise 2
A computer centre has three expert programmers. The centre wants three
application programs to be developed. The head of the computer centre,
after carefully studying the programs to be developed, estimates the
computer time in minutes required by the experts for the application
programs as follows:
Assign the programmers to the programs in such a way that the total
computer time is minimum.
7
04-02-2025
Exercise 3
A department of a company has five employees with five jobs to be
performed. The time (in hours) that each man takes to perform each job is
given in the effectiveness matrix.
How should the jobs be allocated, one per employee, so as to minimize the
total man-hours?
