Industrial Engineering and Operations Research (ME 401)
Assignment Problem
7th Semester
Mechanical Engineering
Introduction
An assignment problem is a particular case of transportation problem.
The objective is to assign a number of resources to an equal number, of activities.
So as to minimize total cost or maximize total profit of allocation.
The problem of assignment arises because available resources such as men,
machines etc. have varying degrees of efficiency for performing different
activities, therefore, cost, profit or loss of performing the different activities is
different.
Suppose that the n jobs need to be performed on m machines (one job to one
machine).
The objective is to assign the jobs to the machines at the minimum cost (or
maximum profit).
Under the assumption that each machine can perform each job but with varying
degree of efficiencies.
Matrix Form of Assignment Problem
The assignment problem can be stated that in the form of mxn matrix cij called a Cost
Matrix (or) Effectiveness Matrix where cij is the cost of assigning i th machine to jth job.
Mathematical Formulation of an Assignment Problem
Consider an assignment problem of assigning n jobs to n machines (one job to one
machine). Let cij be the unit cost of assigning ith machine to the jth job and, ith machine
to jth job.
Let xij = 1 , if jth job is assigned to i th machine.
xij = 0 , if jth job is not assigned to i th machine
Difference Between Transportation Problem and Assignment Problem
[Link] Transportation Problem Assignment Problem
Supply at any source may Supply at any source
1 be any positive quantity ai. (machine)will be 1.
i.e., ai = 1.
Demand at any destination may Demand at any destination
2 be any positive quantity bj. (job) will be 1. i.e., bj
= 1.
One or more source to any One source (machine) to
3 number of destinations. only one destination (job).
Assignment Algorithm (or) Hungarian Method
First check whether the number of rows is equal to number of columns, if it is so, the
assignment problem is said to be balanced. Then proceed to step 1. If it is not balanced, then
it should be balanced before applying the algorithm.
Step 1: Subtract the smallest cost element of each row from all the elements in the row of the
given cost matrix. See that each row contains atleast one zero.
Step 2: Subtract the smallest cost element of each column from all the elements in the column
of the resulting cost matrix obtained by step 1 and make sure each column contains atleast one
zero.
Step 3: (Assigning the zeros)
(a)Examine the rows successively until a row with exactly one unmarked zero is found. Make
an assignment to this single unmarked zero by encircling it. Cross all other zeros in the
column of this encircled zero, as these will not be considered for any future assignment.
Continue in this way until all the rows have been examined.
(b) Examine the columns successively until a column with exactly one unmarked zero
is found. Make an assignment to this single unmarked zero by encircling it and cross
any other zero in its row. Continue until all the columns have been examined.
Step 4: (Apply Optimal Test)
a) If each row and each column contain exactly one encircled zero, then the
current assignment is optimal.
b) If atleast one row or column is without an assignment (i.e., if there is atleast one
row or column is without one encircled zero), then the current assignment is not
optimal. Go to step 5. Subtract the smallest cost element of each column from
all the elements in the column of the resulting cost matrix obtained by step 1
and make sure each column contains atleast one zero.
Step 5: Cover all the zeros by drawing a minimum number of straight lines as
follows:
(a)Mark the rows that do not have assignment.
(b)Mark the columns (not already marked) that have zeros in marked rows.
(c)Mark the rows (not already marked) that have assignments in marked columns.
(d)Repeat (b) and (c) until no more marking is required.
(e)Draw lines through all unmarked rows and marked columns. If the number of these
lines is equal to the order of the matrix then it is an optimum solution otherwise not.
Step 6: Determine the smallest cost element not covered by the straight lines.
Subtract this smallest cost element from all the uncovered elements and add this to all
those elements which are lying in the intersection of these straight lines and do not
change the remaining elements which lie on the straight lines.
Step 7: Repeat steps (1) to (6), until an optimum assignment is obtained.
Problem 1: Solve the following assignment problem shown in Table using
Hungarian method. The matrix entries are processing time of each man in hours.
Solution: The given problem is balanced with 5 job and 5 men.
Subtract the smallest cost element of each row from all the elements in the row of the
given cost matrix. See that each row contains atleast one zero.
Subtract the smallest cost element of each row from all the elements in the row of the
given cost matrix. See that each row contains atleast one zero.
Assigning the zeros, the following A =
Since each row and each column contain exactly one encircled zero, then the
current assignment is optimal.
Where the optimal assignment is as 1 to II , 2 to IV , 3 to I , 4 to V and 5 to III.
The optimal z = 15 + 14 + 21 + 20 + 16 = 86 hours