Assignment Problem

Assumptions and
Formulation of Assignment problems,
Hungarian method,
Maximization problems.
LEARNING OBJECTIVES
 Understand the features of assignment problems and transportation problems.
 Formulate an assignment problem as a square matrix.
 Apply the Hungarian method to solve an assignment problem.
 make appropriate changes in the Hungarian method to solve an unbalanced
assignment problem,
 Profit maximization assignment problem, etc.

INTRODUCTION

An assignment problem is a particular case of a transportation problem where the resources

(say facilities) are assignees and the destinations are activities (say jobs). Given n resources
(or facilities) and n activities (or jobs), with effectiveness (in terms of cost, profit, time, etc.)
of each resource for each activity. Then problem becomes to assign (or allocate) each
resource to only one activity (job) and vice-versa so that the given measure of effectiveness is
optimized. The problem of assignment arises because the resources that are available such as
men, machines, etc., have varying degree of efficiency for performing different activities.
Therefore, the cost, profit or time of performing different activities is also different. Thus, the
problem becomes:
How should the assignments be made in order to optimize the given objective.
Some of the problems where the assignment technique may be useful are assignment of (i)
workers to machines, (ii) salesmen to different sales areas, (iii) clerks to various checkout
counters, (iv) classes to rooms, (v) vehicles to routes, (vi) contracts to bidders, etc.
MATHEMATICAL MODEL OF ASSIGNMENT PROBLEM
The general data matrix for assignment problem is shown in Table . It may be noted that this
data matrix is the same as the transportation cost matrix except that the supply (or
availability) of each of the resources and the demand at each of the destinations is taken to be
one. It is due to this fact that assignments are made on a one-to-one basis.

Suppose, xij represents the assignment of resource (facility) i to activity (job) j such that

Then mathematical model of the assignment problem can be stated as:

subject to the constraints

and xij = 0 or 1, for all i and j
where cij represents the cost of assignment of resource i to activity j.
This mathematical model of assignment problem is a particular case of the transportation
problem for two reasons:
(i) the cost matrix is a square matrix, and
(ii) the optimal solution table (matrix) for the problem would have only one
assignment in a given row or a column.
SOLUTION METHODS OF ASSIGNMENT PROBLEM
An assignment problem can be solved by any of the following methods:
• Enumeration method • Simplex method
• Transportation method • Hungarian method
1. Enumeration Method In this method, a list of all possible assignments among the given
resources (men, machines, etc.) and activities (jobs, sales areas, etc.) is prepared. Then an
assignment that involves the minimum cost (or maximum profit), time or distance is selected.
If two or more assignments have the same minimum cost (or maximum profit), time or
distance, the problem has multiple optimal solutions.
In general, if an assignment problem involves n workers/jobs, then in total there are n!
possible assignments. For example, for an n = 5 workers/jobs problem, we have to evaluate a
total of 5! or 120 assignments. However, when n is large, the method is unsuitable for manual
calculations. Hence, this method is suitable only when the value of n is small.
2. Simplex Method Since each assignment problem can be formulated as a 0 or 1 integer
linear programming problem, such a problem can also be solved by the simplex method. The
general mathematical model of the assignment problem involves n × n decision variables and
n + n or 2n equalities. Thus, for any assignment problem that involves 5 workers/jobs, there
will be 25 decision variables and 10 equalities. Solving such an assignment problem
manually is difficult.
3. Transportation Method Since an assignment problem is a special case of the
transportation problem, it can also be solved by using MODI method. However, every basic
feasible solution of a general assignment problem that has a square matrix of order n should
have m + n – 1 = n + n – l = 2n – 1 assignments. But due to the special structure of this
problem, none of the solutions can have more than n assignments. Consequently, solutions
will be degenerate. To remove degeneracy, (n – 1) number of dummy allocations (deltas or
epsilons) will be required in order to proceed with MODI method. Thus, the problem of
degeneracy at each solution makes the procedure computationally inefficient for solving an
assignment problem.
4. Hungarian Method The Hungarian method (developed by Hungarian mathematician D.
Konig) is an efficient method of finding the optimal solution of an assignment problem
without making a direct comparison of every solution. The method works on the principle of
reducing the given cost matrix to a matrix of opportunity costs. Opportunity costs show the
relative penalties associated with assigning a resource to an activity. Hungarian method
reduces the cost matrix to the extent of having at least one zero in each row and column so as
to make optimal assignments.

Hungarian Method for Solving Assignment Problem

The Hungarian method (minimization case) can be summarized in the following steps:
Step 1: Develop the cost matrix from the given problem If the number of rows are not
equal to the number of columns, then add required number of dummy rows or columns. The
cost element in dummy rows/columns are always zero.
Step 2: Find the opportunity cost matrix
(a) Identify the smallest element in each row of cost matrix and then subtract it from each
element of that row, and
(b) In the reduced matrix obtained from 2(a), identify the smallest element in each column
and then subtract it from each element of that column. Each row and column now have at
least one zero element.
Step 3: Make assignments in the opportunity cost matrix The procedure of making
assignments is as follows:
(a) First round for making assignments
 Identify rows successively from top to bottom until a row with exactly one zero
element is found. Make an assignment to this single zero by making a square (􀂅)
around it. Then cross off (×) all other zeros in the corresponding column.
 Identify columns successively from left to right hand with exactly one zero element
that has not been assigned. Make assignment to this single zero by making a square
(􀂅) around it and then cross off (×) all other zero elements in the corresponding row.

(b) Second round for making assignments

 If a row and/or column has two or more unmarked zeros and one cannot be chosen by
inspection, then choose zero element arbitrarily for assignment.
 Repeat steps (a) and (b) successively until one of the following situations arise.
Step 4: Optimality criterion
(a) If all zero elements in the cost matrix are either marked with square (􀂅) or are crossed off
(×) and there is exactly one assignment in each row and column, then it is an optimal
solution. The total cost associated with this solution is obtained by adding the original cost
elements in the occupied cells.
(b) If a zero element in a row or column was chosen arbitrarily for assignment in Step 4(a),
there exists an alternative optimal solution.
(c) If there is no assignment in a row (or column), then this implies that the total number of
assignments are less than the number of rows/columns in the square matrix. In such a
situation proceed to Step 5.
Step 5: Revise the opportunity cost matrix Draw a set of horizontal and vertical lines to
cover all the zeros in the revised cost matrix obtained from Step 3, by using the following
procedure:
(a) For each row in which no assignment was made, mark a tick (􀀹)
(b) Examine the marked rows. If any zero element is present in these rows, mark a tick (􀀹) to
the respective columns containing zeros.
(c) Examine marked columns. If any assigned zero element is present in these columns, tick
(􀀹) the respective rows containing assigned zeros.
(d) Repeat this process until no more rows or columns can be marked.
(e) Draw a straight line through each marked column and each unmarked row.
If the number of lines drawn (or total assignments) is equal to the number of rows (or
columns), the current solution is the optimal solution, otherwise go to Step 6.
Step 6: Develop the new revised opportunity cost matrix
(a) Among the elements in the matrix not covered by any line, choose the smallest element.
Call this value k.
(b) Subtract k from every element in the matrix that is not covered by a line.
(c) Add k to every element in the matrix covered by the two lines, i.e. intersection of two
lines.
(d) Elements in the matrix covered by one line remain unchanged.
Step 7: Repeat steps Repeat Steps 3 to 6 until an optimal solution is obtained.
Flowchart of Hungerian method

Example 1 A computer centre has three expert programmers. The centre wants three
application programmes to be developed. The head of the computer centre, after carefully
studying the programmes to be developed, estimates the computer time in minutes required
by the experts for the application programmes as follows:

Assign the programmers to the programmes in such a way that the total computer time is
minimum.
Solution: Steps 1 & 2 The minimum time element in rows 1, 2 and 3 is 80, 80 and 110,
respectively. Subtract these elements from all elements in their respective row. The reduced
time matrix is shown in Table

In reduced above Table the minimum time element in columns A, B and C is 0, 10 and 0,
respectively. Subtract these elements from all elements in their respective column in order to
get the reduced time matrix. This is shown in Table .
Step 3 (a) Examine all the rows starting from the first, one-by-one, until a row containing
single zero element is found. In Table rows 1 and 3 have only one zero in the cells (1, C) and
(3, A), respectively. Make an assignment in these cells and cross off all zero elements in the
assigned column as shown in Table.

Now examine each column starting from A in Table . There is one zero in column B in the
cell (2, B). Make an assignment in this cell as shown in Table.

Since the number of assignments (= 3) equals the number of rows (= 3), the optimal solution
is obtained. The pattern of assignments among programmers and programmes with their
respective time (in minutes) is given below:

Example 2 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?
Solution
Cover the zeros with minimum number of lines (= 4) as explained below:
(a) Mark (􀀹) row D where there is no assignment.
(b) Mark (􀀹) columns I and IV since row D has zero element in these columns.
(c) Mark (􀀹) rows B and E since columns I and IV have an assignment in rows B and E,
respectively.
(d) Since no other rows or columns can be marked, draw straight lines through the unmarked
rows A and C and the marked columns I and IV, as shown in Table

Develop the revised matrix by selecting the smallest element among all uncovered elements
by the lines in Table ; viz., 2. Subtract k = 2 from uncovered elements including itself and add
it to elements 5, 10, 8 and 0 in cells (A, I), (A, IV), (C, I) and (C, IV), respectively, which lie
at the intersection of two lines. The revised matrix, so obtained is shown in Table.

Since the number of assignments (= 5) equals the number of rows (or columns), the solution
is optimal. The pattern of assignments among jobs and employees with their respective time
(in hours) is given below:
Maximization Case in Assignment Problem
If instead of cost matrix, a profit (or revenue) matrix is given, then assignments are mode in
such a way that total profit is maximized. The profit maximization assignment problems are
solved by converting them into a cost minimization problem in either of the following two
ways:
(i) Put a negative sign before each of the elements in the profit matrix in order to convert the
profit values into cost values.
(ii) Locate the largest element in the profit matrix and then subtract all the elements of the
matrix from the largest element including itself.
The transformed assignment problem can be solved by using usual Hungarian method.

Example A company operates in four territories, and four salesmen available for an
assignment. The territories are not equally rich in their sales potential. It is estimated that a
typical salesman operating in each territory would bring in the following annual sales:
Territory : I II III IV
Annual sales (Rs) : 1,26,000 1,05,000 84,000 63,000

The four salesmen also differ in their ability. It is estimated that, working under the same
conditions, their yearly sales would be proportionately as follows:
Salesmen : A B C D
Proportion : 7 5 5 4
If the criterion is maximum expected total sales, the intuitive answer is to assign the best
salesman to the richest territory, the next best salesman to the second richest, and so on;
verify this answer by the assignment technique.
Solution Construct the Effectiveness Matrix: To avoid the fractional values of annual sales of
each salesman in each territory, for convenience, consider their yearly sales as 21 (i.e. the
sum of sales proportions), taking Rs 1,000 as one unit. Now divide the individual sales in
each territory by 21 in order to obtain the required annual sales by each salesman. The
maximum sales matrix so obtained is given in Table

Converting Maximization Problem into Minimization Problem: The given maximization

assignment problem can be converted into a minimization assignment problem by subtracting
from the highest element (i.e. 42) all the elements of the given table. The new data so
obtained is given in Table .
The pattern of two alternative optimal assignments among territories and salesmen with their
respective sales volume (in Rs 1,000) is given in the table.

Example A marketing manager has five salesmen and five sales districts. Considering the
capabilities of the salesmen and the nature of districts, the marketing manager estimates that
the sales per month (in hundred rupees) for each salesman in each district would be as
follows:
Find the assignment of salesmen to districts that will result in maximum sales.
Solution The given maximization problem can be converted into a minimization problem by
subtracting
from the largest element (i.e. 41) all the elements of the given table. The new cost data so
obtained is given
in Table .

The solution shown in Table is not optimal since only four assignments are made. Cover the
zeros with the minimum number of lines (= 4) as shown in Table.
Develop the revised cost matrix by selecting the minimum element (= 4) among all
uncovered elements by the lines. Subtract 4 from all uncovered elements, including itself, and
add it to the element at the intersection of the lines. A revised cost table, so obtained, is
shown in Table. Repeat the above procedure again to make the assignments in the reduced
Table. The two alternative assignments are shown in Tables. Two more alternative solutions
exist due to presence of zero element in cells (4, C), (4, D) and cells (5, C), (5, D).

Two alternative optimal assignments are as follows:

Unbalanced Assignment Problem
The Hungarian method for solving an assignment problem requires that the number of
columns and rows in the assignment matrix should be equal. However, when the given cost
matrix is not a square matrix, the assignment problem is called an unbalanced problem. In
such cases before applying Hungarian method, dummy row(s) or column(s) are added in the
matrix (with zeros as the cost elements) in order to make it a square matrix.
Restrictions on Assignments
Sometimes it may so happen that a particular resource (say a man or machine) cannot be
assigned to a particular activity (say territory or job). In such cases, the cost of performing
that particular activity by a particular resource is considered to be very large (written as M or
∞∞) so as to prohibit the entry of this pair of resource-activity into the final solution.
Example In the modification of a plant layout of a factory four new machines M1, M2, M3,
and M4 are to be installed in a machine shop. There are five vacant places A, B, C, D and E
available. Because of limited space, machine M2 cannot be placed at C and M3 cannot be
placed at A. The cost of locating a machine at a place (in hundred rupees) is as follows.

Find the optimal assignment schedule.

Solution Since cost matrix is not balanced, add one dummy row (machine) with a zero cost
elements in that row. Also assign a high cost, denoted by M, to the pair (M2, C) and (M3, A).
The cost matrix so obtained is given in Table . Apply Hungarian method for solving this
problem

The total minimum cost (Rs) and optimal assignments made are as follows:

MCQ QUESTIONS
1) An assignment problem is considered as a particular case of a transportation problem
because
A. The number of rows equals columns
B. All xij= 0 or 1
C. All rim conditions are 1
D. All of the above
2) An optimal assignment requires that the maximum number of lines that can be drawn
through squares with zero opportunity cost be equal to the number of
A. Rows or columns B. Rows & columns C. Rows + columns –1 d.
D. None of the above
3) While solving an assignment problem, an activity is assigned to a resource through a
square with zero opportunity cost because the objective is to
A. Minimize total cost of assignment
B. Reduce the cost of assignment to zero
C. Reduce the cost of that particular assignment to zero
D. All of the above
4) The method used for solving an assignment problem is called
A. Reduced matrix method
B. MODI method
C. Hungarian method
D. None of the above
5) The purpose of a dummy row or column in an assignment problem is to
A. Obtain balance between total activities &total resources
B. Prevent a solution from becoming degenerate
C. Provide a means of representing a dummy problem
D. None of the above
6) Maximization assignment problem is transformed into a minimization problem by
A. Adding each entry in a column from the maximization value in that column
B. Subtracting each entry in a column from the maximum value in that column
C. Subtracting each entry in the table from the maximum value in that table
D. Any one of the above
7) If there were n workers & n jobs there would be
A. n! solutions B. (n-1)! solutions C. (n!)nsolutions D. n solutions
8) An assignment problem can be solved by
A. Simplex method
B. Transportation method
C. Both a & b
D. None of the above
9) The assignment problem
A. Requires that only one activity be assigned to each resource
B. Is a special case of transportation problem
C. Can be used to maximize resources
D. All of the above
10) An assignment problem is a special case of transportation problem, where
A. Number of rows equals number of columns
B. All rim conditions are 1
C. Values of each decision variable is either 0 or 1
D. All of the above
11) Every basic feasible solution of a general assignment problem, having a square pay-off
matrix of order, n should have assignments equal t
A. 2n+1 B. 2n-1 C. m+n-1 D. m+n
12) The Hungarian method for solving an assignment problem can also be used to solve A.
A transportation problem B. A travelling salesman problem C. A LP problem
D. Both a & b
13) An optimal solution of an assignment problem can be obtained only if
A. Each row & column has only one zero element
B. Each row & column has at least one zero element
C. The data is arrangement in a square matrix
D. None of the above
14) In assignment problem of maximization, the objective is to maximise
A. Profit B. optimization C. cost D. None of the above
15) In the Hungarian method of solving an assignment problem, the row reduction is obtained
by
(a) Dividing each row by the elements of the row above it
(b) Subtracting the elements of the row from the elements of the row above it
(c) Subtracting the smallest element from all other elements of the row
(d) Subtracting all the elements of the row from the highest element in the matrix

PRACTICE PROBLEMS
1) Five men are available to do five different jobs. From past records, the time (in hours)
that each man takes to do each job is known and is given in the following table:

Find out how men should be assigned the jobs in way that will minimize the total time
taken.
2) Five workers are available to work with the machines and the respective costs (in
rupees) associated with each worker machine assignment are given below. A sixth
machine is available to replace one of the existing ones and the associated of that
machine costs are also given below.

(a) Determine whether the new machine can be accepted.

(b) Also determine the optimal assignment and the associated saving in cost.
3) A company has four machines that are to be used for three jobs. Each job can be assigned
to one and only one machine. The cost of each job on each machine is given in the following
table.

What are the job-assignment pairs that shall minimize the cost?