The basic objective of an assignment problem is to assign n number of resources to n number of
activities so as to minimize the total cost or to maximize the total profit of allocation in such a
way that the measure of effectiveness is optimized. The problem of assignment arises because
available resources such as men, machines, etc., have varying degree of efficiency for
performing different activities such as job. Therefore cost, profit or time for performing the
different activities is different. Hence the problem is, how should the assignments be made so as
to optimize (maximize or minimize) the given objective. The assignment model can be applied in
many decision-making processes like determining optimum processing time in machine
operators and jobs, effectiveness of teachers and subjects, designing of good plant layout, etc.
This technique is found suitable for routing travelling salesmen to minimize the total travelling
MATHEMATICAL STRUCTURE OF ASSIGNMENT PROBLEM
The structure of assignment problem of assigning operators to jobs is shown in Table
Let n be the number of jobs and number of operators.
tij be the processing time of job i taken by operator j.
A few applications of assignment problem are:
i. assignment of employees to machines.
ii. assignment of operators to jobs.
iii. effectiveness of teachers and subjects.
iv. allocation of machines for optimum utilization of space.
v. salesmen to different sales areas.
vi. clerks to various counters.
In all the cases, the objective is to minimize the total time and cost or otherwise maximize
the sales and returns.
TYPES OF ASSIGNMENT PROBLEM
The assignment problems are of two types (i) balanced and (ii) unbalanced. If the number of
rows is equal to the number of columns or if the given problem is a square matrix, the problem is
termed as a balanced assignment problem. If the given problem is not a square matrix, the
problem is termed as an unbalanced assignment problem. If the problem is an unbalanced one,
add dummy rows /dummy columns as required so that the matrix becomes a square matrix or a
balanced one. The cost or time values for the dummy cells are assumed as zero.
HUNGARIAN METHOD FOR SOLVING ASSIGNMENT PROBLEM
Step 1: In a given problem, if the number of rows is not equal to the number of columns and vice
versa, then add a dummy row or a dummy column. The assignment costs for dummy cells are
always assigned as zero.
Step 2: Reduce the matrix by selecting the smallest element in each row and subtract with other
elements in that row.
Step 3: Reduce the new matrix column-wise using the same method as given in step 2.
Step 4: Draw minimum number of lines to cover all zeros.
Step 5: If Number of lines drawn = order of matrix, then optimally is reached, so proceed to step
7. If optimally is not reached, then go to step 6.
Step 6: Select the smallest element of the whole matrix, which is NOT COVERED by lines.
Subtract this smallest element with all other remaining elements that are NOT COVERED by
lines and add the element at the intersection of lines. Leave the elements covered by single line
as it is. Now go to step 4.
Step 7: Take any row or column which has a single zero and assign by squaring it. Strike off the
remaining zeros, if any, in that row and column (X). Repeat the process until all the assignments
have been made.
Step 8: Write down the assignment results and find the minimum cost/time.
Note: While assigning, if there is no single zero exists in the row or column, choose any
one zero and assign it. Strike off the remaining zeros in that column or row, and repeat
the same for other assignments also. If there is no single zero allocation, it means multiple
number of solutions exist. But the cost will remain the same for different sets of allocations.
UNBALANCED ASSIGNMENT PROBLEM
If the given matrix is not a square matrix, the assignment problem is called an unbalanced
problem. In such type of problems, add dummy row(s) or column(s) with the cost
elements as zero to convert the matrix as a square matrix. Then the assignment problem
is solved by the Hungarian method.
RESTRICTED ASSIGNMENT PROBLEM
In real practice, situations may arise where a particular machine cannot be assigned to an
operator because he may not be skilled enough to operate it. Because of this, no assignment is
made for the operator on that machine. This situation is overcome by assigning a large value, or
by assigning M. This will result in no assignment made to the restricted combinations.
Example 5: Five jobs are to be assigned to five men. The cost (in Rs.) of performing
the jobs by each man is given in the matrix (Table 7.29). The assignment has restrictions
that Job 4 cannot be performed by Man 1 and Job 3 cannot be performed by Man 4 Find
the optimal assignment of job and its cost involved.
Men 1 2 3 4 5
1 16 12 11 X 15
2 13 15 11 16 18
3 20 21 18 19 17
4 16 13 X 16 12
5 20 19 18 17 19