UNIT 15: Network Optimisation Assignment Problem

UNIT

15 Network Optimisation Assignment

Problem

Names of Sub-Units

Assignment Problem, Mathematical Formulation, Solution of the Assignment Problem, Computational

Procedure of the Assignment Problem, Modi�ied the Assignment Problem

Overview

In this unit, you will learn the concept of assignment problem and its mathematical formulation. This
unit covers the method for solving the assignment problem as well as its computational procedure.
At the end of this unit, you will be introduced to the method for solving the assignment problem after
modifying it.

Learning Objectives

In this unit, you will learn to:

 Explain the meaning of assignment problem
 Analyse the method on assignment problem
 Describe the computational procedure for solving assignment problem
 Elucidate Hungarian method for assignment problems
 Analyse unbalanced assignment problem
 Mathematical Foundation for Computer Application

Learning Outcomes

At the end of this unit, you would:

 Evaluate the minimum cost value on assignment type problem
 Analyse the basic feasible solution using the different techniques
 Assess the problem based on Hungarian method
 Clarify the unbalanced assignment type problem
 Evaluate maximisation in assignment type problem
 Calculate the optimality for assignment type problem

Pre-Unit Preparatory Material

 https://www.lkouniv.ac.in/site/writereaddata/siteContent/202005032114048108Rajendra%20
Bahadur-ASSIGNMENT-PROBLEM.pdf
 https://kanchiuniv.ac.in/coursematerials/OperationResearch.pdf

15.1 INTRODUCTION
Previously, we have discussed the transportation problem and different methods for solving it.
Transportation problem is a special case of a linear programming problem, while transportation
problem has its special case, which is an assignment problem.
The main objective of the assignment problem is several of resources to a same number of activities so
that total cost can be minimised or total pro�it of each allocation can be maximised.
The reason for arising the problem of assignment problem is that peoples or staffs have varying degrees
of ef�iciency or capacity for performing different activities, thus, cost, loss or pro�it of performing
various activities in assignment problem varies.

15.2 ASSIGNMENT PROBLEM

Suppose there are ‘n’ jobs to be performed and ‘n’ persons are available for doing these jobs. Assume
that each person can do each job at a time, with varying degrees of ef�iciency, let cij be the cost of the ith
person is assigned to the jth job.
The problem is to �ind an assignment (which job should be assigned to which person, on a one to-
one basis) so that the total cost of performing all jobs is minimum, such kind of problem is known as
assignment problem.
Assignment problem is of two types:
 Balanced Assignment Problem
 Unbalanced Assignment Problem

2
UNIT 15: Network Optimisation Assignment Problem

The assignment problem can be expressed in the form of n x n cost matrix [cij] of real members as given
in the below table. The matrix [cij] is said to be the cost of effectiveness matrix.
Jobs

1 2 n
P1 
c11 c 12 c1 n
Persons P2 c c c
 21 22 2n 
 
Pn c c c
 n1
 n2 nn nn

15.3 MATHEMATICAL FORMULATION

Mathematically, the assignment problem can be expressed as:
n n
Z cijxij
i1 j1

Subject to restrictions of the form:

x1 j x2 j x3 j  xnj 1 for j = 1, 2, 3, …, n

xi1 xi2 xi3  xin 1 for i = 1, 2, 3, …, n

This restriction implies that a person is assigned only one job and only one job can be done by a person.

1; when i th person is assigned to jth job
Where xij 
0; when i person is not assigned to j job
th th


15.4 SOLUTION OF THE ASSIGNMENT PROBLEM

However, assignment problems are special cases of transportation problems, we do not use the method
for solving transportation problems. There is a method to solve the assignment problem, which is
called Hungarian Method. This method is easy as compared to other methods and takes less time.
The Hungarian method of assignment problem provides us an ef�icient method of �inding the optimal
solution without having to make a-direct comparison of every solution for minimum cost. It works on
the principle of reducing the given cost matrix to a matrix of opportunity costs.

15.5 COMPUTATIONAL PROCEDURE OF THE ASSIGNMENT PROBLEM

The Hungarian method can be summarised in the following steps:
Step 1: Develop the Cost Table from the given Problem:
If the no of rows is not equal to the no of columns and vice versa, a dummy row or dummy column must
be added. The assignment cost for dummy cells is always zero.

3
 Mathematical Foundation for Computer Application

Step 2: Find the Opportunity Cost Table:

a. Locate the smallest element in each row of the given cost table and then subtract that from each
element of that row.
b. In the reduced matrix obtained from 2 (a), locate the smallest element in each column and then
subtract that from each element. Each row and column now have at least one zero value.
Step 3: Make Assignment in the Opportunity Cost Matrix:
The procedure of making assignments is as follows:
a. Examine rows successively until a row with exactly one unmarked zero is obtained. Make an
assignment single zero by making a square around it.
b. For each zero value that becomes assigned, eliminate (Strike off) all other zeros in the same row
and/ or column.
c. Repeat steps 3 a. and 3 b. for each column also with exactly single zero value all that has not been
assigned.
d. If a row and/or column have two or more unmarked zeros and one cannot be chosen by inspection,
then choose the assigned zero cell arbitrarily.
e. Continue this process until all zeros in row-column are either enclosed (Assigned) or struck off (x)
Step 4: Optimality Criterion:
If the member of assigned cells is equal to the number of rows column, then it is the optimal solution.
The total cost associated with this solution is obtained by adding original cost �igures in the occupied
cells.
If a zero cell was chosen arbitrarily in step (3), there exists an alternative optimal solution. But if no
optimal solution is found, then go to step (5).
Step 5: Revise the Opportunity Cost Table:

Draw a set of horizontal and vertical lines to cover all the zeros in the revised cost table 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 occurs in those columns, tick the respective rows that contain
those assigned zeros.
c. Repeat this process until no more rows or columns can be marked.
d. Draw a straight line through each marked column and each unmarked row.
If a no of lines drawn is equal to the no of (or columns) the current solution is the optimal solution,
otherwise go to step 6.
Step 6: Develop the New Revised Opportunity Cost Table:
a. From among the cells not covered by any line, choose the smallest element, call this value K
b. Subtract K from every element in the cell not covered by line.
c. Add K to every element in the cell covered by the two lines, i.e., intersection of two lines.
d. Elements in cells covered by one line remain unchanged.

4
UNIT 15: Network Optimisation Assignment Problem

Step 7: Repeat Step 3 to 6 Unlit an Optimal Solution is Obtained:

Example 1. A company has 5 jobs to be done on �ive machines. Any job can be done on any machine. The
cost of doing the jobs on different machines is given below. Assign the jobs for different machines so as
to minimise the total cost.

Machines
Jobs
A B C D E
1 13 8 16 18 19
2 9 15 24 09 12
3 12 9 04 04 4
4 6 12 10 08 13
5 15 17 18 12 20

Solution: We form the �irst modi�ied matrix by subtracting the minimum element from all elements in
the respective row, and the same with respective columns.
Step 1: Subtract the smallest element of each row from all elements of the same row. And, then subtract
the smallest element of each column with all elements of the same column.

A B C D E
1 5 0 8 10 11
 
2 0 6 15 0 3 
3 8 5 0 0 0
 
 40 6 4  2 7
5 3 5 6 0 8 

Since each column has the minimum element 0, we will get the �irst modi�ied matrix again. Now we
draw the minimum number of lines to cover all zeros.
Step 2: Check each row one by one and then column. If we will get an unmarked single zero on a row or
column, we will put it into a square box and will cross the other zeros on the same row or column. We
will get the table:

A B C D E
5 
1 0 8 10 11

2  0 6 15 0 3 
 
38 5 0 0 0
40 6 4 
2 7
 
5 0 8
3 5 6

Since there are 5 jobs and only 4 are assigned to the machine, that is, the number of allocations is not
equal to number of rows and number of columns, thus, this allocation will not give an optimal solution
as there should be 5 allocations.

5
 Mathematical Foundation for Computer Application

Step 3: To get the optimal solution, we will �ind the revised cost matrix. For that follow these steps.
Tick marks the row which has no assignment, i.e., 2 nd row, then tick mark the column having zeros
corresponding to ticked row, i.e., 1st and 4th column. Then, tick mark the rows having the assignment
corresponding to the marked column, i.e., 4th and 5th row. Tick marks the column having zeros
corresponding to newly marked rows 4th and 5th, which are 1st and 4th column again which are already
marked. Now, draw the horizontal line in unmarked rows and vertical lines on marked columns. After
this process, our cost matrix will be as follows:

A B C DE
 0 8 10 11
1 5
2  0 6 15 0 3
 
3 8 5 0 0 0
40 6 4 2 7


5
3 5 6 0 8 

Note: There is a trick to draw these lines without marking ticks. Draw the minimum number of
horizontal and vertical lines such that it can cover all the zeros in the cost matrix.
Step 4: Check the smallest number in the cost matrix not covered by horizontal or vertical lines, that is
3. Add 3 to the numbers where lines are intersecting with each other and subtract it from the uncovered
numbers in the cost matrix. Thus, our revised cost matrix will be:

A B C D E
1 8 0 8 13 11
 
2 0 3 12 0 0 
3 11 5 0 3 0
 
 4 0 3 1 2 4
5 3 2 3 0 
5

Step 5: Repeat the process same as in step 2, then we will get the following cost matrix.

A B C D E


18 0 8 13 11

20 3 12 0 0 
 
3 11 5 0 3 0
40 
3 1 2 4
5 
3 2 3 0 5

6
UNIT 15: Network Optimisation Assignment Problem

Since the number of assignments, that is 5, equal to the number of rows and the number of columns, this
assignment gives the optimal solution. Thus, assignments will be:

Jobs Machine
1  B
2  E
3  C
4  A
5  D

Minimum (total cost) = 8 + 12 + 4 + 6 + 12 = Rs. 42

15.6 MODIFIED THE ASSIGNMENT PROBLEM

Sometimes, the number of resources may not be equal to number of jobs in the transportation problem.
In this situation, we will modify the transportation problem and then solve it.
An assignment problem is said to be an Unbalanced Assignment problem if the number of rows is not
equal to the number of columns or the cost matrix is not equal to a square matrix, i.e., the number of
rows and columns are not equal. To make an unbalanced assignment problem a balanced one, a dummy
facility(s) or a dummy job(s) (as the case may be) is introduced with zero cost or time. That is, to make
an assignment problem balanced, add dummy rows or columns and assign the cost 0 on dummy row
or column.
Example 2: A company has 4 jobs to be done on �ive machines. Only one job can be done on one machine.
The cost of doing the jobs on different machines is given below. Assign the jobs for different machines
to minimise the total cost.

Machines
Jobs
A B C D E
1 4 3 6 2 7
2 10 12 11 14 16
3 4 3 2 1 5
4 8 7 6 9 6

Solution: Since the cost of the matrix is not a square matrix, the given problem is unbalanced. We will
add a dummy job 5 with each entry zero. Thus, our modi�ied matrix will be;

A B C D E
1 4 3 6 2 7
2 10 12 11 14 16
3 4 3 2 1 5
4 8 7 6 9 6
5 0 0 0 0 0

7
 Mathematical Foundation for Computer Application

Step 1: We subtract the smallest element from all the elements in the respective rows. Since all the
columns have zeros, there will be no change in the cost matrix after subtracting the smallest number of
each column, which is zero, from all the numbers of the same column.

A B C D E
1 2 1 4 0 5
 
2 0 2 1 4 6
3 3 2 1 0 4
 
4 2 1 0 3 0
5 0 0 0 0 0

Step 2: Check each row one by one and then column. If we will get an unmarked single zero on a row or
column, we will put it into a square box and will cross the other zeros on the same row or column. We
will get the table:

A B C D E
1 2 1 4 0 5 
 
0 2 1 4 6
2 
3 3 2 1 0 4
 
42 1 
0 3 0

5 0 0 0 
0 0
Since the third row does not have any assignments, it will not produce an optimal solution.
Step 3: For getting an optimal solution, we will �ind a revised cost matrix. Draw a minimum number of
horizontal and vertical lines to cover all marked and unmarked zeros in the cost matrix.

A B C D E

1 2 1 4 0 5

20 2 1 4 6
 
33 2 1 0 4
42 1 0 3 0


5
0 0 0 0 0 

Step 4: Check the smallest number in the cost matrix not covered by horizontal or vertical lines, that is
1. Add 1 to the numbers where lines are intersecting with each other and subtract it from the uncovered
numbers in the cost matrix. Thus, our revised cost matrix will be:

A B C D E
1 2 0 3 0 4

2  0 1 0 4 5


3 3 1 0 0 3
 
 1 0 4 043
5 1 0 0 1 0

8
UNIT 15: Network Optimisation Assignment Problem

Step 5: Repeat the process same as we did in step 2 and make the assignments on the above revised cost
matrix.

A B C D E
 3 4
12 0 0

20 1 0 4 5
 
33 1 0 0 3
43 1 0 4 0


5
1 0 0 1 0 

Step 6: Since the number of lines that covers all zeros in the cost matrix is equal to 5, this assignment
will give the optimal solution.
Thus, optimum assignment is: 1B; 2A; 3C; 4 E
Therefore, minimum cost = 3 + 10 + 1 + 6 = Rs. 20
Maximal Assignment Problem:
Earlier, we have solved the problem of minimising the cost in an assignment problem. Now, we will learn
how to deal with the problems when it asks for maximising the pro�it in an assignment problem.
To solve the Maximal Assignment problem, we will convert the maximisation problem into a minimisation
problem by subtracting the highest number from all the other numbers in the cost matrix. Now, one can
solve this problem by following the steps in the Hungarian method.
The optimal solution obtained after the whole procedure will give you the optimal solution that maximise
the pro�it.

Conclusion 15.7 CONCLUSION

 The transportation problem is a special case of a linear programming problem, while the
transportation problem has its special case, which is the assignment problem.
 The problem is to �ind an assignment (which job should be assigned to which person, on a one-to-one
basis) so that the total cost of performing all jobs is minimum, such kind of problem is known as an
assignment problem.
 To solve the Maximal Assignment problem, we will convert the maximisation problem into
minimisation problem by subtracting the highest number from all the other numbers in the cost
matrix.
 Assignment problem is a special case of transportation problem.
 An assignment problem is said to be an Unbalanced Assignment problem if the number of rows
is not equal to the number of columns or the cost matrix is not equal to a square matrix, i.e., the
number of rows and columns are not equal.
 To make an unbalanced assignment problem, a balanced one, a dummy facility(s) or a dummy job(s)
(as the case may be) is introduced with zero cost or time.
 The method which is used to solve the assignment problem is called Hungarian Method.

9
 Mathematical Foundation for Computer Application

15.8 GLOSSARY

 Assignment Problem: The assignment problem is seen to be a special case of a transportation

problem when each origin is associated with one and only one destination, i.e., used for allocating
resources (mostly workforce) in an optimal way
 Unbalanced Assignment Problem: Unbalanced assignment problem is an assignment problem
where the number of rows is not equal to the number of columns in the cost matrix
 The Maximal Assignment Problem: Sometimes, the assignment problem deals with the maximisation
of an objectives function rather than minimizing it

15.9 SELF-ASSESSMENT QUESTIONS

A. Essay Type Questions

1. In a machine shop, a supervisor wishes to assign �ive jobs among six machines. Any one of them can
be processed completely by any one of the machines as follows:
Machine
A B C D E F
13 13 16 23 19 9

JOBS 11 19 26 16 17 18
12 11 4 9 6 10
7 15 9 14 14 13
9 13 12 8 14 11

The assignment of jobs to machines be on a one-to-one basis. Assign the jobs to machines so that the
total cost is minimum. Find the minimum total cost.
2. A department head has six jobs and �ive subordinates. The department head estimate the time each
man would take to perform each task as given in the effectiveness matrix below.
Task
Man A B C D E F
1 20 15 26 40 32 12
2 15 32 46 26 28 20
3 11 15 2 12 6 14
4 8 24 12 22 22 20
5 12 20 18 10 22 15

The assignment of jobs to machines be on a one-to-one basis. Assign the jobs to machines so that the
total cost is minimum. Find the minimum total cost.
3. A truck company on a particular day has 5 trucks for sending material to 6 terminals. The cost of
sending material from some destination to different trucks will be different as given by the cost
matrix below. Find the assignment of 4 trucks to four terminals out of six at the minimum cost.

10
 Task
Terminals A B C D E
1 3 6 2 6 5
2 7 1 4 4 7
3 3 8 5 8 3
4 6 4 3 7 4
5 5 2 4 3 2

6 5 7 6 2 5

4. A company has 4 machines to do 3 jobs. Each job can be assigned to only one Machine. The cost of
each job on each machine is given below. Determine the job Assignments that will minimise the total
cost.

Machine
W X Y Z
A 18 24 28 32
Jobs B 8 13 17 18
C 10 15 19 22

5. A company has 4 machines on which to do 3 jobs. Each job can be assigned to one and one only one
machine. The cost of each job on each machine is given in the following table:
Machine
Jobs
W X Y Z
A 18 24 28 32
B 8 13 17 19
C 10 15 19 22
What are the job assignments which will minimise the cost?

15.10 ANSWERS AND HINTS FOR SELF-ASSESSMENT QUESTIONS

A. Hints for Essay Type Questions

1. 1 F, 2A, 3  E, 4 C, 5  D, Minimum optimal cost = ` 43
2. 1 F; 2 A; 3 E; 4 C; 5 D; OR 1 B; 2 F; 3 C; 4 A; 5 D; Minimum optimal Cost = ` 55

11
3. 1  C; 2  B, 3  A, 6  D; Minimum optimal Cost = ` 8
4. A  W, D  Z, B  X, C  Y or A W, D  Z, B  Y, C  X
Minimum optimum cost =18 + 13 + 19 = ` 50
5. AW, BY, C  X; Minimum cost = ` 50

@ 15.11 POST-UNIT READING MATERIAL

 https://www.hindawi.com/journals/aor/2018/8958393/
 https://kanchiuniv.ac.in/coursematerials/OperationResearch.pdf
 https://cbom.atozmath.com/example/CBOM/Assignment.
aspx?he=e&q=HM&ex=3#:~:text=There%20may%20be%20situation%20when,matrix%20from%20
the%20highest%20element.

15.12 TOPICS FOR DISCUSSION FORUMS

 Discuss the mathematical formulation of assignment problem.

 Discuss the algorithm with your classmates to solve an assignment problem.

12