Assignment Problem
Dr. Ramesh Kumar Chaturvedi
UNIT II
What an Assignment problem is?
• When we want to solve a linear programming
problem with special characteristic such as a
Square Matrix (i.e. No. of destinations are
same as no. of sources)
• When each source (resource facility) can be
associated with one and only one
job/destination (One job to one machine)
• Association is to be done in such a way to
maximize or minimize the total effectiveness.
Few examples of Assignment problem
• Assigning sales man to sales territory
• Vehicles and drivers to different routes
• Product to factories
• Jobs to a machines
• Contract to Bidders
• Research problem to teams
Can you think of Problem that suits to Assignment
methodology?
A case Assignment problem
Mettalica Works Ltd. Is a metal working machine shop. It
generally does work on contract basis. At present it has
four jobs – A,B, C, C in hand. Mettalica has four
machines – 1,2 ,3 and 4. The jobs can be performed on
all machines. However the cost of performing a job on
different machines vary because of capacity machine
and characteristics of the job. The jobs are to be
exclusively performed on any one machine as the setup
cost is too expensive to permit setting of an other
machine for same job. An estimate has been made of
the cost of performing the job on each machine and
estimated cost data is tabulated below:
Tables of Job –Machines
Table 1
JOB/ 1 2 3 4
Machine
A 20 36 31 17
B 24 32 40 12
C 22 40 38 18
D 36 39 35 16
The above matrix highlights that if job A is performed out on
machine 1, it would cost Rs. 20, if performed on Machine 2 the cost
would be Rs. 36, for Machine cost would be Rs. 31 and on Machine
4 cost would be RS 17.
Matellica would like to schedule the jobs on machine so that over
all cost is minimum.
Back to final Assignment
The Hungarian method of solving the
Assignment Problem
• Step 1: Determine the opportunity Cost table
from Table 1.
a. Subtract the lowest entry in each row with all
the entries in that row.
b. Subtract the lowest entry in a column in
resulting table from a above with all entries
in that column.
The resultant Table is Opportunity cost table.
Row opportunity cost table
JOB/ 1 2 3 4
Machine
A 3 (20-17) 19 (36-17) 14 0
B 12 20 28 0
C 4 22 20 0
D 20 23 19 0
Opportunity cost Tables
JOB/ 1 2 3 4
Machine
A 0 (3 – 3) 0 (19 -19) 0 0
B 9 (12 – 3) 1 14 0
C 1 3 6 0
D 17 4 5 0
Lowest element of the column is
subtracted from all other elements of
column of row opportunity cost table
Step 2
• Determine weather an optimal assignment can
be made( This can be done by assigning all jobs to machines where opportunity
cost is 0)
Check of Optimality:
Draw straight line vertically and horizontally
through the total opportunity cost table in such a
manner that all Zero cells in the matrix are
covered with minimum number of lines.
If number of line is equal to n (for an n X n matrix)
or equal to number of rows or columns; then the
optimal solutions is arrived.
Opportunity cost Tables
JOB/ 1 2 3 4
Machine
A 0 0 0 0
B 9 1 14 0
C 1 3 6 0
D 17 4 5 0
There are only Two lines that could cover all 0’s in cells. But we have 4x4
matrix and for optimal solution number of lines should be equal to n (i.e. 4)
Hence we can not make an optimal assignment.
Other method of drawing minimum
number of straight lines
• Make assignment by selecting row/column with only
one zero.
• Mark (√) the rows for which assignment has not been
made.
• Mark (√) the column which has zeros in marked rows.
• Mark (√) the rows which have assignments in marked
column
• Repeat sub steps above till no more marking is possible
• Draw lines through all unmarked rows and marked
columns.
Step 3
Revise the total opportunity cost table as follows:
a. Select the smallest number in the table that is
not covered by any straight line and subtract it
from all other numbers not covered by any
straight line.
b. Add this number to number lying at the
intersection of any two lines. A new opportunity
cost table is obtained.
C. Go to step 2 with this new opportunity cost table
New Opportunity cost Tables
JOB/ 1 2 3 4
Machine
A 0 0 0 0 Now 1
(0 + 1)
B 8 (9 -10= 1 (1 – 1) = 13 (14-1) 0
0
C 0 (1-1) 2 (3 -1) 5 (6-1) 0
D 16 (17-1) 3 (4-1) 4 (5-1) 0
This is the smallest number in
table not covered by any line;
This the number at
it is to be subtracted from all
intersection of two lines, add
other numbers not covered by
1 to it
any line.
Revisited Step 2
• Determine weather an optimal assignment can
be made
Check of Optimality:
Draw straight line vertically and horizontally
through the total opportunity cost table in such a
manner that all Zero cells in the matrix are
covered with minimum number of lines.
If number of line is equal to n (for an n X n matrix)
or equal to number of rows or columns; then the
optimal solutions is arrived.
New Opportunity cost Tables
JOB/ 1 2 3 4
Machine
A 0 0 0 1
B 8 0 13 0
C 0 2 5 0
D 16 3 4 0
Now number of lines is equal to 4,
equal to the order of the matrix;
hence a optimal solution is obtained.
Step 4
Making the optimal Assignment:
a. Select the a row with only one ‘0’ in it. Make an Assignment
by marking‘ ’ around ‘0’ of this row. After making
assignment cross ’X’ out all other ‘0’s in the corresponding
column. Repeat this step for all remaining rows that fulfil
‘only one zero’ condition.
b. If there is no row (left) with zero, repeat the step a for
column. Cross ’X’ all other ‘0’s in corresponding Row.
C. If all Jobs are yet not assigned and there is no Row or
Column with only one zero, then chose a row or column
arbitrarily and make an allocation to this row/column. Cross
’X’ all other ‘0’s in the same row as well as same column.
Making Optimal assignment
JOB/ 1 2 3 4
Machine
A 0 0 0 1
B 8 0 13 0
C 0 2 5 0
D 16 3 4 0
1. Row D has only one “0”, so make assignment to it (D4). And cross all
other 0 in the corresponding column.
2. After Assignment of D on machine 4, now Row B and C both have only
one Zero. So assignment are made to these rows ( C1 and B2) and
zeros in columns are crossed.
3. Finally only one Zero is left in Row A where Machine three has a Zero
so a job A is assigned to Machine 3 (A3).
Final assignment is as follows:
JOB/ 1 2 3 4
Machine
A 0 0 0 1
B 8 0 13 0
C 0 2 5 0
D 16 3 4 0
1. Cot of performing 4 jobs on 4 machines is : (See original cost Matrix)
A3 = 31
B2=32
C1=22
D4=16
Total = 101
Maximization Problem
• Just Subtract all element of Cost Matrix from
the largest Number in the matrix to; What we
get is a loss matrix.
• Than proceed with steps for a normal
minimization method.
Practice
M1 M2 M3 M4
A 5 7 11 6
B 8 5 9 6
C 4 7 10 7
D 10 4 8 3
How A,B,C, and D jobs be assigned to 4 machines M1 to M4 in order to minimize
the cost?
Opportunity cost Matrix
M1 M2 M3 M4
A 0 2 2 1
B 3 0 0 1
C 0 3 2 3
D 7 1 1 0
1. 0 in red are assignments.
2nd FBS
M1 M2 M3 M4
A 0 1 1 0
B 4 0 0 1
C 0 2 1 2
D 8 1 1 0
1. 0 in red are assignments.
2nd FBS
M1 M2 M3 M4
A 0 0 0 0
B 5 0 0 2
C 0 1 0 2
D 8 0 0 0
1. 0 in red are assignments.
2. Soln. Is 23.